• This repository has been archived on 04/Nov/2020
  • Stars
    star
    541
  • Rank 82,114 (Top 2 %)
  • Language
    Go
  • License
    MIT License
  • Created about 8 years ago
  • Updated about 4 years ago

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

Fast Raft framework using the Redis protocol for Go

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.

More Repositories

1

gjson

Get JSON values quickly - JSON parser for Go
Go
12,768
star
2

tile38

Real-time Geospatial and Geofencing
Go
8,655
star
3

evio

Fast event-loop networking for Go
Go
5,747
star
4

buntdb

BuntDB is an embeddable, in-memory key/value database for Go with custom indexing and geospatial support
Go
4,196
star
5

redcon

Redis compatible server framework for Go
Go
2,005
star
6

sjson

Set JSON values very quickly in Go
Go
1,978
star
7

SwiftWebSocket

Fast Websockets in Swift for iOS and OSX
Swift
1,532
star
8

summitdb

In-memory NoSQL database with ACID transactions, Raft consensus, and Redis API
Go
1,394
star
9

jj

JSON Stream Editor (command line utility)
Go
1,293
star
10

btree

B-tree implementation for Go
Go
937
star
11

hashmap.c

Hash map implementation in C.
C
631
star
12

uhaha

High Availability Raft Framework for Go
Go
579
star
13

pinhole

3D Wireframe Drawing Library for Go
Go
554
star
14

wal

Write ahead log for Go.
Go
525
star
15

tg

Geometry library for C - Fast point-in-polygon
C
502
star
16

Safe

Modern Concurrency and Synchronization for Swift.
Swift
417
star
17

pretty

Efficient JSON beautifier and compactor for Go
Go
354
star
18

chanx

A simple interface wrapper around a Go channel.
Go
321
star
19

rtree

An R-tree implementation for Go
Go
285
star
20

btree.c

B-tree implementation in C
C
246
star
21

GoSwift

Go Goodies for Swift. Including goroutines, channels, defer, and panic.
Swift
234
star
22

shardmap

A simple and efficient thread-safe sharded hashmap for Go
Go
211
star
23

hashmap

A simple and efficient hashmap package for Go. Open addressing, robin hood hashing, and xxh3 algorithm. Supports generics.
Go
203
star
24

celltree

A fast in-memory prefix tree that uses uint64 for keys and allows for duplicate entries.
Go
201
star
25

gjson.rs

Get JSON values quickly - JSON parser for Rust
Rust
195
star
26

cities

10,000 Cities with Latitude, Longitude, and Elevation in Go
Go
161
star
27

tinylru

A fast little LRU cache for Go
Go
144
star
28

Avios

Realtime H264 decoding library for iOS.
Swift
129
star
29

jd

Interactive JSON Editor
Go
128
star
30

pinhole-js

3D Wireframe Drawing Library for HTML Canvas
JavaScript
119
star
31

mmap

Load file-backed memory
Go
117
star
32

geojson

GeoJSON for Go. Used by Tile38
Go
116
star
33

doppio

Doppio is a fast LRU cache on top of Ristretto, Redcon, and Evio. Support for the Redis protocol.
Go
115
star
34

rtree.rs

A fast R-tree for Rust
Rust
112
star
35

match

Simple string pattern matcher for Go
Go
97
star
36

rtree.c

An R-tree implementation in C
C
96
star
37

tinybtree

Just an itsy bitsy b-tree in Go
Go
94
star
38

jsonc

Parse json with comments and trailing commas.
Go
79
star
39

rhh

A simple and efficient hashmap package for Go. Uses open addressing, Robin Hood hashing, and xxhash algorithm.
Go
79
star
40

kvnode

key value server. redis api, leveldb storage, raft support
Go
79
star
41

raft-fastlog

Raft in-memory backend implementation with persistence
Go
78
star
42

resp

Reader, Writer, and Server implementation for the Redis RESP Protocol.
Go
78
star
43

modern-server

Basic web server framework with HTTP/2 and Let's Encrypt.
Go
76
star
44

limiter

A goroutine limiter for Go
Go
76
star
45

redraft

Redis + Raft server implementation
Go
75
star
46

redcon.rs

Redis compatible server framework for Rust
Rust
72
star
47

rocksdb-server

