Write Heavy DB Design

Write Heavy DB Design

A write heavy database is designed so that a write costs as little as possible. A traditional database keeps its data in a B+ tree, where insertion and search are both order log n. Every SQL command is one I/O call and gets its own acknowledgement.

Two ideas make writes cheaper:

1. Condense the data queries into a single query. The server gathers them into one block and sends it in one shot: one I/O call, one acknowledgement. The server gives up some memory to hold the block.
2. Write to a log. A log follows the linked list: a write appends at the end, in constant time.

The log has fast writes and slow reads, because a read searches it sequentially, in order n.

A sorted array is searched in order log n. A linked list for the writes with a sorted array for the reads gives great write speeds and great read speeds. This is where the log structured merge tree comes from.

Write Heavy DB Design - Merging Sorted String Tables

A log is fast to write and slow to read, so the database persists the log's records in sorted order and reads them with a binary search.

The server appends each new record to a log in memory. At a threshold the records are sent to the database in one shot and stored sorted.

The database can treat the next batch in three ways:

1. Merge it into the one sorted file. Six records and six records make a sorted file of 12. After 10,000 records, six more force 10,000 and six records to be sorted, at n log n.
2. Keep every batch as its own sorted chunk. Writes stay fast. A read does a binary search on each chunk, and n insertions leave n divided by six chunks, so reads are order n.
3. A hybrid. Chunks are merged as long as the sort time is not too high.

A merge moves a pointer along each of two sorted arrays and keeps taking the smaller element.

Write Heavy DB Design - Query optimisations

A log structured merge tree speeds up reads by merging sorted chunks in the background into larger sorted arrays that can be binary searched.

Three chunks of size 6 hold 18 records. A search in one chunk takes approximately 3 operations, so a search in all three takes around 9. Merging two chunks into a sorted array of size 12 brings that to 7.

The merging is similar to merge sort:

1. Two blocks of size 6 become a block of size 12.
2. Two blocks of size 12 become a block of size 24, searched in approximately 5 operations instead of 12.
3. The blocks are of varying size, and a read is spread across them.
4. A Bloom filter on top of each chunk tells whether a record exists in it. It has false positives and no false negatives.
5. A merged array gets a larger Bloom filter, which reduces the chance of a false positive.

A sorted set of records is called a sorted string table. Merging sorted string tables into a single array is called compaction.

Quorom

Quorum is a way in which the nodes that hold a piece of data vote for a value, and the value a majority accepts is taken as the truth.

The replication factor is three: nodes 5, 1 and 2 hold the profile. Node 5 crashes before a read.

With a quorum of 2:

1. Node 1 does not have the data and node 2 has it. The data with the latest timestamp is returned, and the user sees the profile.
2. Both have it. The correct data is returned.
3. Neither has the write replicated yet. Both agree that there is no profile, and the user gets a wrong error.

The third case is rare, and it is the risk taken with a NoSQL database, which moves forward with availability instead of consistency.

With a quorum of 3, the query fails, because node 5 does not return a value.

Most of the time, when the nodes do not agree on a value, the database query fails and the user is told the system is unavailable.