Fast Raft framework using the Redis protocol for Go

Overview

This project has been archived. Please check out Uhaha for a fitter, happier, more productive Raft framework.

FINN

Go Report Card GoDoc

Finn is a fast and simple framework for building Raft implementations in Go. It uses Redcon for the network transport and Hashicorp Raft. There is also the option to use LevelDB, BoltDB or FastLog for log persistence.

Features

Getting Started

Installing

To start using Finn, install Go and run go get:

$ go get -u github.com/tidwall/finn

This will retrieve the library.

Example

Here's an example of a Redis clone that accepts the GET, SET, DEL, and KEYS commands.

You can run a full-featured version of this example from a terminal:

go run example/clone.go
package main

import (
	"encoding/json"
	"io"
	"io/ioutil"
	"log"
	"sort"
	"strings"
	"sync"

	"github.com/tidwall/finn"
	"github.com/tidwall/match"
	"github.com/tidwall/redcon"
)

func main() {
	n, err := finn.Open("data", ":7481", "", NewClone(), nil)
	if err != nil {
		log.Fatal(err)
	}
	defer n.Close()
	select {}
}

type Clone struct {
	mu   sync.RWMutex
	keys map[string][]byte
}

func NewClone() *Clone {
	return &Clone{keys: make(map[string][]byte)}
}

func (kvm *Clone) Command(m finn.Applier, conn redcon.Conn, cmd redcon.Command) (interface{}, error) {
	switch strings.ToLower(string(cmd.Args[0])) {
	default:
		return nil, finn.ErrUnknownCommand
	case "set":
		if len(cmd.Args) != 3 {
			return nil, finn.ErrWrongNumberOfArguments
		}
		return m.Apply(conn, cmd,
			func() (interface{}, error) {
				kvm.mu.Lock()
				kvm.keys[string(cmd.Args[1])] = cmd.Args[2]
				kvm.mu.Unlock()
				return nil, nil
			},
			func(v interface{}) (interface{}, error) {
				conn.WriteString("OK")
				return nil, nil
			},
		)
	case "get":
		if len(cmd.Args) != 2 {
			return nil, finn.ErrWrongNumberOfArguments
		}
		return m.Apply(conn, cmd, nil,
			func(interface{}) (interface{}, error) {
				kvm.mu.RLock()
				val, ok := kvm.keys[string(cmd.Args[1])]
				kvm.mu.RUnlock()
				if !ok {
					conn.WriteNull()
				} else {
					conn.WriteBulk(val)
				}
				return nil, nil
			},
		)
	case "del":
		if len(cmd.Args) < 2 {
			return nil, finn.ErrWrongNumberOfArguments
		}
		return m.Apply(conn, cmd,
			func() (interface{}, error) {
				var n int
				kvm.mu.Lock()
				for i := 1; i < len(cmd.Args); i++ {
					key := string(cmd.Args[i])
					if _, ok := kvm.keys[key]; ok {
						delete(kvm.keys, key)
						n++
					}
				}
				kvm.mu.Unlock()
				return n, nil
			},
			func(v interface{}) (interface{}, error) {
				n := v.(int)
				conn.WriteInt(n)
				return nil, nil
			},
		)
	case "keys":
		if len(cmd.Args) != 2 {
			return nil, finn.ErrWrongNumberOfArguments
		}
		pattern := string(cmd.Args[1])
		return m.Apply(conn, cmd, nil,
			func(v interface{}) (interface{}, error) {
				var keys []string
				kvm.mu.RLock()
				for key := range kvm.keys {
					if match.Match(key, pattern) {
						keys = append(keys, key)
					}
				}
				kvm.mu.RUnlock()
				sort.Strings(keys)
				conn.WriteArray(len(keys))
				for _, key := range keys {
					conn.WriteBulkString(key)
				}
				return nil, nil
			},
		)
	}
}

func (kvm *Clone) Restore(rd io.Reader) error {
	kvm.mu.Lock()
	defer kvm.mu.Unlock()
	data, err := ioutil.ReadAll(rd)
	if err != nil {
		return err
	}
	var keys map[string][]byte
	if err := json.Unmarshal(data, &keys); err != nil {
		return err
	}
	kvm.keys = keys
	return nil
}

func (kvm *Clone) Snapshot(wr io.Writer) error {
	kvm.mu.RLock()
	defer kvm.mu.RUnlock()
	data, err := json.Marshal(kvm.keys)
	if err != nil {
		return err
	}
	if _, err := wr.Write(data); err != nil {
		return err
	}
	return nil
}

The Applier Type

Every Command() call provides an Applier type which is responsible for handling all Read or Write operation. In the above example you will see one m.Apply(conn, cmd, ...) for each command.

The signature for the Apply() function is:

