Minicache - Distributed cache implemented in Go. Like Redis but simpler.

minicache

build badge

Distributed cache implemented in Go. Like Redis but simpler. Features include:

  • Client-side consistent hashing to support fault-tolerance by minimizing the number of key re-remappings required in the event of node failure
  • Dynamic node discovery enabling arbitrary cluster sizes
  • Distributed leader election via Bully algorithm and leader heartbeat monitors which ensure no single-point of failure
  • Both HTTP/gRPC interfaces for gets/puts
  • mTLS secured communication (gRPC only for now, adding to HTTP/REST API soon)
  • Dockerfiles to support containerized deployments

Contents


Features

Thread-safe LRU cache with O(1) operations

  • Least-recently-used eviction policy with a configurable cache capacity ensures low cache-miss rate
  • Get/Put operations and eviction run all run in O(1) time
  • LRU cache implementation is made thread safe by use of Go synchronization primitives

Consistent Hashing

  • Client uses consistent hashing to uniformly distribute requests and minimize required re-mappings when servers join/leave the cluster
  • Client automatically monitors the cluster state stored on the leader node for any changes and updates its consistent hashing ring accordingly

Distributed leader election algorithm

  • Bully election algorithm used to elect a leader node for the cluster, which is in charge of monitoring the state of the nodes in the cluster to provide to clients so they can maintain a consistent hashing ring and route requests to the correct nodes
  • Follower nodes monitor heartbeat of leader and run a new election if it goes down

Dynamic node discovery

  • New nodes join the cluster when they come online by first registering themselves with the cluster, which is done by sending identifying information (hostname, port, etc.) to each of the cluster's original "genesis" nodes (i.e. nodes defined in the config file used at runtime) until one returns a successful response.
  • When an existing node receives this registration request from the new node, it will add the new node to its in-memory list of nodes and send this updated list to all other nodes.
  • The leader node monitors heartbeats of all nodes in the cluster, keeping a list of active reachable nodes in the cluster updated in real-time.
  • Clients monitor the leader's cluster config for changes and updates their consistent hashing ring accordingly. Time to update cluster state after node joins/leaves cluster is <= 1 second.

No single point of failure

  • The distributed election algorithm allows any nodes to arbitrarily join/leave cluster at any time, and there is always guaranteed to be a leader tracking the state of nodes in the cluster to provide to clients for consistent hashing.

Supports both REST API and gRPC

  • Make gets/puts with the simple familiar interfaces of HTTP/gRPC

mTLS for maximum security

  • minicache uses mutual TLS, with mutual authentication between client and server for maximum security.

Performance

1. LRU Cache implemtation ran directly by a test program: ~4.17 million puts/second

2. Distributed cache running locally with storage via gRPC calls over local network: ~17,000 puts/second

10,000 items stored in cache via gRPC calls in 0.588 seconds when running 4 cache servers on localhost with capacity of 100 items each, when all servers stay online throughout the test

$ go test -v main_test.go
	...
    main_test.go:114: Time to complete 10k puts via gRPC: 588.774872ms
    main_test.go:115: Cache misses: 0/10,000 (0.000000%)

3. Distributed cache storage running in Docker containers with storage via gRPC calls: 1150 puts/second

10,000 items stored in cache via gRPC calls in 8.69 seconds when running 4 cache servers on localhost with capacity of 100 items each, when all servers stay online throughout the test

# docker run --network minicache_default cacheclient
	...
	cache_client_docker_test.go:95: Time to complete 10k puts via REST API: 8.6985474s

Test environment:

  • 2013 MacBook Pro
  • Processor: 2.4 GHz Intel Core i5
  • Memory: 8 GB 1600 MHz DDR3

Testing

1. Unit tests

  • LRU Cache implementation has exhaustive unit tests for correctness in all possible scenarios (see lru_cache_test.go)
  • Run the unit tests with the command go test -v ./lru_cache
  • Consistent hashing ring contains exhaustive unit tests for various scenarios (see ring_test.go)
  • Run these unit tests with the command go test -v ./ring

2. Integration tests

