# Stratum: A KV Store in Go

The inspiration behind this project was to revise syntax but I'm happy this matured into something far better than what I hoped for :)

A key value store is a very simple type of database. It works by initialising a continuous block of memory (like an array) of size BUCKET\_SIZE.

![](https://cdn.hashnode.com/uploads/covers/6a51f8fc428c6df4e7cbb9e1/dddda345-f3b8-45ca-9338-ad2efb92b100.png)
Similar to a typical database, KV store has 3 main operations:

*   PUT - To insert the key and value
    
*   GET - To get the value stored at 'key'
    
*   DELETE - To delete the stored key value pair
    

Now how do we decide which block or array to insert a key in? A naive way would be to just insert in the first block that's free. But as the size of the table grows, this becomes more inefficient as the complexity will soon approach O(n).

What could be a better solution? Instead of searching for an empty bucket in the table, what if you somehow got the bucket from the key itself?

This is where hashing comes in. You can hash the key and modulo by bucket size to get the bucket it's supposed to go to.

![](https://cdn.hashnode.com/uploads/covers/6a51f8fc428c6df4e7cbb9e1/8412ab5c-979e-4fe1-a5ad-6a962f1471e7.png)

This method works fairly well. However, an issue is that as the buckets get more filled, collisions become more likely. Therefore, we will need a way to deal with collisions (ie, when a key value pair wants to occupy a bucket but it is already taken by another key value pair).

![](https://cdn.hashnode.com/uploads/covers/6a51f8fc428c6df4e7cbb9e1/89dc1958-50ba-497d-b34d-e0f289d6dd77.png)

There are multiple ways to handle collisions, but the one I'll be talking about is separate chaining. In this method, a bucket stores a linked list and each node points to the next node in the chain, which stores a key value pair. Checking if a key exists would require traversing all the nodes of the linked list.

![](https://cdn.hashnode.com/uploads/covers/6a51f8fc428c6df4e7cbb9e1/a2c38550-1843-4766-90d3-97ed57412d4b.png)

Although this can directly be implemented, Go supports something known as dynamic slices. Meaning instead of storing them as linked lists in a bucket, you can store them like below:

```plaintext
Bucket 0
[
  cat    : 50
  dog    : 75
]

Bucket 1
[
  grape  : 90
]

Bucket 2
[
  apple  : 10
  banana : 25
  orange : 30
]

Bucket 3
[
  kiwi   : 15
  mango  : 45
]
```

This is very similar to how separate chaining works, but works without the additional overhead of storing a Next Ptr for each node, thus making it more memory efficient.

With all this, now we're ready to implement our `PUT` function that takes a key value pair and inserts it into the table (also known as memtable as all the key value pairs are stored in memory).

Implementing `GET` is also fairly simple. Traverse the memtable and check if `entry.key == key1` where `key1` is the key being searched for. It's important to remember that since our implementation can store multiple KV pairs in a single bucket, you will have to use two for loops to check if the entry exists within a bucket.

Deletion also follows a similar approach. Search for the key, and once the key is found, remove it.

There's actually a fairly smart syntax that you can use here to do this, which I found very cool.

```go
table[bucket] = append(table[bucket][:index], table[bucket][index+1:]...)
```

This line says that take all the entries present till index, and to that slice, append every entry after index+1. This means the element at index is deleted. The `…` after index +1 is because `table[bucket][index+1:]` returns a slice, and append expects individual elements rather than a slice. The `…` unpacks (spreads) that slice into individual arguments so append can use them.

With this, we are done with the three main functions of a simple KV Store :)

Now let's think about this further, what are some cases that we could have missed out in this implementation?

What would happen if the memtable is completely filled with KV pairs? At that point the very next insertion would fail. How would we prevent this?

The solution is to create another function that checks if the load factor (ENTRIES/BUCKET\_SIZE) >= 0.75. If this condition is true, meaning more than 75 percent of the memtable is full, then the memtable will have to be resized to a bigger amount.

The reason why we are resizing the table when it's 75 percent filled is because

1.  Inserting a lot of entries in one bucket makes traversal slower since each bucket now has more entries.
    
2.  Maintaining a low load factor gives an average lookup time of O(1), thereby increasing performance.
    

Increasing the bucket size would require every entry inside the memtable to be rehashed. Recollect that `bucket := hash(key) / BUCKET_SIZE`. Since bucket size has changed, we would have to traverse and rehash every key in each bucket. The following code snippet accomplishes this.

```go
func resize() {
	// every entry in a bucket has to be rehashed and appended to new table
	if float64(ENTRIES)/float64(BUCKET_SIZE) > 0.75 {
		NEW_BUCKET_SIZE := 2 * BUCKET_SIZE
		new_table := make([][]Entry, NEW_BUCKET_SIZE)
		for _, bucket := range table {
			for _, entry := range bucket {
				new_bucket := int(hash(entry.key) % uint64(NEW_BUCKET_SIZE)) // bucket should be int
				new_table[new_bucket] = append(new_table[new_bucket], entry)
			}
		}
		table = new_table
		BUCKET_SIZE = NEW_BUCKET_SIZE
	}
}
```

And with that, we are done with a very basic KV Store in Go :)

I have implemented some more advanced concepts (WAL, SSTables, etc) to take this idea further, which I will touch upon in my next blog post.

Thanks for reading :)

GitHub repo: https://github.com/0xmaster7/Stratum/
