1 of 14

Storage in NoSQL

1

2 of 14

How is data stored in files?

2

3 of 14

In traditional databases: In-place storage

3

1234, John Smith

3434, Mary Bla

…

Sailors Table file

1234, John Smith

2344, Peter Che

3434, Mary Bla

…

Sailors Table file

INSERT INTO Sailors VALUES(2344, Peter Che)

Expensive: random disk access for each INSERT (or UPDATE or DELETE)

4 of 14

NoSQL Storage (e.g., in Cassandra):�Log Structured Merge (LSM) Tree

4

1234, John Smith

4445, Jay Bla

…

Sailors SSTable (file1)

1234, John Smit

3434, Mary Fu

…

Sailors SSTable (file2)

…

4353, May Wilson

9879, Ray Smith

2344, Peter Che

INSERT INTO Sailors VALUES(2344, Peter Che)

RAM

HDD/SSD

MemTable

Periodically Merged (Compacted)

1234, John Smith

434, Mary Fu

4445, Jay Bla

…

5 of 14

LSM Storage

Facilitates high write throughput, i.e. many writes per second, e.g., Twitter
Complicates reads: first read MemTable, then SSTable1, then SSTable2, … until we find the record
Compactions: Merge multiple SSTables into 1 new SSTable; handle deletes/overwrites
Used in: Apache AsterixDB, Bigtable, HBase, LevelDB, Apache Accumulo, SQLite4, Tarantool, RocksDB, Apache Cassandra

5

6 of 14

LevelDB

Log file
Memtable
Immutable Memtable
SSTable (file)
Manifest file: records smallest, largest key for each SSTable

6

Sanjay Ghemawat

Jeffrey Dean

Compilers don't warn Jeff Dean. Jeff Dean warns compilers.
Jeff Dean's keyboard has two keys: 1 and 0.
When Jeff has trouble sleeping, he Mapreduces sheep.

7 of 14

LevelDB Compaction

Pick one SSTable (level i)
Merge it with all the overlapping SSTables (level i+1) and write them into level i+1

Triggered when Li (i>0) SSTable space exceeds 10^i MB

7

8 of 14

Compaction Strategy in Cassandra

ALTER TABLE users WITH compaction = { 'class' : 'LeveledCompactionStrategy’ }
ALTER TABLE users WITH compaction = {'class' : 'SizeTieredCompactionStrategy', 'min_threshold' : 6 } �triggers minor compaction when there are 6 similar sized SSTables on disk
More info: https://docs.datastax.com/en/cassandra-oss/3.0/cassandra/operations/opsConfigureCompaction.html

8

9 of 14

Compaction Trade-off

High Write Throughput

Infrequent compaction
Compaction creates write stalls

High Read Rate

Frequent compaction
Fewer SSTables accessed per read

9

10 of 14

Bloom Filter: Approximate set membership problem

Quickly check if a key found in an SSTable
Suppose we have a set

S = {s₁,s₂,...,s_m} ⊆ universe U

Represent S in such a way we can quickly answer “Is x an element of S ?”
To take as little space as possible ,we allow false positive (i.e. x∉S , but we answer yes )
If x∈S , we must answer yes .

10

11 of 14

Bloom filters

Consist of an arrays A[n] of n bits (space) , and k independent random hash functions

h₁,…,h_k: U --> {0,1,..,n-1}

1. Initially set the array to 0

2. ∀ s∈S, A[h_i(s)] = 1 for 1≤ i ≤ k

(an entry can be set to 1 multiple times, only the first times has an effect )

3. To check if x∈S , we check whether all location A[h_i(x)] for 1≤ i ≤ k are set to 1

If not, clearly x∉S.

If all A[h_i(x)] are set to 1 ,we assume x∈S

11

[Michael Mitzenmacher Eli Upfal]

12 of 14

12

0

Initial with all 0

1

x₁

x₂

Each element of S is hashed k times

Each hash location set to 1

1

y

To check if y is in S, check the k hash

location. If a 0 appears , y is not in S

1

y

If only 1s appear, conclude that y is in S

This may yield false positive

Bloom filters: example

13 of 14

Bloom Filters

Cassandra:

ALTER TABLE keyspace.table WITH bloom_filter_fp_chance=0.01
Default is 0.1

More RAM?

Lower bloom_filter_fp_chance

Few reads?

Higher bloom_filter_fp_chance

13

14 of 14

Conclusion

LSM trees support fast write throughput
Compactions (merges) run periodically
Write vs. read throughput tradeoff determined by compaction strategy and parameters
Bloom filters used to index keys in SSTable

14