## Friday, January 20, 2012

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

## Wednesday, July 20, 2011

### Cassandra Storage 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.

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.

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.

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 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.

Very very minimal and not worth calculating.

See org.apache.cassandra.io.sstable.SSTableWriter for more details.

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.

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%)