Run the integration tests with the command go test -v main_test.go, which performs the following steps:

  1. Spins up multiple cache server instances locally on different ports (see nodes-local.json config file)
  2. Creates cache client
  3. Runs 10 goroutines which each send 1000 requests to put items in the distributed cache via REST API endpoint
  4. Runs 10 goroutines which each send 1000 requests to put items in the distributed cache via gRPC calls
  5. After each test, displays % of cache misses (which in this case, is when the client is simply unable to store an item in the distributed cache)

3. Fault-tolerance testing

A useful test is to to manually stop/restart arbitrary nodes in the cluster and observe the test log output to see the consistent hashing ring update in real time.

Example of stopping and restarting cacheserver1 while integration tests are running:

2022/05/15 02:23:35 cluster config: [id:"node2" host:"cacheserver2" rest_port:8080 grpc_port:5005 id:"epQKE" host:"cacheserver3" rest_port:8080 grpc_port:5005 id:"node0" host:"cacheserver0" rest_port:8080 grpc_port:5005]
...
2022/05/15 02:23:35 Removing node node1 from ring
...
2022/05/15 02:23:36 cluster config: [id:"epQKE" host:"cacheserver3" rest_port:8080 grpc_port:5005 id:"node0" host:"cacheserver0" rest_port:8080 grpc_port:5005 id:"node2" host:"cacheserver2" rest_port:8080 grpc_port:5005]
...

2022/05/15 02:23:40 Adding node node1 to ring
...
2022/05/15 02:23:41 cluster config: [id:"node2" host:"cacheserver2" rest_port:8080 grpc_port:5005 id:"epQKE" host:"cacheserver3" rest_port:8080 grpc_port:5005 id:"node0" host:"cacheserver0" rest_port:8080 grpc_port:5005 id:"node1" host:"cacheserver1" rest_port:8080 grpc_port:5005]

Set Up and Usage

1. Define initial nodes

You will need to define 1 or more initial "genesis" nodes in a JSON config file (see nodes-local.json or nodes-docker.json for working examples).

These genesis nodes are the original nodes of the cluster, which any new nodes created later on will attempt to contact in order to dynamically register themselves with the cluster. As long as at least 1 of these initial nodes is online, any arbitrary number of new nodes can be spun up (e.g. launching more cache server containers from an image) without defining them in a config file, rebuilding the image etc.

Therefore it is recommended to define at least 3 initial nodes to support fault-tolerance to a reasonable level.

2. Generate TLS certificates

Before using minicache you will need to generate TLS certificates by performing the following steps:

  • Update config files certs/client-ext.cnf and certs/server-ext.cnf to include any hostnames and/or IPs of any servers you plan on running. If you plan on using Docker containers, the DNS hostnames should match those of the docker containers defined in docker-compose.yml. By default, the following hostnames and IPs are defined in the config files (note the hostnames match those defined in docker-compose.yml):
subjectAltName = DNS:localhost,DNS:cacheserver0,DNS:cacheserver1,DNS:cacheserver2,DNS:cacheserver3,IP:0.0.0.0,IP:127.0.0.1
  • Run ./gen.sh which will generate the TLS certificates and store them in the appropriate location (/certs).

3. Run cache servers and clients by following any of the examples below


Examples

Example 1: Run Distributed Cache Using Docker Containers

NOTE: Make sure you've generated TLS certificates by following the steps here

  1. Run docker-compose build from the project root directory to build the Docker images.

  2. Run docker-compose up to spin up all of the containers defined in the docker-compose.yml file. By default the config file defines 4 cache server instances, 3 of which are the initial nodes defined in the configs/nodes-docker.json config file, and 1 of which is an extra server node which dynamically adds itself to the cluster, in order to demonstrate this functionality.

  3. Run docker build -t cacheclient -f Dockerfile.client . from the project root directory to build a Docker image for the client.

  4. Run docker run --network minicache_default cacheclient to run the client in a docker container connected t to the docker compose network the servers are running on. By default, the Dockerfile simply builds the client and runs the integration tests described above, although you can change it to do whatever you want.

PRO TIP: a useful test is to to manually stop/restart arbitrary nodes in the cluster and observe the test log output to see the consistent hashing ring update in real time.

Example 2: Starting All Cache Servers Defined in Config File

