Help us shape the future of Go! Take the 2026 Go Developer Survey

olric

package module
v0.0.0-...-867e715 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Nov 26, 2018 License: Apache-2.0 Imports: 29 Imported by: 0

README

Olric

GoDoc Coverage Status Build Status Go Report Card License

Distributed and in-memory key/value database that persists on disk. It can be used both as an embedded Go library and as a language-independent service. Built with Go.

WIP

This project is a work in progress. The implementation is incomplete. The documentation may be inaccurate.

Table of Contents

Features

  • Designed to share some transient, approximate, fast-changing data between servers,
  • Accepts arbitrary types as value,
  • In-memory with optional persistence,
  • Implements a fast and simple binary protocol,
  • Embeddable but can be used as a language-independent service with olricd,
  • Stores values in off-heap memory, which is memory within the runtime that is not subject to Go garbage collection.
  • Supports atomic operations,
  • Provides a single-node lock implementation which can be used for non-critical purposes,
  • Time-To-Live(TTL) eviction policy,
  • Highly available,
  • Horizontally scalable,
  • Provides best-effort consistency guarantees without being a complete CP solution,
  • Distributes load fairly among cluster members with a consistent hash function,
  • Supports replication by default(with sync and async options),
  • Thread-safe by default,
  • Provides a command-line-interface to access the cluster directly from the terminal,
  • Very simple package API,
  • Offers a built-in Go client,
  • Gob, JSON and MessagePack are supportted by default as serialization format,
  • Simplicity as a key concept with a small set of features.

Planned Features

  • Anti-entropy system to repair inconsistencies in DMaps,
  • LRU eviction policy,
  • Publish/Subscribe for messaging,
  • Eviction listeners by using Pub/Sub,
  • Memcached interface,
  • Python client.

We may implement different data structures such as list, queue or bitmap in Olric. It's highly depends on attention of the Golang community.

Installing

With a correctly configured Golang environment:

go get -u github.com/buraksezer/olric

Usage

Olric is designed to work efficiently with the minimum amount of configuration. So the default configuration should be enough for experimenting:

db, err := olric.New(nil)

This creates an Olric object without running any server at background. In order to run Olric, you need to call Start method.

err := db.Start()

When you call Start method, your process joins the cluster and will be responsible for some parts of the data. This call blocks indefinitely. So you may need to run it in a goroutine. Of course, this is just a single-node instance, because you didn't give any configuration.

Create a DMap object to access the cluster:

dm := db.NewDMap("my-dmap")

DMap object has Put, PutEx, Get, Delete, LockWithTimeout, Unlock and Destroy methods to access and modify data in Olric. We may add more methods for finer control but first, I'm willing to stabilize this set of features.

When you want to leave the cluster, just need to call Shutdown method:

err := db.Shutdown(context.Background())

This will stop background tasks and servers, synchronizes in-memory data to the disk if persistence is enabled. Finally purges in-memory data and quits.

Put

Put sets the value for the given key. It overwrites any previous value for that key and it's thread-safe.

err := dm.Put("my-key", "my-value")

The key has to be string. Value type is arbitrary. It is safe to modify the contents of the arguments after Put returns but not before.

PutEx

Put sets the value for the given key with TTL. It overwrites any previous value for that key. It's thread-safe.

err := dm.PutEx("my-key", "my-value", time.Second)

The key has to be string. Value type is arbitrary. It is safe to modify the contents of the arguments after PutEx returns but not before.

Get

Get gets the value for the given key. It returns ErrKeyNotFound if the DB does not contains the key. It's thread-safe.

value, err := dm.Get("my-key")

It is safe to modify the contents of the returned value. It is safe to modify the contents of the argument after Get returns.

Delete

Delete deletes the value for the given key. Delete will not return error if key doesn't exist. It's thread-safe.

err := dm.Delete("my-key")

It is safe to modify the contents of the argument after Delete returns.

LockWithTimeout

