Simple implementation

In your copy of the learndb repo, check out the key-value-store-simple_before branch and install the project’s dependencies by running npm install.

The branch contains a few configuration and boilerplate files, including the following:

Path Description
node_modules/ Contains dependencies needed for the project to function
src/benchmarks.js A set of simple benchmarks so we can compare the performance of our key-value store as it progreses
src/key-value-store.js This will contain the implementation of the key-value store
tests/key-value-store.js We'll write some basic end-to-end tests to ensure our implementation works as expected.

For an editor, I recommend using Visual Studio Code. You can open learndb.code-workspace in VSCode for some handy extension recommendations.

Tests

In tests/key-value-store.js, you’ll see a basic test that just makes sure the test runner works.

You can execute tests by running npm run test. The output should appear similar to this:

> @learndb/learndb@0.1.1 test C:\projects\learndb
> run-s test:e2e

> @learndb/learndb@0.1.1 test:e2e C:\projects\learndb
> mocha --require @babel/register --full-trace tests/**/*.js

  KeyValueStore
    √ tests work

  1 passing (10ms)

Let’s add some tests for the methods we expect our key-value store to support. First though, we need to add some setup code to our test suite. Open tests/key-value-store.js and add the following import line after the existing import lines at the top:

import { KeyValueStore } from '../src/key-value-store'

Next, delete the existing test (everything in the describe function, between and including it( and })).

In place of the old test you removed, in the existing describe block, add this setup code:

// Test keys and values we'll use in the new tests
const testKey1 = 'test-key-1'
const testValue1 = 'test-value-1'
const testValue2 = 'test-value-2'

// Contains a fresh instance of the key-value store for each test.
let keyValueStore = null

beforeEach(() => {
  // Before each test, create a new instance of the key-value store.
  keyValueStore = new KeyValueStore()

  // This won't do anything for now, but will be helpful soon when we have
  // to initialize resources such as database files.
  keyValueStore.init()
})

Now each of the tests we add will get its own fresh instance of our key-value store.

Add the following tests to verify our key-value store can perform some basic tasks. Put them inside the describe block, after the beforeEach call.

it('get() returns value that was set()', () => {
  keyValueStore.set(testKey1, testValue1)
  assert.equal(keyValueStore.get(testKey1), testValue1)
})

it('get() returns last value that was set()', () => {
  keyValueStore.set(testKey1, testValue1)
  keyValueStore.set(testKey1, testValue2)
  assert.equal(keyValueStore.get(testKey1), testValue2)
})

it('get() for non-existent key returns undefined', () => {
  assert.equal(keyValueStore.get(testKey1), undefined)
})

it('set() and get() support null value', () => {
  keyValueStore.set(testKey1, null)
  assert.equal(keyValueStore.get(testKey1), null)
})

it('delete() for key causes get() to return undefined', () => {
  keyValueStore.set(testKey1, testValue1)
  keyValueStore.delete(testKey1)
  assert.equal(keyValueStore.get(testKey1), undefined)
})

If you run the test suite now (via npm run test), it’s going to fail spectacularly. We don’t yet have an implementation for our key-value store, so let’s take care of that next.

Remember that we’re starting out with a simple in-memory implementation that will pass our tests and give us something to build on. It’s not very useful, but allows us to make incremental improvements over time.

Simple implementation

Open src/key-value-store.js and replace the content with the following code:

export class KeyValueStore {
  constructor() {
    this.store = {}
  }

  init() {}

  set(key, value) {
    this.store[key] = value
  }

  get(key) {
    return this.store[key]
  }

  delete(key) {
    this.store[key] = undefined
  }
}

You’ve probably noticed that we’re using a newer JavaScript syntax that supports classes, instead of using functions and prototypes. This syntax comes from the ECMAScript 2015 standard (also known as ECMAScript 6 or ES6). You can read more about ES6 classes here.

This simple implementation just stores our data in a JavaScript object, which behaves like an in-memory key-value store.

Now you should be able to run the test suite (via npm run test), and all the tests should pass.

Benchmarks

I’ve included some basic benchmarks to help us keep track of the performance of our database system at various stages of its development. Currently it supports the key-value store methods we just implemented.

You can run the benchmarks with the command npm run benchmarks. Here’s the output when I run the benchmarks on my local machine:

> @learndb/learndb@0.1.1 benchmarks C:\projects\learndb
> node --require @babel/register src/benchmarks.js

Starting RSS memory usage: 57.676 MB
KeyValueStore#set x 1,774,185 ops/sec ±2.53% (84 runs sampled)
KeyValueStore#get x 11,633,332 ops/sec ±3.46% (83 runs sampled)
KeyValueStore#delete x 11,518,884 ops/sec ±3.51% (85 runs sampled)
Ending RSS memory usage: 82.695 MB
Difference: 25.020 MB

It’s pretty fast at this point with the in-memory implementation. The numbers don’t matter too much–we’ll just use them as a reference point to see how the performance of our database system evolves. This will allow us to perform optimizations where needed.

Remember, you can check out the corresponding key-value-store-simple_after branch to see the result of the changes we’ve made.

Challenge

I’ve added a challenge for you to try to complete on your own. You can find the tests for it by checking out the key-value-store-simple_after branch and opening tests/challenges/key-value-store-simple.js.

The challenge is to implement a checkAndSet() method in the key-value store. Check-and-set (also known as compare-and-swap) is an important concept in computer science. It allows atomic operations, which can provide guarantees about the order and completion of operations when multiple entities (threads, processes, etc) are attempting to access and modify the same resources. We’ll be using check-and-set in the future to implement transaction functionality.

You’ll notice there are three tests in tests/challenges/key-value-store-simple.js. I’ll briefly walk through the first two, and provide some more context on the last one.

Test 1 - happy path

The first test ensures that the simple case works – we try to modify a key’s value and succeed.

it('checkAndSet() returns true when expectedValue matches and value was set', () => {
  let newValueWasSet = keyValueStore.checkAndSet({
    key: testKey1,
    expectedValue: undefined,
    newValue: testValue1
  })
  assert.isTrue(newValueWasSet)
  assert.equal(keyValueStore.get(testKey1), testValue1)

  newValueWasSet = keyValueStore.checkAndSet({
    key: testKey1,
    expectedValue: testValue1,
    newValue: testValue2
  })
  assert.isTrue(newValueWasSet)
  assert.equal(keyValueStore.get(testKey1), testValue2)
})