In the example below:

  • RELATIVE_CERT_DIR is the directory containing TLS certificates you generated here
  • RELATIVE_CONFIG_PATH is the path to the JSON config file containing the initial node information, discussed here
	// start servers
	capacity := 100
	verbose := false
	abs_cert_dir, _ := filepath.Abs(RELATIVE_CERT_DIR)
	abs_config_path, _ := filepath.Abs(RELATIVE_CONFIG_PATH)

	components := server.CreateAndRunAllFromConfig(capacity, abs_config_path, verbose)
	
	...

	// cleanup
	for _, srv_comps := range components {
		srv_comps.GrpcServer.Stop()

	    ctx, cancel := context.WithTimeout(context.Background(), 3*time.Second)
	    defer cancel()

	    if err := srv_comps.HttpServer.Shutdown(ctx); err != nil {
	        t.Logf("Http server shutdown error: %s", err)
	    }
	}

Example 3: Starting a Single Cache Server

func main() {
	// parse arguments
	grpc_port := flag.Int("grpc-port", 5005, "port number for gRPC server to listen on")
	capacity := flag.Int("capacity", 2, "capacity of LRU cache")
	verbose := flag.Bool("verbose", false, "log events to terminal")
	config_file := flag.String("config", "", "filename of JSON config file with node info")
	rest_port := flag.Int("rest-port", 8080, "enable REST API for client requests, instead of just gRPC")

	flag.Parse()

	// set up listener TCP connectiion
	listener, err := net.Listen("tcp", fmt.Sprintf(":%d", *grpc_port))
	if err != nil {
		panic(err)
	}

	// get new grpc id server
	grpc_server, cache_server := server.NewCacheServer(*capacity, *config_file, *verbose, server.DYNAMIC)

	// run gRPC server
	log.Printf("Running gRPC server on port %d...", *grpc_port)
	go grpc_server.Serve(listener)

	// register node with cluster
	cache_server.RegisterNodeInternal()

	// run initial election
	cache_server.RunElection()

	// start leader heartbeat monitor
	go cache_server.StartLeaderHeartbeatMonitor()

	// run HTTP server
	log.Printf("Running REST API server on port %d...", *rest_port)
	http_server := cache_server.RunAndReturnHttpServer(*rest_port)

	// set up shutdown handler and block until sigint or sigterm received
	c := make(chan os.Signal, 1)
	signal.Notify(c, os.Interrupt, syscall.SIGTERM, syscall.SIGINT)
	go func() {
		<-c

		log.Printf("Shutting down gRPC server...")
		grpc_server.Stop()

		log.Printf("Shutting down HTTP server...")
		ctx, cancel := context.WithTimeout(context.Background(), 3*time.Second)
		defer cancel()

		if err := http_server.Shutdown(ctx); err != nil {
			log.Printf("Http server shutdown error: %s", err)
		}
		os.Exit(0)
	}()

	// block indefinitely
	select {}
}

Example 4: Creating and Using a Cache Client

NOTE: Make sure you've generated TLS certificates by following the steps here

In the example below:

  • abs_cert_dir is the directory containing TLS certificates you generated here
  • abs_config_path is the path to the JSON config file containing the initial node information, discussed here
	// start client
	c := cache_client.NewClientWrapper(abs_cert_dir, abs_config_path)
	c.StartClusterConfigWatcher()
	...
	c.Put(key, value)
	...
	val := c.Get(key)

To Do

  • TLS for REST API
  • Improve performance of REST API
  • Improve code quality and project organization
  • Documentation
Comments
  • TLS support for REST API

    TLS support for REST API

    Currently gRPC supports TLS but the HTTP (Gin REST API endpoints) do not use TLS.

    The REST API endpoints should support TLS as well.

    Relevant section of code here

  • Make using TLS optional

    Make using TLS optional

    Currently using TLS is required - if the TLS certificates do not exist in the certs/ directory, or if the node's current hostname/IP is not listed in the TLS certificate SANs (subject alternate names), then the connection will fail at the TLS step.

    Using TLS should be optional, perhaps with a command line flag when launching the server, or as a value in a config file.

  • Use zap logger on client side instead of native log package

    Use zap logger on client side instead of native log package

    Logging should be handled consistently throughout the project. Server side logging is handled by Zap logger so the client should as well, instead of using the native log package.

  • Optionally write logs to file or stdout

    Optionally write logs to file or stdout

    Right now logging just goes to stdout, via the zap logger and native log package. This should be more flexible and allow logging to files instead as well.

  • Find a mistake in server/election.go

    Find a mistake in server/election.go

    Hi, I think there is a mistake in server/election.go#L235

    should be

    	if !ok {
    		s.logger.Infof("leader %s does not exist", s.leaderID)
    		return false                   <--- here
    	}
    

    am I right?

