Storage And Retrieval

Question 1

Log-Structured Storage

Answer 1

A type of data storage system that treats its storage as a circular log and weird all updated sequentially.

Question 2

SSTable

Answer 2

Sorted String Table
Data structure used for storing large amount of data.

Question 3

LSM-Tree

Answer 3

Data structure designed for write heavy workload.
They store data in two or more separate components.
LSM-Tree comprise two parts:
- A memory component, Memtable
- A series of SSTable files on disk

Question 4

Bloom filter

Answer 4

A data structure that uses minimal amount of memory to probabilistically determine if an element belong to a set.

LSM-trees use bloom filter to reduce disk lookup for non existent keys. Since the bloom filter can definitively say that the key is not in the SSTable, the LSM-Tree can avoid a costly lookup.