A LWW CRDT implementation with Redis support in Go.
A conflict-free replicated data type (CRDT) is a type of data structure that is used to achieve strong eventual consistency (SEC) and monotonicity (ie, there are no rollbacks) across a set of nodes in a distributed system.
It can be particularly interesting in available/partition-tolerant (AP) environment because it makes conflicts mathematically impossible. In other words, there is no need for conflict resolution.
This package focuses on Last-Writer-Wins (LWW) Element Set data structure that uses timestamped adds and removes. It provides 2 implementations (Go maps and Redis).
Unlike Roshi, this package does not provide replication, sharding, garbage collection or REST-ish HTTP interface.
This package (lww) exposes 3 different constructors. Each constructor returns an ElementSet.
Public methods return an error if something like a network failure error happens.
Add() and Remove() methods do not guarantee that the operation took effect,
just that it was acknowledged if no error.
Exists() and Get() methods provides liveness guarantees only.
See GoDoc reference for details.
import (
"time"
"github.com/cedricblondeau/go-lww-element-set"
)
ms := lww.NewMapElementSet()
ms.Add("Hello", time.Now())
ms.Add("Hi!", time.Now())
ms.Remove("Hello", time.Now())
elements, err := ms.Get()
elements // ["Hi!"]import (
"time"
"github.com/cedricblondeau/go-lww-element-set"
redis "gopkg.in/redis.v4"
)
rc := redis.NewClient(&redis.Options{
Addr: "localhost:6379",
Password: "", // no password set
DB: 0, // use default DB
})
rs := lww.NewRedisElementSet("shopping_cart", rc)
addErr1 := s.Add("Product #1", time.Now()) // Check addErr1 for eventual redis error
addErr2 := rs.Add("Product #2", time.Now()) // Check addErr2 for eventual redis error
rmErr := rs.Remove("Product #1", time.Now()) // Check rmErr for eventual redis error
elements, err := rs.Get() // Check err for eventual redis error
elements // ["Product #2"]You can also use NewRedisElementSetWithCustomMarshalling() construtor
to specify custom marshalling/unmarshalling functions.
ElementSet defines the LWW Element Set logic. An ElementSet is backed by two underlying timestamped sets (timedSet).
timedSet is an interface that defines a set where added element are associated with timestamps. This package provides two implementations of this interface:
- mapTimedSet (using Go maps)
- redisTimedSet (using Redis)
Go maps implementation uses two mapTimedSet. A mapTimedSet is a timedSet backed with a Go map. Because Go maps are not safe for concurrent use, mutual exclusion is used.
Redis implementation uses two redisTimedSet. A redisTimedSet is a timedSet backed with a Redis sorted set. This implementation uses go-redis client.
To make the add() action atomic, a Redis script (which is transactional by definition and by extension atomic) is used.
Redis uses IEEE 754 64-bit numbers to rank elements in a sorted set (score). As a result, the given timestamps will be converted to float64 and it will limit the precision to one millisecond.
To run tests with race detector enabled:
go test -race