gdcache is a pure non-intrusive distributed cache library implemented by golang
gdcache is a pure non-intrusive distributed cache library implemented by golang

gdcache is a pure non-intrusive distributed cache library implemented by golang, you can use it to implement your own distributed cache

Sep 26, 2022
Cache library for golang. It supports expirable Cache, LFU, LRU and ARC.
Cache library for golang. It supports expirable Cache, LFU, LRU and ARC.

GCache Cache library for golang. It supports expirable Cache, LFU, LRU and ARC. Features Supports expirable Cache, LFU, LRU and ARC. Goroutine safe. S

Dec 30, 2022
Dec 28, 2022
Package cache is a middleware that provides the cache management for Flamego.

cache Package cache is a middleware that provides the cache management for Flamego. Installation The minimum requirement of Go is 1.16. go get github.

Nov 9, 2022
A mem cache base on other populator cache, add following feacture

memcache a mem cache base on other populator cache, add following feacture add lazy load(using expired data, and load it asynchronous) add singlefligh

Oct 28, 2021
Cache - A simple cache implementation

Cache A simple cache implementation LRU Cache An in memory cache implementation

Jan 25, 2022
Gin-cache - Gin cache middleware with golang

Gin-cache - Gin cache middleware with golang

Nov 28, 2022
🧩 Redify is the optimized key-value proxy for quick access and cache of any other database throught Redis and/or HTTP protocol.

Redify (Any database as redis) License Apache 2.0 Redify is the optimized key-value proxy for quick access and cache of any other database throught Re

Sep 25, 2022
POC de caching en Go en utilisant go-redis/cache

Test-web POC de caching en Go en utilisant go-redis/cache, cette lib permet d'avoir un cache local et un cache redis (appel cache local puis cache red

Nov 19, 2021
Achieve Cache GO Like GroupCache、MemCache

Cache 分布式缓存 Achieve Cache GO Like GroupCache、MemCache 1.LRU(Least Recently Used) 实现LRU淘汰算法两个核心数据结构 1.字典(map),存储键(string)与值(list.Element链表节点)的关系。 2.双向链

Feb 25, 2022
LevelDB style LRU cache for Go, support non GC object.

Go语言QQ群: 102319854, 1055927514 凹语言(凹读音“Wa”)(The Wa Programming Language): https://github.com/wa-lang/wa LRU Cache Install go get github.com/chai2010/c

Jul 5, 2020
groupcache is a caching and cache-filling library, intended as a replacement for memcached in many cases.

groupcache Summary groupcache is a distributed caching and cache-filling library, intended as a replacement for a pool of memcached nodes in many case

Dec 31, 2022
☔️ A complete Go cache library that brings you multiple ways of managing your caches
☔️ A complete Go cache library that brings you multiple ways of managing your caches

Gocache Guess what is Gocache? a Go cache library. This is an extendable cache library that brings you a lot of features for caching data. Overview He

Jan 1, 2023
fastcache - fast thread-safe inmemory cache for big number of entries in Go

Fast thread-safe inmemory cache for big number of entries in Go. Minimizes GC overhead

Dec 27, 2022
An in-memory cache library for golang. It supports multiple eviction policies: LRU, LFU, ARC

GCache Cache library for golang. It supports expirable Cache, LFU, LRU and ARC. Features Supports expirable Cache, LFU, LRU and ARC. Goroutine safe. S

May 31, 2021
Efficient cache for gigabytes of data written in Go.

BigCache Fast, concurrent, evicting in-memory cache written to keep big number of entries without impact on performance. BigCache keeps entries on hea

Dec 30, 2022
An in-memory key:value store/cache (similar to Memcached) library for Go, suitable for single-machine applications.

go-cache go-cache is an in-memory key:value store/cache similar to memcached that is suitable for applications running on a single machine. Its major

Dec 29, 2022
Primer proyecto OSS en comunidad sobre cache en memoria.

GoKey ?? Concepto del proyecto: Sistema de base de datos clave valor, distribuido. En forma de cache en memoria. Especificaciones: Para conjuntar inf

Aug 6, 2022