contains spoilers, proceed with caution!
Below is the order in which you should pass the tests:
test header op
test encode kv
test disk CaskDB
test disk CaskDB existing file
I have relisted the tasks here again, but with more details. If you have difficulty understanding the steps, the following should help you.
The word 'paper' might scare you, but Bitcask's paper is very approachable. It is only six pages long, half of them being diagrams.
Test | test header op |
---|
The next step is to implement a fixed-sized header similar to Bitcask. Every record in our DB contains a header holding metadata and helps our DB read values from the disk. The DB will read a bunch of bytes from the disk, so we need information on how many bytes to read and from which byte offset.
Some more details:
The header contains three fields timestamp, key size, and value size.
Field | Type | Size |
---|---|---|
timestamp | int | 4B |
key_size | int | 4B |
value_size | int | 4B |
We need to implement a function which takes all these three fields and serialises them to bytes. The function signature looks like this:
function encodeHeader(buffer: Buffer, timestamp: number, keySize: number, valueSize: number): void
Then we also need to write the opposite of the above:
function decodeHeader(data: Buffer): [number, number, number]
More Hints:
- Read this comment to understand why do we need serialiser methods
- Check out the documentation of
Buffer
for serialisation methods in Node.js - Not sure how to come up with a file format? Read the comment in the format module
Test | test encode kv |
---|
Now we will write encode and decode methods for key and value.
The method signatures:
function encodeKV(timestamp: number, key: string, value: string): [number, Buffer]
function decodeKV(data: bytes): [number, string, string]
Note that encodeKV
method returns the bytes and the bytes' size.
Test | test disk CaskDB |
---|
This step involves figuring out the persistence layer, saving the data to the disk, and keeping the pointer to the inserted record in the memory.
So, implement the DiskStorage
class in disk-store.ts
Hints:
Test | test disk CaskDB existing file |
---|
DiskStorage is a persistent key-value store, so we need to load the existing keys into the KeyDir
at the start of the database.