Column Overhead and Sizing
Every column in a ColumnFamily requires overhead. And since every row can contain different column names as well as a different number of columns, the column meta-data must be stored with every row.
For every column, the following must be saved:
name : 2 bytes (len as short int) + byte[]
flags : 1 byte
if counter column : 8 bytes (timestamp of last delete)
if expiring column : 4 bytes (TTL) + 4 bytes (local deletion time)
timestamp : 8 bytes (long)
value : 4 bytes (len as int) + byte[]
For the majority of us (the ones not using TTL or Counters) the formula would be:
Ø Column size = 15 + size of name + size of value
This tells us that if you have columns with small values, the column metadata can account for a non-trivial part of your storage requirements. For example let's say you are using a timestamp (long) for column name and another long for the column value. Using the formula:
column size = 15 + 8 + 8 = 31 bytes. 23 (bytes of overhead to store 8 bytes of data!)
See org.apache.cassandra.db.ColumnSerializer for more details.
Row Overhead and Sizing
Just like columns, every row incurs some overhead as well when stored on disk in an SSTABLE. As you can see below, I don't have values for the bloom filter nor index overhead. Calculating them is proportional to the size of the row and number of columns. I'll give a rough estimate for both of them, but I don't completely understand bloom filters, so forgive me. For every row, the following is stored:
key : 2 bytes (len as short) + byte[]
flag : 1 byte (1 or 0)
ColumnFamily ID : 4 bytes (int)
local deletion time : 4 bytes (int)
marked for delete time : 8 bytes (long)
column count : 4 bytes (int)
data : all columns (overhead + data)
row bloom filter : ???
row index : ???
As you can see there is a lot going on when storing a row of columns! Minimally there are 26 bytes of overhead (including minimum size for bloom filter.) It is basically impossible to predict the actual row size if your key size varies or your column data size varies. So best just to pick some averages for key size, number of columns, etc and get an estimate:
Ø row overhead = 23 + avg key size + bloom filter size + index size
Bloom Filter Size
The bloom filter is complicated and the following formula is only an estimate, but should capture the majority of use cases … if I understand things correctly:
Ø bloom filter size = 2 bytes (len as short) + (8 + ceiling((number of columns * 4 + 20) / 8))
Example: if you have 40 columns, then the bloom filter will require ~33 bytes.
For a row with only a few columns and not much data the size of the bloom filter seems more significant than a row with many columns.
See org.apache.cassandra.utils.BloomFilter and org.apache.cassandra.utils.BloomFilterSerializer for more details.
Index Size
The row index helps optimize locating a specific column within a row. The size of the index will normally be zero unless you have rows with a lot of columns and/or data. For the index size to grow larger than zero, the size of the row (overhead + column data) must exceed column_index_size_in_kb, defined in your YAML file (default = 64.) If the size is exceeded, one index entry is created for each column_index_size_in_kb number of bytes in the row. So if your row is 80kb, there will be two index entries.
An index entry consists of:
first col name : 2 bytes + byte[]
last col name : 2 bytes + byte[]
offset into the row data : 8 bytes (long)
width of data : 8 bytes (long)
The formulat for calculating number of index entries:
Ø number of entries = ceiling(row data size / column_index_size_in_kb)
The formula for calculating size of index an index entry:
Ø entry size = 20 + first size + last size
Each entry will be a different size if your column names differ in size, so you must calculate an average column name size for sizing the row like this:
Ø row index size = 4 bytes [len as int] + if index size > 1 => (20 + 2 * avg name size) * numEntries
So if you have 80kb worth of data in a row and the avg column name size is 10, then the index will require the following space:
number of entries = ceiling(80kb / 64kb) = 2
row index size = 4 + (20 + 2 * 10) * 2
row index size = 84 bytes
And if you have 23kb worth of data in a row and the avg column name size is 10, then the index will require the following space (notice that the length of the index is always saved which requires 4 bytes):
number of entries = ceiling(23kb / 64kb) = 1
row index size = 4 + 0
row index size = 4 bytes
As you can see the size of the index isn't that large compared to the size of the row for default settings. Since it is only created if the size of the row exceeds column_index_size_in_kb, most of us do not incur the overhead of the index. And you probably should not care about it unless you have a lot of rows with a large number of columns, and/or have reduced the column_index_size_in_kb setting.
See org.apache.cassandra.io.sstable.IndexHelper for more details.
SSTABLE Overhead and Sizing
Every SSTABLE has a Data file that contains the actual column data. Also there is an Index, Bloom Filter, and Statistics data associated with it - each stored in its on file separate from the row data. The size of each of these is determined by the number of rows and the key size.
Index Overhead
The index is for quickly finding where in an SSTABLE the key and its data are located. For an index there is one entry per row key:
Row key
|
2 bytes (length) + byte[]
|
File offset into Data file
|
8 bytes (long)
|
So the index size is dependent on the number of rows and size of your keys. For sizing purposes, just pick an average key size:
Ø index size = rows * (10 + avg key size)
There is also a summary index and segment boundary markers, but they are not worth calculating - and I didn't want to figure it out ;) What we can surmise from this is that the index overhead is not tiny but will only be significant if you have very narrow and skinny rows.
Bloom Filter Overhead
Bloom filters are used to quickly determine if an SSTABLE contains a key. The bloom filter for SSTABLES is calculated similar to rows, but has a different target. Otherwise the same code applies. As I mentioned earlier, I am not that familiar with the bloom filter algorithm and this is just an approximation for sizing:
Ø bloom filter size = (numRows * 15 + 20) / 8
The same can be surmised for bloom filters as the indices, if you have lots of narrow and skinny rows then the overhead for the bloom filter will be more significant.
Statistics Overhead
Very very minimal and not worth calculating.
See org.apache.cassandra.io.sstable.SSTableWriter for more details.
Replication Overhead
Replication will obviously play a role in how much storage is used. If you set ReplicationFactor (RF) = 1 then there isn't any overhead for replicas (because you don’t have any.) However if RF > 1 then your total data storage requirement will include replication overhead:
Ø replication overhead = (base storage) * (RF-1)
"base storage" is based on all the calculations we've made in the previous sections – see the summary table below.
Snapshots
On linux, snapshots are made by creating hard links (man ln) to all of the data files. By definition a hard link cannot be made across logical volumes, so the snapshots will exist on the same volume as your data files. This is very fast and does not count against storage usage until SSTABLES are removed leaving only the snapshot reference to the files. So you can either do nothing (consuming disk space), or move them off to another volume.
If you choose to keep them on the same volume, then make sure you take into account the size of a snapshot, which is the same size as your total storage requirement.
More Overhead!
So it seems all I can talk about is overhead overhead overhead. Well there is (at least) one more place Cassandra uses storage, during compaction. When Cassandra performs a compaction (major or minor type) it combines a subset of existing SSTABLES into one new SSTABLE. During the process Cassandra will discard tombstoned data and merge rows. How much extra space is required? Up to the total required storage size we’ve calculated thus far. That means that you need an _additional_ “total storage” size. If there are tombstones that can be cleared, then the extra storage will be less depending on how often you delete data. Once the process is completed the original SSTABLES are marked as compacted and will be removed during the next GC or Cassandra restart.
Ø Extra space for compaction = an additional "total storage” size
Example: Suppose compaction is combining 4 SSTABLES 1gb each. If there are no tombstones, the process will require 4gb of extra space.
Storage Sizing Summary
The following table clearly defines and summarizes the formulas from previous sections:
Number of Rows
|
NR
|
Estimated or Target number of rows in your ColumnFamily
|
Number of Columns Per Row
|
NC
|
Estimated/Average number of columns per row
|
Total Number of Columns
|
TNC
|
Number of columns in ColumnFamily
|
Column name size
|
CNS
|
Average size of name of column
|
Column value size
|
CVS
|
Average size of data stored in a column value
|
Row key size
|
RKS
|
Average size of keys
|
ReplicationFactor
|
RF
| |
Number of Nodes
|
NN
|
Number of nodes in cluster
|
Column data
|
NR * NC * CVS
| |
Column overhead
|
NR * NC * (15 + CNS)
| |
Column overhead (counter)
|
NR * NC * (23 + CNS)
| |
Column overhead (w/TTL)
|
NR * NC * (19 + CNS)
| |
Row header overhead
|
NR * (23 + RKS)
| |
Row bloom filter
|
NR * (2 bytes (len as short) + (8 + ceiling((NC * 4 + 20) / 8)))
| |
Row index
|
4 bytes [len as int] + if index size > 1 => (20 + 2 * avg name size) * numEntries
|
Number of entries in index is always written. See above for more details
|
SSTABLE index
|
NR * (10 + RKS)
| |
SSTABLE bloom filter
|
(NR * 15 + 20)/8
| |
Base Storage
|
BS
|
Sum of everything above
|
Additional Replicas
|
BS * (RF-1)
| |
Compaction Overhead
|
BS * RF
| |
Total Storage
|
BS * RF * 2
| |
Snapshots
|
Total Storage
|
For every snapshot, “Total Storage” space is required. Remember to move them off the data volume and you will recover the space
|
Every column requires overhead that cannot be overlooked
For sizing purposes just assume your column names are 10 bytes each, so the total overhead per column is 15 + 10 = 25 bytes. That's just the overhead, don't forget about the actual size of the values. It's the ratio of the data size to the overhead that surprises people. If you have a lot of columns with small data sizes you will very likely have more overhead than actual data.
Compaction overhead requires enough space for an additional copy of the data
This figure assumes no deletes. This is a _LARGE_ requirement which is being optimized in a future Cassandra release.
Use Case where overhead far exceeds data size
Let's say we want to save the the number of times per day that a URL on our website has been accessed. And we’ll assume that over time, 1 million URLs will be accessed on average about 10 different days per URL.
NR
|
1,000,000
|
Estimated or Target number of rows in your ColumnFamily
|
NC
|
10
|
Average over all the rows
|
TNC
|
10,000,000
|
Total number of columns
|
CNS
|
8
|
All names are timestamps (long)
|
CVS
|
4
|
All values are counts (integer)
|
RKS
|
50
|
Average URL length
|
RF
|
3
|
Replication Factor
|
Number of Nodes
|
9
|
We will have the following space requirement:
Column data
|
1,000,000 * 10 * 4
|
40mb
|
Column overhead
|
1,000,000 * 10 * (15+8)
|
230mb
|
Row header overhead
|
1,000,000 * (23 + 50 + 0)
|
73mb
|
Row bloom filter
|
1,000,000 * (2+8 + ceiling((10 * 4 + 20) / 8))
|
18mb
|
Row index
|
RI = 1,000,000 * 4
|
4mb
We assume no indices because it will require 2,428 days to exceed the default column_index_size_in_kb limit.
|
SSTABLE index
|
1,000,000 * (10 + 50)
|
60mb
|
SSTABLE bloom filter
|
(1,000,000 * 15 + 20)/8
|
1.9mb
|
Base Storage
|
BS
|
426,875,003 = ~427mb
|
Additional Replicas
|
427mb * (3-1)
|
853,750,005 = ~854mb
|
Compaction Overhead
|
427mb * 3
|
1,280,625,008 = ~1,281mb
|
Total Storage
|
427mb * 3 * 2
|
2,561,250,015 = ~2,561mb
|
Actual column value data = 40mb (9.4%)
Column overhead = 230mb (53.9%)
Row overhead = 95mb (22.2%)
SSTABLE overhead = 61.9mb (14.5%)
Summary
So you can see that in the example Use Case the overhead is over 9 times the actual data size! This doesn’t mean the overhead is bad or should be reduced. In this case the column names do more than simply designate a value, they actually store the timestamp (date) when the URL was accessed. This exercise is merely to determine your required storage footprint and allow you to plan for the future.
Enjoy
References