Storage Sizing Spreadsheet

I've been asked for a spreadsheet to help out with calculating storage, so here is one I'm sharing from google docs.   Storage Sizing Spreadsheet

Cassandra Storage Sizing

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

Cassandra 0.8.1 Codebase