inmemdb

An in-memory key-value database implemented in the context of an interview.

Overview

inmemdb is a key/value store written in Go with support for transactions using the read commited isolation level.

inmemdb uses Go Modules introduced in Go 1.11 for dependency management.

Install

$ go get github.com/devodev/inmemdb

Usage (library)

Install the package

$ go get github.com/devodev/inmemdb

package main

import "github.com/devodev/inmemdb"

func main() {
    // Error handling omitted for brevity
    db := NewDatabase()
    db.CreateTransaction("tx1")
    db.PutTxn("key1", "value1", "tx1")
    db.CommitTransaction("tx1")
    value, _ := db.Get("key1")
}

Tests

Run all tests

$ go test -v

Run all tests with race condition check enabled

$ go test -v -race

Constraints

• Language: Golang
• Deadline: 48 hours from the reception of the problem statement.

Problem statement

This is a simple database problem. You'll implement an in-memory database as a key value store. The interface for this database follows.
You may modify it to match the idiomatic way to program using Go as the programming language.

Guidelines

Your solution does not need to persist data between restarts.

API Spec

The Basic API

Your API should accept the following:

• void put(String key, String value)
  • Set the variable “key” to the provided “value”
  • Throws an exception or returns an error on failure
• void put(String key, String value, String transactionId)
  • Set the variable “key” to the provided “value” within the transaction with ID “transactionId”
  • Throws an exception or returns an error on failure
• String get(String key)
  • Returns the value associated with “key”
  • Throws an exception or returns an error on failure
• String get(String key, String transactionId)
  • Returns the value associated with “key” within the transaction with ID “transactionId”
  • Throws an exception or returns an error on failure
• void delete(String key)
  • Remove the value associated with “key”
  • Throws an exception or returns an error on failure
• void delete(String key, String transactionId)
  • Remove the value associated with “key” within the transaction with ID “transactionId”
  • Throws an exception or returns an error on failure

Here is an example request sequence without transactions:

myDb.put(“example”, “foo”)
myDb.get(“example”)        // returns “foo”
myDb.delete(“example”)
myDb.get(“example”)        // returns null
myDb.delete(“example”)

Transactions

In addition to the above requests, your program should also support basic transactions by also implementing these operations:

• void createTransaction(String transactionId)
  • Starts a transaction with the specified ID. The ID must not be an active transaction ID.
  • Throws an exception or returns an error on failure
• void rollbackTransaction(String transactionId)
  • Aborts the transaction and invalidates the transaction with the specified transaction ID
  • Throws an exception or returns an error on failure
• void commitTransaction(String transactionId)
  • Commits the transaction and invalidates the ID. If there is a conflict (meaning the transaction attempts to change a value for a key that was mutated after the transaction was created), the transaction always fails with an exception or an error is returned.

Transactions should be isolated at the read committed level, as defined by this Wikipedia page.
Any put, delete, get operation that is issued without a transaction ID should commit immediately.

Here is an example request sequence:

myDb.createTransaction(“abc”)
myDb.put(“a”, “foo”, “abc”)
myDb.get(“a”, “abc”)            // returns “foo”
myDb.get(“a”)                   // returns null

myDb.createTransaction(“xyz”)

myDb.put(“a”, “bar”, “xyz”)
myDb.get(“a”, “xyz”)            // returns “bar”

myDb.commitTransaction(“xyz”)

myDb.get(“a”)                   // returns “bar”

myDb.commitTransaction(“abc”)   // failure

myDb.get(“a”);                  // returns “bar”

myDb.createTransaction(“abc”)

myDb.put(“a”, “foo”, “abc”)
myDb.get(“a”)                   // returns “bar”

myDb.rollbackTransaction(“abc”)

myDb.put(“a”, “foo”, “abc”)     // failure
myDb.get(“a”)                   // returns “bar”

myDb.createTransaction(“def”)

myDb.put(“b”, “foo”, “def”)
myDb.get(“a”, “def”)            // returns “bar”
myDb.get(“b”, “def”)            // returns “foo”

myDb.rollbackTransaction(“def”)

myDb.get(“b”)                   // returns null

Performance Considerations

• All of the put, get, and delete operations should have an expected worst-case runtime of O(log N) or better, where N is the total number of variables stored in the database.
• The vast majority of transactions will only update a small number of variables. Accordingly, your solution should be efficient about how much memory each transaction uses.