memstore

A simple key-value in-memory store with built-in sharding and load-balancing

About The Project

This project is my personal project, and it does not offer security, consistency and other production essential feature. Do not use it in live environment

memstore is a simple key-value in-memory storage which uses REST API as main interface. The minimum operator of memstore is transaction and transactions are atomic and isolated (like SQL transaction). Every transaction is executed multithreaded on a copy of a shard and after successful execution of all commands - transaction is being added to the shard queue for actual apply. Right now supported operations are only GET and SET. Despite little amount of operations, store does automatic shardering and load-balancing between shards. Default number of shards if 4, but in future I will add mechanism to increase or decrease amount of shards on fly. Every operation inside of transaction is mapped to exact shard using consistent hashing. Let me explain some terms used in this project:

• Node: A minimal working unit containing storage and queue element. You can consider node as a shard (in SQL it is also called Page)
• Node Queue: A single-threaded queue mechanism which allows executing transactions 100% atomically
• Node snapshot: A very fast copy of node used to test commands before adding them to Node Queue
• Cluster: set of nodes which handles load distribution between them (in SQL it is also called Partition)

The project is in working condition, but still a lot of work is required

(back to top)

Getting Started

This is an example of how you may give instructions on setting up your project locally. To get a local copy up and running follow these simple example steps.

Prerequisites

• Install Go 1.18 (or at least 1.15)
  Go Install Guide

Installation

1. Clone the repo

   git clone https://github.com/FoxFurry/memstore

2. Install the dependencies

    $ go mod download

(back to top)

Usage

To launch the project after copying repo, use next

$ go run main.go serve --port=8000

Port flag can be omitted, default value is 8080

Documentation: https://pkg.go.dev/github.com/FoxFurry/memstore

(back to top)

API description

GET

POST /v1/execute

Request

{
  "commands": [
    {
      "cmd_type": "get",
      "key": "foo"
    }
  ]
}

Response

{
    "results": [
        "bar"
    ]
}

---

SET

POST /v1/execute

Request

{
  "commands": [
    {
      "cmd_type": "set",
      "key": "foo",
      "value": "bar"
    },
    {
      "cmd_type": "set",
      "key": "foo2",
      "value": "bar2"
    }
  ]
}

Response

{
  "results": [
    "bar",
    "bar2"
  ]
}

---

ERROR

POST /v1/execute

Request

{
  "commands": [
    {
      "cmd_type": "will_cause_error",
      "key": "any",
      "value": "literally"
    }
  ]
}

Response

{
  "error": "unknown command"
}

(back to top)

Roadmap

• Basic command execution
• Node implementation
  • Node itself
  • Node queue mechanism
  • Node copying mechanism
• Cluster implementation
  • Consistent hashing
• Basic web interface
• Add cobra CLI interface
• Add config files
• Fix SET/GET data race
• Add logging mechanism to imitate persistence
• Fix strange btree.Item is nil issue
• Add unit tests
• Improve performance
  • Under 100ns for GET
  • Under 200ns for SET
• Dynamic node number
  • Optimal node number calculator
  • Node rebalancing mechanism
• To be continued ...

(back to top)

Dependencies

• github.com/buraksezer/consistent
• github.com/cespare/xxhash
• github.com/gin-gonic/gin
• github.com/google/btree

(back to top)

License

Distributed under the MIT License. See LICENSE for more information.

(back to top)

Acknowledgments

• Table and Index Organization
• Planning and Architecture (Database Engine)

(back to top)