When life is hard take it back to the basics. - Alex Daniel

Let us consider the world's simplest database implemented as 2 functions f(x):

var helpers = require('./helper.js');

function setValue(key, value) {
    try {
        helpers.writeToFile(key + "," + value);
    } catch(ex) {
        return false;
    }
    return true;
}

function getValue(key) {
    try {
        return helpers.readFromFile(key);
    } catch (ex) {
        // Log the exception
    }
    return null;
}

These 2 functions implement the key-value store. We can call the setValue function which will store the value associated to a key. The key and value can be any string [1]. We can then call the getValue function to get the most recent value that was assigned to a key.

And it works surprisingly well😍😍:

> setValue("123", '{"name":"tejaram15","likes":["Suits","Avengers"]}')
> true

> getValue("123")
> {"name":"tejaram15","likes":["Suits","Avengers"]}

The underlying storage is basically a text file storing all the information row by row. setValue appends a key-value pair to the end of a text file. getValue searches for the last written key-value pair and returns the value for a given key🔑🔑.

Thought process

Even though this is the most basic implementation possible understanding the thought process is the crux of this series.

I initially implemented the app.js file which abstracted away all the details and was expecting 2 functions which would do all the work for me. These are helper functions and the implementation can be different based on where we are importing them from.

Lesson 1: Always implement the functional requirements(or API specs) on a high level first and then implement the underlying details. This helps in keeping breaking your code into blocks and its easier to implement.

I then moved on to helper.js which would hold the actual low level implementation details. The first thing i implemented is the writeToFile function. While searching google for the query "node js append to a file" i found the fs.writeFileSync API [3]. I implemented a function that took in a string data and appended this to the end of a file with path FILE_NAME. This was a good time to start unit testing because i already had a concrete implementation for one of the core low level functions. I used mocha for unit-testing in nodejs but there are many other options. I implemented the write test first and started testing the function. Some bug fixes later i was able to see that the function was working correctly.

Lesson 2: Always write unit-tests as soon as you implement a function. This will improve the overall test coverage as you won't miss anything un-intentionally. And also make sure you aren't missing any important assumptions.

I implemented the readFromFile function next which had multiple steps to it.

1. First read the file through the fs.readFileSync API [4].
2. Split the data received into multiple lines.
3. Reverse those lines (as we are interested in the last inserted key).
4. Split these lines by a separator (",").
5. Check if the current key matches with the searchKey and return the value.

I then implemented the unit tests for it and pushed the code repository after completing basic tests.

Time complexity analysis

You might have already figured out the time complexity of the operations supported by our key-value store. setValue takes O(1) time in every case and getValue takes O(n) time in the worst case. This isn't the best possible solution. Also since the data is always being written to a single file the size of the file keeps growing infinitely.

We could improve the time-complexity of the reads by maintaining an index of all the keys we are storing in the database. This will be the topic of our next article.

Notes and References

[1] String is used because it is easier to serialize and de-serialize. Additional serialisation will be required if we want to save other primitive types or complex objects.

[2] Repository link🔗🔗: https://github.com/tejaram15/kvstore/tree/basic-kv-store

[3] fs.writeFileSync API🔗🔗: https://www.geeksforgeeks.org/node-js-fs-writefilesync-method/

[4] fs.readFileSync API🔗🔗: https://www.geeksforgeeks.org/node-js-fs-readfilesync-method/

[5] Notion Link: Notion Link

✌🏻✌🏻

Peace.