LockWithTimeout sets a lock for the given key. If the lock is still unreleased the end of given period of time, it automatically releases the lock. Acquired lock is only for the key in this map. Please note that, before setting a lock for a key, you should set the key with Put method. Otherwise it returns ErrKeyNotFound error.

err := dm.LockWithTimeout("my-key", time.Second)

It returns immediately if it acquires the lock for the given key. Otherwise, it waits until timeout. The timeout is determined by http.Client which can be configured via Config structure.

You should know that the locks are approximate, and only to be used for non-critical purposes.

Please take a look at Lock Implementation section for implementation details.

Unlock

Unlock releases an acquired lock for the given key. It returns ErrNoSuchLock if there is no lock for the given key.

err := dm.Unlock("my-key")
Destroy

Destroy flushes the given DMap on the cluster. You should know that there is no global lock on DMaps. So if you call Put/PutEx and Destroy methods concurrently on the cluster, Put/PutEx calls may set new values to the DMap.

err := dm.Destroy()

Configuration

memberlist configuration can be tricky and and the default configuration set should be tuned for your environment. A detailed deployment and configuration guide will be prepared before stable release.

Please take a look at Config section at godoc.org

Here is a sample configuration for a cluster with two hosts:

m1, _ := olric.NewMemberlistConfig("local")
m1.BindAddr = "127.0.0.1"
m1.BindPort = 5555
c1 := &olric.Config{
	Name:          "127.0.0.1:3535", // Unique in the cluster and used by TCP server.
	Peers:         []string{"127.0.0.1:5656"},
	MemberlistCfg: m1,
}

m2, _ := olric.NewMemberlistConfig("local")
m2.BindAddr = "127.0.0.1"
m2.BindPort = 5656
c2 := &olric.Config{
	Name:          "127.0.0.1:3636",
	Peers:         []string{"127.0.0.1:5555"},
	MemberlistCfg: m2,
}

db1, err := olric.New(c1)
// Check error

db2, err := olric.New(c2)
// Check error

// Call Start method for db1 and db2 in a seperate goroutine.

Architecture

Overview

Olric uses:

Olric distributes data among partitions. Every partition is owned by a cluster member and may has one or more backup for redundancy. When you read or write a map entry, you transparently talk to the partition owner. Each request hits the most up-to-date version of a particular data entry in a stable cluster.

In order to find the partition which the key belongs to, Olric hashes the key and mod it with the number of partitions:

partID = MOD(hash result, partition count)

The partitions are distributed among cluster members by using a consistent hashing algorithm. In order to get details, please see buraksezer/consistent. The backup owners are also calculated by the same package.

When a new cluster is created, one of the instances elected as the cluster coordinator. It manages the partition table:

  • When a node joins or leaves, it distributes the partitions and their backups among the members again,
  • Removes empty owners from the partition owners list,
  • Pushes the new partition table to all the members,
  • Pushes the the partition table to the cluster periodically.

Members propagates their birthdate(Unix timestamp in nanoseconds) to the cluster. The coordinator is the oldest member in the cluster. If the coordinator leaves the cluster, the second oldest member elected as the coordinator.

Olric has a component called fsck which is responsible for keeping underlying data structures consistent:

  • Works on every node,
  • When a node joins or leaves, the cluster coordinator pushes the new partition table. Then, fsck goroutine runs immediately and moves the partitions and backups to their new hosts,
  • Merges fragmented partitions,
  • Runs at background periodically and repairs partitions i.e. creates new backups if required.

Partitions have a concept called owners list. When a node joins or leaves the cluster, a new primary owner may be assigned by the coordinator. At any time, a partition may has one or more partition owner. If a partition has two or more owner, this is called fragmented partition. The last added owner is called primary owner. Write operation is only done by the primary owner. The previous owners are only used for read and delete.

When you read a key, the primary owner tries to find the key on itself, first. Then, queries the previous owners and backups, respectively. Delete operation works with the same way.

The data(distributed map objects) in the fragmented partition is moved slowly to the primary owner by fsck goroutine. Until the move is done, the data remains available on the previous owners. DMap methods use this list to query data on the cluster.

