Open Source Uses About
BaseCode

Building an implementation agnostic Key-Value Store

by Brian Faust – 8 minute read

A key-value store is a form of storage that uses an associative array as its base, think of a dictionary in Python or Hash in Ruby. Each key is unique and has a value assigned to it, those entries are called key-value pairs.

Those key-value pairs always consist of a key which is commonly either a string or number and a value which can be pretty much anything you want it to be. There are some exceptions for things like a WeakMap in JavaScript where the key can be an object.

Use-Cases

There is a wide variety of use-cases for key-value stores for applications at all scales. They range from serving as a simple cache, session management to storing system configurations and statistics for heavy computations.

The performance of those solutions relies on a lot of factors but hardware is a major one as a lot of key-value stores do the majority of their work in-memory so having performant RAM will make a world of a difference together with a good software.

The most popular key-value store out there by a far is probably redis which can serve all of the above mentioned use-cases and more. You probably have used it before in one form or another without even knowing.

Planning

So how could we go on about building our own implementation of a key-value in TypeScript? First we should figure out what our goals are from a technical and human point of view.

  1. Do we want every bit of performance possible? If yes than TypeScript is probably the wrong choice in the first place and we should look at a more performant language like C++ or Rust.
  2. Do we want to be able to easily switch out the underlying store? Most certainly if we want to be ready to scale up and follow the SOLID principles.
  3. Do we want other developers to be able to extend the system? Again a clear yes if you care about the SOLID principles and want to abide to them and provide a greater developer experience.

Designing

Now that we have our goals set we can start to design an implementation contract. But wait, something is missing! What kind of operations do we expect our key-value store to be able to perform? Well this is an easy one as all key-value stores basically perform the same actions and there is no need to reinvent that.

Functionality

  • Return entries, keys and values
  • Create, Read, Update & Delete entries
  • Perform all operations in bulk

Implementation Contract

With those functionalities in mind our implementation contract could look something like the following. Keep in mind that this contains some methods that aren’t stricly included in the above list but certainly needed for a better developer experience.

export interface KeyValueStore<K, T> {
    /**
     * Get all of the items in the store.
     */
    all(): Array<[K, T]>;

    /**
     * Get the keys of the store items.
     */
    keys(): K[];

    /**
     * Get the values of the store items.
     */
    values(): T[];

    /**
     * Retrieve an item from the store by key.
     */
    get(key: K): T | undefined;

    /**
     * Retrieve multiple items from the store by key.
     */
    getMany(keys: K[]): Array<T | undefined>;

    /**
     * Retrieve an item from the store and remove it.
     */
    pull(key: K): T | undefined;

    /**
     * Retrieve multiple items from the store and remove them.
     */
    pullMany(keys: K[]): Array<T | undefined>;

    /**
     * Store an item in the store.
     */
    put(key: K, value: T): boolean;

    /**
     * Store multiple items in the store.
     */
    putMany(values: Array<[K, T]>): boolean[];

    /**
     * Determine if an item exists in the store.
     */
    has(key: K): boolean;

    /**
     * Determine if multiple items exist in the store.
     */
    hasMany(keys: K[]): boolean[];

    /**
     * Determine if an item doesn't exist in the store.
     */
    missing(key: K): boolean;

    /**
     * Determine if multiple items don't exist in the store.
     */
    missingMany(keys: K[]): boolean[];

    /**
     * Remove an item from the store.
     */
    forget(key: K): boolean;

    /**
     * Remove multiple items from the store.
     */
    forgetMany(keys: K[]): boolean[];

    /**
     * Remove all items from the store.
     */
    flush(): boolean;

    /**
     * Count the number of items in the store.
     */
    count(): number;

    /**
     * Determine if the store is empty.
     */
    isEmpty(): boolean;

    /**
     * Determine if the store is not empty.
     */
    isNotEmpty(): boolean;
}

Note that in a real world application I would omit the comments as the method names themselves are already conveying all important information.

Implementation

Now that we have the implementation contract we can start to think about the concrete implementation that will satisfy the contract. In this example we will use a Map as the underlying store but a plain object would work just as fine but requires more boilerplate.

The advantage of a Map is that it itself is already a key-value store so it saves us some time when it comes to implementing certain methods. A Map also has other advantages like being purely a hash without all the prototype logic of an object and preserving the insertion order of keys.

class MapStore<K, T> implements KeyValueStore<K, T> {
    /**
     * The store that holds the key-value pairs.
     */
    private readonly store: Map<K, T> = new Map<K, T>();

    /**
     * Get all of the items in the store.
     */
    public all(): [K, T][] {
        return [...this.store.entries()];
    }