Fast Redis clone written in C using RocksDB as a backend.
C++
72
star
48

lotsa

Simple Go library for executing lots of operations spread over any number of threads
Go
71
star
49

box

Efficiently box values in Go. Optimized for primitives, strings, and byte slices.
Go
69
star
50

evio-lite

Fast event-loop networking for Go (the lite version)
Go
68
star
51

transform

Using io.Reader for data transformation in Go
Go
67
star
52

uspto-trademark

How to file a USPTO trademark without an attorney for $225
66
star
53

pjson

A JSON stream parser for Go
Go
66
star
54

geodesic

Go package for performing accurate measurements of Earth. Includes the geodesic routines from GeographicLib.
Go
59
star
55

expr

Expression evaluator for Go
Go
58
star
56

json.c

Fast JSON parser for C
C
56
star
57

spinlock

A spinlock implementation for Go.
Go
56
star
58

raft-wal

Write ahead Raft log for Go
Go
55
star
59

rtred

RTree implementation for Go
Go
53
star
60

bfile

A buffer pool file I/O library for Go
Go
53
star
61

mvt

Draw Mapbox Vector Tiles (MVT) in Go
Go
52
star
62

redcon.c

Redis compatible server framework for C
C
47
star
63

cache-server

A minimal key/value server written in Rust with Redis API support.
Rust
46
star
64

spanmap

A fast collection type that uses uint64 for keys.
Go
44
star
65

go-node

Run Javascript in Go using Node.js
Go
42
star
66

ticketd

A distributed service for monotonically increasing tickets.
Go
42
star
67

hexd

Please love the nicely formatted hex.
Go
42
star
68

DeflateSwift

Deflate Compression for Swift
Swift
40
star
69

proximity-chat

Chat app for real-time chats with people within 500 meters.
JavaScript
39
star
70

lru

A simple and efficient LRU cache package for Go
Go
38
star
71

sider

A Redis clone written in Go
Go
36
star
72

xv

An expression evaluator for C
C
34
star
73

geometry

Efficient 2D geometry library for Go.
Go
32
star
74

pkg.sh

A generalized package manager for whatever code.
Shell
32
star
75

rfront

An HTTP protocol frontend for Redis-compatible services.
Go
31
star
76

redis-gis

Redis fork with Geospatial support based on Tile38 commands
C
31
star
77

RetroSwiper

Load classic games from magnetic swipe cards
Rust
31
star
78

uhasql

A high availability Sqlite service
C
30
star
79

redbench

Benchmarking for custom Redis commands and modules
Go
30
star
80

sds

simple data streams for go
Go
29
star
81

spmap

A hashmap for Go that uses crypto random seeds, hash hints, open addressing, and robin hood hashing.
Go
29
star
82

IoniconsSwift

Ionicons for Swift and iOS
Swift
29
star
83

raft-leveldb

Raft backend using LevelDB
Go
28
star
84

evio.c

A framework for building event based networking applications.
C
28
star
85

tinyqueue

Binary heap priority queues in Go
Go
27
star
86

kvbench

Server for benchmarking pure Go key/value databases
Go
26
star
87

gjson-play

A playground for GJSON. Runs in the browser.
JavaScript
25
star
88

randjson

Make random JSON in Go
Go
25
star
89

redlog

Redis style logger for Go
Go
25
star
90

SnapHTTP

An incredibly simple HTTP client library for Swift.
Swift
24
star
91

qtree

jeez it's just a quadtree chill out
Go
24
star
92

rtime

Retrieve the current time from remote servers
Go
21
star
93

fast-spatial-joins

Go vs GPU: Fast Spatial Joins
Go
21
star
94

assert

An assert function for Go that works like the one in C.
Go
20
star
95

pair

create low memory key/value objects in Go
Go
20
star
96

match.c

Simple string pattern matcher for C
C
19
star
97

secret

A simple utility for encrypting and decrypting data in Go (AES-256-CFB)
Go
19
star
98

pony

🌈 🐴 Turn your terminal text into an absolutely beautiful display of dazzling colors....
Go
19
star
99

btree-benchmark

Benchmark utility for the tidwall/btree Go package
Go
19
star
100

lru-server

A convenient LRU cache server that supports REST API and Let's Encrypt.
Go
18
star