Please note that, multiple partition owner is an undesirable situation and the fsck component is designed to fix that in a short time.

When you call Start method of Olric, it starts background services with a TCP server.

Consistency and Replication Model

Olric is an AP product, which employs the combination of primary-copy and optimistic replication techniques. With optimistic replication, when the partition owner receives a write or delete operation for a key, applies it locally, and propagates it to backup owners.

This technique enables Olric clusters to offer high throughput. However, due to temporary situations in the system, such as network failure, backup owners can miss some updates and diverge from the primary owner. If a partition owner crashes while there is an inconsistency between itself and the backups, strong consistency of the data can be lost.

Two types of backup replication are available: sync and async. Both types are still implementations of the optimistic replication model.

  • sync: Blocks until write/delete operation is applied by backup owners.
  • async: Just fire & forget.

An anti-entropy system has been planned to deal with inconsistencies in DMaps.

Eviction

Olric only implements TTL eviction policy. It shares the same algorithm with Redis:

Periodically Redis tests a few keys at random among keys with an expire set. All the keys that are already expired are deleted from the keyspace.

Specifically this is what Redis does 10 times per second:

  • Test 20 random keys from the set of keys with an associated expire.
  • Delete all the keys found expired.
  • If more than 25% of keys were expired, start again from step 1.

This is a trivial probabilistic algorithm, basically the assumption is that our sample is representative of the whole key space, and we continue to expire until the percentage of keys that are likely to be expired is under 25%

When a client tries to access a key, Olric returns ErrKeyNotFound if the key is found to be timed out. A background task evicts keys with the algorithm described above.

LRU eviction policy implementation has been planned.

Lock Implementation

DMap implementation is already thread-safe to meet your thread safety requirements. When you want to have more control on the concurrency, you can use LockWithTimeout method. It's slightly modified version of Moby's(formerly Docker) locker package. It utilizes sync.Mutex. Take a look at the code for details.

Please note that the lock implementation has no backup. So if the node, which the lock belongs to, crashed, the acquired lock is dropped.

I recommend the lock implementation to be used for efficiency purposes in general, instead of correctness.

Client

Olric is mainly designed to be used as an embedded DHT. So if you are running long-lived servers, Olric is pretty suitable to share some transient, approximate, fast-changing data between them. What if you want to access the cluster in a short-lived process? Fortunately, Olric has an external API which can be used to access the cluster within any environment. It will be documented soon.

A Golang client is already prepared to access and modify DMaps from outside. Here is the documentation.

Sample Code

The following snipped can be run on your computer directly. It's a single-node setup, of course:

package main

import (
	"context"
	"fmt"
	"log"
	"reflect"
	"strconv"
	"time"

	"github.com/buraksezer/olric"
)

type customType struct {
	Field1 string
	Field2 uint64
}

func main() {
	// This creates a single-node Olric cluster. It's good enough for experimenting.
	db, err := olric.New(nil)
	if err != nil {
		log.Fatalf("Failed to create Olric object: %v", err)
	}

	go func() {
		// Call Start at background. It's a blocker call.
		err = db.Start()
		if err != nil {
			log.Fatalf("Failed to call Start: %v", err)
		}
	}()

	// Put 10 items into the DMap object.
	dm := db.NewDMap("bucket-of-arbitrary-items")
	for i := 0; i < 10; i++ {
		c := customType{}
		c.Field1 = fmt.Sprintf("num: %d", i)
		c.Field2 = uint64(i)
		err = dm.Put(strconv.Itoa(i), c)
		if err != nil {
			log.Printf("Put call failed: %v", err)
		}
	}

	// Read them again.
	for i := 0; i < 10; i++ {
		val, err := dm.Get(strconv.Itoa(i))
		if err != nil {
			log.Printf("Get call failed: %v", err)
		}
		fmt.Println(val, reflect.TypeOf(val))
	}

	// Don't forget the call Shutdown when you want to leave the cluster.
	ctx, _ := context.WithTimeout(context.Background(), 10*time.Second)
	err = db.Shutdown(ctx)
	if err != nil {
		log.Printf("Failed to shutdown Olric: %v", err)
	}
}

