Build Cache from Scratch: 3. Cache core implementation

Table of Contents

wtf cache - This article is part of a series.

Part : Build Cache from Scratch: 6. observe our service

Part : Build Cache from Scratch: 5. TCP cache server

Part : Build Cache from Scratch: 4. HTTP cache server

Part : This Article

Part : Build Cache from Scratch: 2. initialize project

Part : Build Cache from Scratch: 1. introduction

Download source code:
https://github.com/challenai/wtfcache

What is a cache, how to describe a cache
#

cache is somewhere we can store data. We usually find data by its ID, or key, thus we need to store a key-value pair when we store data. At last, we have the basic requirement of removing a specific key-value pair.

As a result, or cache should look like as follows:

cache:
  - set(key, value)
  - get(key) -> value
  - delete(key)

according to our design, we get the abstract interface.

type Cache interface {
	Get(key string) ([]byte, error)
	Set(key string, value []byte) error
	Del(key string) (bool, error)
}

We design our cache abstract in the cache folder.

Implement the real internal structure: in memory
#

We find the structure of the cache looks like a hashmap,
and the hashmap provides O(1) time complexity for all our operation: get/set/delete.
Therefore, we decided to use hashmap to store our kv pairs.
Notice that our design is to store data in a hashmap,
and if there are some other considerations like performance, we can use some other data structure.
But there’s something we need to pay attention when we use hashmap,
we don’t expect our cache serve only one user at a time, it’s not good enough for current world,
so our cache should handle more than one requests simutaneously, in another world, we need a thread-safe hashmap, so our choice is sync.Map.

The core implementation is showed as bellow:

type MemCache struct {
	sync.Map
}

func (mc *MemCache) Get(k string) ([]byte, error) {
	// sync.Map.Load(k)
}

func (mc *MemCache) Set(k string, v []byte) error {
	// sync.Map.LoadOrStore(k, v)
}

func (mc *MemCache) Del(k string) (bool, error) {
	// syc.Map.LoadAndDelete(k)
}

We implement our memory cache in the mem folder.

Implement the real internal structure: disk oriented
#

to persist data to the disk, most of the time the database is the best choice,
because there are quite a lot of different types of database which provide different features currently, it’s unnecessary to build a whole new one, and the internal structure is not really easy to understand. In our case, we need a key-value based database, there are different options like LevelDB, RocksDB, Riak, Cassandra, DynamoDB, BoltDB, BadgerDB. However, the critical feature for us is a tiny high performance single node storage engine. Thus the best option should be RocksDB, we don’t need distributed feature, we don’t have really huge data for a cache application, we hope it to be real-time, and we have a golang version RocksDB alternative which provide high performance, it’s called BadgerDB, and of the most value is that this engine is written in golang, it’s extremly easy to maintain, you can find everyone can run it with go run main.go, but with RocksDB, you don’t know how to maintain them properly since they have so many dependencies which you need to install munually, adn disastrous C++ code.

The core implementation is shown as below:

type Store struct {
	db *xxDB // for example, BadgerDB, or even mysql...
}

func (s *Store) Get(k string) ([]byte, error) {
    // db.Get(k)
}

func (s *Store) Set(k string, v []byte) error {
    // db.Set(k)
}

func (s *Store) Del(k string) (bool, error) {
    // db.Delete(k)
}

We implement our persisted cache in the store folder.

Implement the real internal structure: cloud persisted
#