func Apply(
	conn redcon.Conn, 
	cmd redcon.Command,
	mutate func() (interface{}, error),
	respond func(interface{}) (interface{}, error),
) (interface{}, error)
  • conn is the client connection making the call. It's possible that this value may be nil for commands that are being replicated on Follower nodes.
  • cmd is the command to process.
  • mutate is the function that handles modifying the node's data. Passing nil indicates that the operation is read-only. The interface{} return value will be passed to the respond func. Returning an error will cancel the operation and the error will be returned to the client.
  • respond is used for responding to the client connection. It's also used for read-only operations. The interface{} param is what was passed from the mutate function and may be nil. Returning an error will cancel the operation and the error will be returned to the client.

Please note that the Apply() command is required for modifying or accessing data that is shared on all of the nodes. Optionally you can forgo the call altogether for operations that are unique to the node.

Snapshots

All Raft commands are stored in one big log file that will continue to grow. The log is stored on disk, in memory, or both. At some point the server will run out of memory or disk space. Snapshots allows for truncating the log so that it does not take up all of the server's resources.

The two functions Snapshot and Restore are used to create a snapshot and restore a snapshot, respectively.

The Snapshot() function passes a writer that you can write your snapshot to. Return nil to indicate that you are done writing. Returning an error will cancel the snapshot. If you want to disable snapshots altogether:

func (kvm *Clone) Snapshot(wr io.Writer) error {
	return finn.ErrDisabled
}

The Restore() function passes a reader that you can use to restore your snapshot from.

Please note that the Raft cluster is active during a snapshot operation. In the example above we use a read-lock that will force the cluster to delay all writes until the snapshot is complete. This may not be ideal for your scenario.

Full-featured Example

There's a command line Redis clone that supports all of Finn's features. Print the help options:

go run example/clone.go -h

First start a single-member cluster:

go run example/clone.go

This will start the clone listening on port 7481 for client and server-to-server communication.

Next, let's set a single key, and then retrieve it:

$ redis-cli -p 7481 SET mykey "my value"
OK
$ redis-cli -p 7481 GET mykey
"my value"

Adding members:

go run example/clone.go -p 7482 -dir data2 -join :7481
go run example/clone.go -p 7483 -dir data3 -join :7481

That's it. Now if node1 goes down, node2 and node3 will continue to operate.

Built-in Raft Commands

Here are a few commands for monitoring and managing the cluster:

  • RAFTADDPEER addr
    Adds a new member to the Raft cluster
  • RAFTREMOVEPEER addr
    Removes an existing member
  • RAFTPEERS addr
    Lists known peers and their status
  • RAFTLEADER
    Returns the Raft leader, if known
  • RAFTSNAPSHOT
    Triggers a snapshot operation
  • RAFTSTATE
    Returns the state of the node
  • RAFTSTATS
    Returns information and statistics for the node and cluster

Consistency and Durability

Write Durability

The Options.Durability field has the following options:

  • Low - fsync is managed by the operating system, less safe
  • Medium - fsync every second, fast and safer
  • High - fsync after every write, very durable, slower

Read Consistency

The Options.Consistency field has the following options:

  • Low - all nodes accept reads, small risk of stale data
  • Medium - only the leader accepts reads, itty-bitty risk of stale data during a leadership change
  • High - only the leader accepts reads, the raft log index is incremented to guaranteeing no stale data

For example, setting the following options:

opts := finn.Options{
	Consistency: High,
	Durability: High,
}
n, err := finn.Open("data", ":7481", "", &opts)

Provides the highest level of durability and consistency.

Log Backends

Finn supports the following log databases.

  • FastLog - log is stored in memory and persists to disk, very fast reads and writes, log is limited to the amount of server memory.
  • LevelDB - log is stored only to disk, supports large logs.
  • Bolt - log is stored only to disk, supports large logs.

Contact

Josh Baker @tidwall

License

Finn source code is available under the MIT License.

You might also like...
Fast in-memory key:value store/cache with TTL

MCache library go-mcache - this is a fast key:value storage. Its major advantage is that, being essentially a thread-safe . map[string]interface{} wit

Data structure and relevant algorithms for extremely fast prefix/fuzzy string searching.

Trie Data structure and relevant algorithms for extremely fast prefix/fuzzy string searching. Usage Create a Trie with: t := trie.New() Add Keys with:

Fast and easy-to-use skip list for Go.

Skip List in Golang Skip list is an ordered map. See wikipedia page skip list to learn algorithm details about this data structure. Highlights in this

A fast little LRU cache for Go

tinylru A fast little LRU cache. Getting Started Installing To start using tinylru, install Go and run go get: $ go get -u github.com/tidwall/tinylru

Go implementation of SipHash-2-4, a fast short-input PRF created by Jean-Philippe Aumasson and Daniel J. Bernstein.