To-Do

  • Document the code,
  • Some parts of FSCK implementation is missing: It currently doesn't repair failed backups,
  • Design & write benchmarks,
  • Document the binary protocol,
  • Build a website for Olric and create extensive documentation.

Caveats

Olric uses Golang's built-in map. It's known that the built-in map has problems with the GC:

Olric already uses map[uint64][]byte as underlying data structure. It should work fine for most of the cases.

I have implemented an off-heap hash table with mmap. We may add an option to use it in the future but my implementation needs too much effort to be used in production.

Contributions

Please don't hesitate to fork the project and send a pull request or just e-mail me to ask questions and share ideas.

License

The Apache License, Version 2.0 - see LICENSE for more details.

About the name

The inner voice of Turgut Özben who is the main character of Oğuz Atay's masterpiece -The Disconnected-.

Documentation

Overview

Package olric provides distributed, in-memory and embeddable key/value store, used as a database and cache.

Index

Constants

View Source 
const (
	// SyncBackupMode enables sync backup mode which means that the caller is blocked
	// until write/delete operation is applied by backup owners.
	// The default mode is SyncBackupMode
	SyncBackupMode = 0

	// AsyncBackupMode enables async backup mode which means that write/delete operations
	// are done in a background task.
	AsyncBackupMode = 1
)
View Source 
const (
	// DefaultPartitionCount determines default partition count in the cluster.
	DefaultPartitionCount = 271

	// DefaultLoadFactor is used by the consistent hashing function. Keep it small.
	DefaultLoadFactor = 1.25

	// DefaultLogLevel determines the log level without extra configuration. It's DEBUG.
	DefaultLogLevel = "DEBUG"
)
View Source 
const ReleaseVersion string = "0.1.0"

ReleaseVersion is the current stable version of Olric

Variables

View Source 
var (
	// ErrKeyNotFound is returned when a key could not be found.
	ErrKeyNotFound = errors.New("key not found")

	// ErrOperationTimeout is returned when an operation times out.
	ErrOperationTimeout = errors.New("operation timeout")

	// ErrInternalServerError means that something unintentionally went wrong while processing the request.
	ErrInternalServerError = errors.New("internal server error")
)
View Source 
var ErrNoSuchLock = errors.New("no such lock")

ErrNoSuchLock is returned when the requested lock does not exist

Functions

func NewMemberlistConfig 

func NewMemberlistConfig(env string) (*memberlist.Config, error)

NewMemberlistConfig returns a new memberlist.Config from vendored version of that package. It takes an env parameter: local, lan and wan.

local: DefaultLocalConfig works like DefaultConfig, however it returns a configuration that is optimized for a local loopback environments. The default configuration is still very conservative and errs on the side of caution.

lan: DefaultLANConfig returns a sane set of configurations for Memberlist. It uses the hostname as the node name, and otherwise sets very conservative values that are sane for most LAN environments. The default configuration errs on the side of caution, choosing values that are optimized for higher convergence at the cost of higher bandwidth usage. Regardless, these values are a good starting point when getting started with memberlist.

wan: DefaultWANConfig works like DefaultConfig, however it returns a configuration that is optimized for most WAN environments. The default configuration is still very conservative and errs on the side of caution.

Types

type Config 

