Data Structures : That Power Your Database Part - 1
Consider the world’s simplest database, implemented as two functions:
setData to save data at the end of the document and getData to get Data from the document.
function setData(key: string,data : String){
// Save the data in a Document
}function getData(key: string) : String {
// get the data from the Document
return data ;
}Performance:
When we talk about the performance of the above database it gives high performance when we have to save the data, simply adding data at the end of the Document.
But when we have to retrieve the data we have to traverse all the documents and return the data. so the time complexity in this case will be O(n).
To efficiently find the value for a particular key in the database, we need a different data structure: an index.
An index is an additional structure that is derived from the primary data. Many databases allow you to add and remove indexes, and this doesn’t affect the contents of the database, it only affects the performance of queries.
Keep in Mind :
Maintaining additional structures incurs overhead, especially on writes. For writes, it’s hard to beat the performance of simply appending to a file, because that’s the simplest possible write operation. Any kind of index usually slows down writes, because the index also needs to be updated every time data is written.
Hash Indexes :
Let’s start with indexes for key-value data. Key-value stores are quite similar to the dictionary type that you can find in most programming languages, and which is usually implemented as a hash map.
Let’s say our data storage consists only of appending to a file, as in the preceding example. Then the simplest possible indexing strategy is this: keep an in-memory hash map where every key is mapped to a byte offset in the data file—the location at which the value can be found see below Diagram .
Lets add below data in database:
123,{"name":"USA","city":["Newyork"]}Offset of key 123 will be 0 as it is the first record in in-memory hash map which improve retrieval of data fast.
Getting a Value with Indexing:
To retrieve a value, we consult the hash index to find the exact location of the data in the file, which drastically reduces retrieval time.
Hash table index also has limitations:
• The hash table must fit in memory, so if you have a very large number of keys, you’re out of luck. In principle, you could maintain a hash map on disk, but unfortunately it is difficult to make an on-disk hash map perform well. It requires a lot of random access I/O, it is expensive to grow when it becomes full, and hash collisions require fiddly logic ..
• Range queries are not efficient. For example, you cannot easily scan over all keys between kitty00000 and kitty99999—you’d have to look up each key individually in the hash maps.
Segmentation
Since we always append to the text file whenever a key-value entry comes up to be stored, so how do we avoid eventually running out of disk space?
A good solution is to break the log into segments of a certain size by closing a segment file when it reaches a certain size, and making subsequent writes to a new segment file. Then we can perform Compaction on these segments.
Compaction and Merging
Now the Compaction process reduces the size of a File-segment. Hence we can Merge multiple segments at the same time while the Compaction process is taking place. The entire process looks like this.
Each segment now has its own in-memory hash table, mapping keys to file offsets. In order to find the value for a key, we first check the most recent segment’s hash map; if the key is not present we check the second-most-recent segment, and so on. The merging process keeps the number of segments small, so lookups don’t need to check many hash maps.
Lots of detail goes into making this simple idea work in practice. Briefly, some of the issues that are important in a real implementation are:
File format
CSV is not the best format for a log. It’s faster and simpler to use a binary format that first encodes the length of a string in bytes, followed by the raw string (without need for escaping).
Deleting records
If you want to delete a key and its associated value, you have to append a special deletion record to the data file (sometimes called a tombstone). When log segments are merged, the tombstone tells the merging process to discard any previous values for the deleted key.
Crash recovery
If the database is restarted, the in-memory hash maps are lost. In principle, you can restore each segment’s hash map by reading the entire segment file from beginning to end and noting the offset of the most recent value for every key as you go along. However, that might take a long time if the segment files are large, which would make server restarts painful. we can speeds up recovery by storing snapshot of each segment’s hash map on disk, which can be loaded into memory
more quickly.
Partially written records
The database may crash at any time, including halfway through appending a
record to the log. Use checksums, allowing such corrupted parts
of the log to be detected and ignored.
Concurrency control
As writes are appended to the log in a strictly sequential order, a common implementation choice is to have only one writer thread. Data file segments are
append-only and otherwise immutable, so they can be read concurrently by multiple threads.
HashIndex also have some limitations :
The hash table must fit in memory, so if you have a very large number of keys,
you’re out of luck.
Range queries are not efficient.
In next article lets discuss how SSTables and LSM-Trees power the Database .
If you like this article please share and subscribe.