SipHash (Go) Go implementation of SipHash-2-4, a fast short-input PRF created by Jean-Philippe Aumasson and Daniel J. Bernstein (http://131002.net/sip

go/golang: fast bit set Bloom filter

package implements a fast bloom filter with real 'bitset' and JSONMarshal/JSONUnmarshal to store/reload the Bloom filter.

Implementation of Boyer-Moore fast string search algorithm in Go

boyermoore Implementation of Boyer-Moore fast string search algorithm in Go

dagger is a fast, concurrency safe, mutable, in-memory directed graph library with zero dependencies
dagger is a fast, concurrency safe, mutable, in-memory directed graph library with zero dependencies

dagger is a blazing fast, concurrency safe, mutable, in-memory directed graph implementation with zero dependencies

A fast, threadsafe skip list in Go
A fast, threadsafe skip list in Go

fast-skiplist Purpose As the basic building block of an in-memory data structure store, I needed an implementation of skip lists in Go. It needed to b

Comments
  • Build Errors / Compat with latest hashicorp/raft

    Build Errors / Compat with latest hashicorp/raft

    I tried to use you library recently; but as-is it is riddled with compile errors. I suspect the library is now out-of-date compared with the dependencies it uses? e.g: hashicorp/raft Do you plan to update?

    opened by prologic 6
  • package conflict

    package conflict

    Hi i tried to go get -u github.com/tidwall/finn but it fails, it seems that raft-leveldb and others, dont use the import github.com/tidwall/raft. Do you want to stick on the fork or can we update all modules to github.com/hashicorp/raft ?

    go/src/github.com/tidwall/finn/finn.go:293:14: cannot assign *raftleveldb.LevelDBStore to store (type bigStore) in multiple assignment:
            *raftleveldb.LevelDBStore does not implement bigStore (wrong type for GetLog method)
                    have GetLog(uint64, *"github.com/hashicorp/raft".Log) error
                    want GetLog(uint64, *"github.com/tidwall/raft".Log) error
    go/src/github.com/tidwall/finn/finn.go:299:14: cannot assign *raftfastlog.FastLogStore to store (type bigStore) in multiple assignment:
            *raftfastlog.FastLogStore does not implement bigStore (wrong type for GetLog method)
                    have GetLog(uint64, *"github.com/hashicorp/raft".Log) error
                    want GetLog(uint64, *"github.com/tidwall/raft".Log) error
    go/src/github.com/tidwall/finn/finn.go:315:14: cannot assign *raftfastlog.FastLogStore to store (type bigStore) in multiple assignment:
            *raftfastlog.FastLogStore does not implement bigStore (wrong type for GetLog method)
                    have GetLog(uint64, *"github.com/hashicorp/raft".Log) error
                    want GetLog(uint64, *"github.com/tidwall/raft".Log) error
    
    opened by mschneider82 1
  • Redirect write requests to leader

    Redirect write requests to leader

    Can we think about adding support for redirecting write requests to the leader? I've seen this done before in many raft-based systems. I think the value this provides is convenience more than anything -- not having to care which node you connect to for write.

    opened by prologic 1
  • Separate out data storage backends?

    Separate out data storage backends?

    What are your ideas on separating out the different data storage backends? My reasoning is to have less dependencies in the code. Maybe it's a good thing to have a reasonable default choice, fastlog.

    opened by dwlnetnl 1
Owner
Josh Baker
Josh Baker
:rowboat: Raft implementation in Go

?? Raft This is an instructional implementation of the Raft distributed consensus algorithm in Go. It's accompanied by a series of blog posts: Part 0:

Eli Bendersky 748 Dec 27, 2022
Fast golang queue using ring-buffer

Queue A fast Golang queue using a ring-buffer, based on the version suggested by Dariusz Górecki. Using this instead of other, simpler, queue implemen

Evan Huus 478 Jan 3, 2023
A fast (5x) string keyed read-only map for Go - particularly good for keys using a small set of nearby runes.

faststringmap faststringmap is a fast read-only string keyed map for Go (golang). For our use case it is approximately 5 times faster than using Go's

The Sensible Code Company 30 Jan 8, 2023
A tree like tool help you to explore data structures in your redis server

Redis-view is a tree like tool help you explore data structures in your redis server

dreamersdw 19 Mar 17, 2022
A Go queue manager on top of Redis

Queue A Go library for managing queues on top of Redis. It is based on a hiring exercise but later I found it useful for myself in a custom task proce

Kaveh Mousavi Zamani 74 Aug 12, 2022
ZSet is an in-memory Redis like sorted set datastructure

zset Getting Started Installing To start using hash, install Go and run go get: $ go get -u github.com/arriqaaq/zset This will retrieve the library. U

Farhan 7 Oct 13, 2022
Protocol Buffer compiler written in Go

gotoc This is gotoc, a protocol buffer compiler written in Go. This is only the parser side; you will need a plugin to generate code. Quick Start go g

David Symonds 119 Nov 29, 2022
Go framework to simplify CRUD of structured data using Graph operations

gocrud Go framework to simplify creating, reading, updating, and deleting arbitrary depth structured data — to make building REST services fast and ea

Manish R Jain 311 Nov 28, 2022
Fast ring-buffer deque (double-ended queue)

deque Fast ring-buffer deque (double-ended queue) implementation. For a pictorial description, see the Deque diagram Installation $ go get github.com/

Andrew Gillis 412 Dec 26, 2022
Go native library for fast point tracking and K-Nearest queries

Geo Index Geo Index library Overview Splits the earth surface in a grid. At each cell we can store data, such as list of points, count of points, etc.

Hailo Network IP Ltd 344 Dec 3, 2022