type Config struct {
	LogLevel string
	// Name of this node in the cluster. This must be unique in the cluster. If this is not set,
	// Olric will set it to the hostname of the running machine. Example: node1.my-cluster.net
	//
	// Name is also used by the TCP server as Addr. It should be an IP adress or domain name of the server.
	Name string

	OperationMode OpMode

	KeepAlivePeriod time.Duration

	DialTimeout time.Duration

	// The list of host:port which are used by memberlist for discovery. Don't confuse it with Name.
	Peers []string

	// PartitionCount is 271, by default.
	PartitionCount uint64

	// BackupCount is 0, by default.
	BackupCount int

	// Default value is SyncBackupMode.
	BackupMode int

	// LoadFactor is used by consistent hashing function. It determines the maximum load
	// for a server in the cluster. Keep it small.
	LoadFactor float64

	MaxValueSize int

	// Default hasher is github.com/cespare/xxhash. You may want to use a different
	// hasher which implements Hasher interface.
	Hasher Hasher

	// Default Serializer implementation uses gob for encoding/decoding.
	Serializer Serializer

	// TLS certificate file for TCP server. If it's empty, TLS is disabled.
	CertFile string

	// TLS key file for TCP server. If it's empty, TLS is disabled.
	KeyFile string

	// LogOutput is the writer where logs should be sent. If this is not
	// set, logging will go to stderr by default. You cannot specify both LogOutput
	// and Logger at the same time.
	LogOutput io.Writer

	// Logger is a custom logger which you provide. If Logger is set, it will use
	// this for the internal logger. If Logger is not set, it will fall back to the
	// behavior for using LogOutput. You cannot specify both LogOutput and Logger
	// at the same time.
	Logger *log.Logger

	SnapshotInterval time.Duration
	GCInterval       time.Duration
	GCDiscardRatio   float64
	BadgerOptions    *badger.Options

	// MemberlistConfig is the memberlist configuration that Olric will
	// use to do the underlying membership management and gossip. Some
	// fields in the MemberlistConfig will be overwritten by Olric no
	// matter what:
	//
	//   * Name - This will always be set to the same as the NodeName
	//     in this configuration.
	//
	//   * Events - Olric uses a custom event delegate.
	//
	//   * Delegate - Olric uses a custom delegate.
	//
	// You have to use NewMemberlistConfig to create a new one.
	// Then, you may need to modify it to tune for your environment.
	MemberlistConfig *memberlist.Config
}

Config is the configuration for creating a Olric instance.

type DMap 

type DMap struct {
	// contains filtered or unexported fields
}

DMap represents a distributed map object.

func (*DMap) Decr 

func (dm *DMap) Decr(key string, delta int) (int, error)

Decr atomically decrements key by delta. The return value is the new value after being decremented or an error.

func (*DMap) Delete 

func (dm *DMap) Delete(key string) error

Delete deletes the value for the given key. Delete will not return error if key doesn't exist. It's thread-safe. It is safe to modify the contents of the argument after Delete returns.

func (*DMap) Destroy 

func (dm *DMap) Destroy() error

Destroy flushes the given DMap on the cluster. You should know that there is no global lock on DMaps. So if you call Put/PutEx and Destroy methods concurrently on the cluster, Put/PutEx calls may set new values to the DMap.

func (*DMap) Get 

func (dm *DMap) Get(key string) (interface{}, error)

Get gets the value for the given key. It returns ErrKeyNotFound if the DB does not contains the key. It's thread-safe. It is safe to modify the contents of the returned value. It is safe to modify the contents of the argument after Get returns.

func (*DMap) GetPut 

func (dm *DMap) GetPut(key string, value interface{}) (interface{}, error)

GetPut atomically sets key to value and returns the old value stored at key.

func (*DMap) Incr 

func (dm *DMap) Incr(key string, delta int) (int, error)

Incr atomically increments key by delta. The return value is the new value after being incremented or an error.

func (*DMap) LockWithTimeout 

func (dm *DMap) LockWithTimeout(key string, timeout time.Duration) error

LockWithTimeout sets a lock for the given key. If the lock is still unreleased the end of given period of time, it automatically releases the lock. Acquired lock is only for the key in this map.

It returns immediately if it acquires the lock for the given key. Otherwise, it waits until timeout. The timeout is determined by http.Client which can be configured via Config structure.

You should know that the locks are approximate, and only to be used for non-critical purposes.

func (*DMap) Put 

func (dm *DMap) Put(key string, value interface{}) error

