Brute force finding something inside a database would be a terrible idea and lead to terrible performance. Thus, indexing is useful. The main idea is to keep some additional metadata on the side that act as signposts to locate the date.
Index will slows down write but speed up read.
Hash Indexes
Starts with example of key-value stores.
- data store only appends to a file
- there’s an in-memory hash map where every key is mapped to a byte offset in the data file (location)
- on new append, the hash map is updated to reflect the offset
- on lookup, use hash map to find the offset, read the file using location to obtain value
How to avoid running out of disk space? To break the log into segments of a certain size, and making subsequent writes to a new segment file.
Compaction can also be made: throw away duplicate keys and keeping only the most recent update. After compaction, several logs can be merged together to a new file. (those need to be done in a background thread)
Several things to keep in mind:
- File format: use a binary format that first encodes the length of a string in bytes, followed by the raw string (no need for escaping)
- Deleting records: need to append a special deletion record. When log segments are merged, those record are discarded
- Crash recovery: if database is restarted, the in-memory hash maps are lost. The recovery can be done by reading the log files in theory, but keeping a snapshot of the hash map could be more efficient.
- Partially written records: Files could include checksums to allow the corrupted parts of the log to be detected and ignored.
- Concurrency control: since writes are appended to log in strictly sequential order, an implementation is to have only one writer thread.
SSTables and LSM-Trees
if the sequence of key-value pairs is sorted by key, then this format is Sorted String Table or SSTable.
Each key only appears once within each merged segment file.