    /**
     * Get the keys of the store items.
     */
    public keys(): K[] {
        return [...this.store.keys()];
    }

    /**
     * Get the values of the store items.
     */
    public values(): T[] {
        return [...this.store.values()];
    }

    /**
     * Retrieve an item from the store by key.
     */
    public get(key: K): T | undefined {
        return this.store.get(key);
    }

    /**
     * Retrieve multiple items from the store by key.
     */
    public getMany(keys: K[]): (T | undefined)[] {
        return [...keys].map((key: K) => this.get(key));
    }

    /**
     * Retrieve an item from the store and remove it.
     */
    public pull(key: K): T | undefined {
        const item: T | undefined = this.get(key);

        this.forget(key);

        return item;
    }

    /**
     * Retrieve multiple items from the store and remove them.
     */
    public pullMany(keys: K[]): (T | undefined)[] {
        const items: (T | undefined)[] = this.getMany(keys);

        this.forgetMany(keys);

        return items;
    }

    /**
     * Store an item in the store.
     */
    public put(key: K, value: T): boolean {
        this.store.set(key, value);

        return this.has(key);
    }

    /**
     * Store multiple items in the store.
     */
    public putMany(values: [K, T][]): boolean[] {
        return values.map((value: [K, T]) => this.put(value[0], value[1]));
    }

    /**
     * Determine if an item exists in the store.
     */
    public has(key: K): boolean {
        return this.store.has(key);
    }

    /**
     * Determine if multiple items exist in the store.
     */
    public hasMany(keys: K[]): boolean[] {
        return [...keys].map((key: K) => this.has(key));
    }

    /**
     * Determine if an item doesn't exist in the store.
     */
    public missing(key: K): boolean {
        return !this.has(key);
    }

    /**
     * Determine if multiple items don't exist in the store.
     */
    public missingMany(keys: K[]): boolean[] {
        return [...keys].map((key: K) => this.missing(key));
    }

    /**
     * Remove an item from the store.
     */
    public forget(key: K): boolean {
        return this.store.delete(key);
    }

    /**
     * Remove multiple items from the store.
     */
    public forgetMany(keys: K[]): boolean[] {
        return [...keys].map((key: K) => this.forget(key));
    }

    /**
     * Remove all items from the store.
     */
    public flush(): boolean {
        this.store.clear();

        return this.count() === 0;
    }

    /**
     * Count the number of items in the store.
     */
    public count(): number {
        return this.store.size;
    }

    /**
     * Determine if the store is empty.
     */
    public isEmpty(): boolean {
        return this.count() === 0;
    }

    /**
     * Determine if the store is not empty.
     */
    public isNotEmpty(): boolean {
        return !this.isEmpty();
    }
}

This implementation is very lean as we make use of the native Map that provides most methods we need out-of-the-box so that we only need to implement a handful of methods ourselves. The advantage of this approach is that we don’t need to add our own methods to handle things like null, undefined and falsy which will save us some headaches.

Testing

Now that the implementation is done we need to test it to ensure it is working as intended. In this example we will only cover the pullMany method which grabs some values by their keys from the key-value store and removes the values that belong to the key. We test both the happy path of items being set and pulled with their values and the unhappy path of items not being set and returning undefined to ensure we cover the success and failure of the operation.

let store: MapStore<string, number> = new MapStore<string, number>();

beforeEach(() => store.flush());

describe(".pullMany(keys)", () => {
    const keys: string[] = ["a", "b", "c"];
    const values: number[] = [1, 2, 3];

    it("should pull many items from the store", () => {
        store.put(keys[0], values[0]);
        store.put(keys[1], values[1]);

        expect(store.isNotEmpty()).toBeTrue();
        expect(store.pullMany([keys[0], keys[1]])).toEqual([
            values[0],
            values[1]
        ]);
        expect(store.isEmpty()).toBeTrue();
    });

    it("should fail to pull non-existent items from the store", () => {
        expect(store.pullMany([keys[0]])).toEqual([undefined]);
    });
});

The full test suite is out of scope this post but you can find it for both the sync and async implementation at keeveestore-test-suite.

Conclusion

Building your own key-value store is a great way of understanding their inner workings better and putting you in control of the implementation. The implementation of the MapStore satisfies the KeyValueStore implementation contract and enables us to use KeyValueStore as a type hint in our application instead of the concrete. This decouples us from the concrete implementation such as MapStore and gives us the freedom to switch it out for a RedisStore without any other changes to our application.

Bonus

If you want to see more examples of implementation agnostic packages you can check out Emittr, HTTPack, KeeVeeStore, Logks and VeeStore


More about typescript, agnostic, testing & best practice

npm vs. yarn vs. pnpm