Put sets the value for the given key. It overwrites any previous value for that key and it's thread-safe. The key has to be string. Value type is arbitrary. It is safe to modify the contents of the arguments after Put returns but not before.

func (*DMap) PutEx 

func (dm *DMap) PutEx(key string, value interface{}, timeout time.Duration) error

PutEx sets the value for the given key with TTL. It overwrites any previous value for that key. It's thread-safe. The key has to be string. Value type is arbitrary. It is safe to modify the contents of the arguments after Put returns but not before.

func (*DMap) Unlock 

func (dm *DMap) Unlock(key string) error

Unlock releases an acquired lock for the given key. It returns ErrNoSuchLock if there is no lock for the given key.

type Hasher 

type Hasher interface {
	Sum64([]byte) uint64
}

Hasher is responsible for generating unsigned, 64 bit hash of provided byte slice. Hasher should minimize collisions (generating same hash for different byte slice) and while performance is also important fast functions are preferable (i.e. you can use FarmHash family).

func NewDefaultHasher 

func NewDefaultHasher() Hasher

NewDefaultHasher returns an instance of xxhash package which implements the 64-bit variant of xxHash (XXH64) as described at http://cyan4973.github.io/xxHash/.

type NodeMetadata 

type NodeMetadata struct {
	Birthdate int64
}

TODO: NodeMetadata will be removed.

type Olric 

type Olric struct {
	// contains filtered or unexported fields
}

Olric implements a distributed, in-memory and embeddable key/value store.

func New 

func New(c *Config) (*Olric, error)

New creates a new Olric object, otherwise returns an error.

func (*Olric) NewDMap 

func (db *Olric) NewDMap(name string) *DMap

NewDMap creates an returns a new DMap object.

func (*Olric) Shutdown 

func (db *Olric) Shutdown(ctx context.Context) error

Shutdown stops background servers and leaves the cluster.

func (*Olric) Start 

func (db *Olric) Start() error

Start starts background servers and joins the cluster.

type OpMode 

type OpMode uint8

OpMode is the type for operation modes. 

const (
	// OpInMemory indicates pure in-memory operation mode. In-memory data structures
	// are not durable at that mode.
	OpInMemory OpMode = OpMode(iota)

	// OpInMemoryWithSnapshot indicates in-memory operation mode with snapshot support.
	// The in-memory data is durable at that mode.
	OpInMemoryWithSnapshot
)

type Serializer 

type Serializer interface {
	// Marshal encodes v and returns a byte slice and possible error.
	Marshal(v interface{}) ([]byte, error)

	// Unmarshal decodes the encoded data and stores the result in the value pointed to by v.
	Unmarshal(data []byte, v interface{}) error
}

Serializer interface responsible for encoding/decoding values to transmit over network between Olric nodes.

func NewGobSerializer 

func NewGobSerializer() Serializer

NewGobSerializer returns a gob serializer. It's the default one.

func NewJSONSerializer 

func NewJSONSerializer() Serializer

NewJSONSerializer returns a json serializer.

func NewMsgpackSerializer 

func NewMsgpackSerializer() Serializer

NewMsgpackSerializer returns a msgpack serializer.

Source Files

View all Source files

Directories

Path Synopsis
Package client implements a Golang client to access an Olric cluster from outside.
 Package client implements a Golang client to access an Olric cluster from outside.
cmd
olric-cli command
olric-cli/cli
Package cli is the Olric command line interface, a simple program that allows to send commands to Olric, and read the replies sent by the server, directly from the terminal.
 Package cli is the Olric command line interface, a simple program that allows to send commands to Olric, and read the replies sent by the server, directly from the terminal.
olricd command
olricd/server
Package server provides a standalone server implementation for Olric
 Package server provides a standalone server implementation for Olric
internal
bufpool
protocol
snapshot
storage
Package storage implements an off-heap data store which is memory within the runtime that is not subject to Go garbage collection.
 Package storage implements an off-heap data store which is memory within the runtime that is not subject to Go garbage collection.
transport

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.