README
¶
A conflict-free replicated data type.
What is it
In distributed computing, a conflict-free replicated data type (CRDT) is a type of specially-designed data structure used to achieve strong eventual consistency (SEC) and monotonicity (absence of rollbacks).
One type of data structure used in implementing CRDT is LWW-element-set.
LWW-element-set is a set that its elements have timestamp. Add and remove will save the timestamp along with data in two different sets for each element.
Queries over LWW-set will check both add and remove timestamps to decide about state of each element is being existed to removed from the list.
Documentation
¶
Overview ¶
Package lww implements a Last-Writer-Wins (LWW) Element Set data structure.
In distributed computing, a conflict-free replicated data type (CRDT) is a type of specially-designed data structure used to achieve strong eventual consistency (SEC) and monotonicity (absence of rollbacks).
One type of data structure used in implementing CRDT is LWW-element-set.
LWW-element-set is a set that its elements have timestamp. Add and remove will save the timestamp along with data in two different sets for each element.
Queries over LWW-set will check both add and remove timestamps to decide about state of each element is being existed to removed from the list.
LWW ¶
lww package implements LWW data structure in a modular way. It defines a TimedSet interface for underlying storage.
lww package includes two storage underlying.
Set ¶
Set is one implementation of TimedSet. It uses Go maps to store data. It is a fast but volatile implementation.
Maps in theory have worse Big O of O(n) for different operations, but in practice they are almost reliable for O(1) as long as hash function and hash table implementations are good enough.
Set is the default underlying for LWW if no other TimedSet are attached to AddSet or RemoveSet.
# This will use Set as its AddSet and RemoveSet
lww := LWW{}
Maps are by nature vulnerable to concurrent access. To avoid race problems Set uses a sync.RWMutex as its locking mechanism.
RedisSet ¶
RedisSet is another implementation of TimedSet included in lww package. It uses Redis Sorted Sets to store data.
Redis nature of atomic operations makes it immune to race problem and there is no need to any extra lock mechanism. But it introduces other complexities.
To keep the lww simple, handling of Redis connection for both AddSet and RemoveSet in case of RedisSet is passed to client. It is practical as Redis setup can vary based on application and client might want handle complex connection handling.
Adding New underlying ¶
To add a new underlying you need to implement the necessary methods in your structure. They are defined in TimedSet interface.
Assuming you do that and they work as expected you can initialize LWW like:
add := MyUnderlying{param: "for_add"}
remove := MyUnderlying{param: "for_remove"}
lww := LWW{AddSet:add, RemoveSet:remove}
Note that in theory AddSet and RemoveSet can have different underlying attached. This might be useful in applications which can predict higher magnitude of Adds compared to Removes. In that case application can implementation different types of TimedSet to optimize the setup
There is also a an underlying implementation that mixes two Map and Redis implementations. It is available at https://github.com/kavehmz/qset. That implementation is more practical as it will be as fast as internal maps but persistent and sharable through a redis server.
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type LWW ¶
type LWW struct {
// AddSet will store the state of elements added to the set. By default it is will be of type lww.Set.
AddSet TimedSet
// AddSet will store the state of elements removed from the set. By default it is will be of type lww.Set
RemoveSet TimedSet
}
LWW type a Last-Writer-Wins (LWW) Element Set data structure.
Example ¶
l := LWW{}
l.Init()
e := "Any_Structure"
l.Add(e, time.Now().UTC())
l.Remove(e, time.Now().UTC().Add(time.Second))
fmt.Println(l.Exists(e))
l.Add(e, time.Now().UTC().Add(2*time.Second))
fmt.Println(l.Exists(e))
Output: false true
func (*LWW) Add ¶
Add will add an element to the add-set if it does not exists and updates its timestamp to great one between current one and new one.
func (*LWW) Exists ¶
Exists returns true if element has a more recent record in add-set than in remove-set
type RedisSet ¶
type RedisSet struct {
// Conn is the redis connection to be used.
Conn redis.Conn
// AddSet sets which key will be used in redis for the set.
SetKey string
// Marshal function needs to convert the element to string. Redis can only store and retrieve string values.
Marshal func(interface{}) string
// UnMarshal function needs to be able to convert a Marshalled string back to a readable structure for consumer of library.
UnMarshal func(string) interface{}
// LastState is an error type that will return the error state of last executed redis command. Add redis connection are not shareable this can be used after each command to know the last state.
LastState error
// contains filtered or unexported fields
}
RedisSet is a race free implementation of what WWL can use as udnerlying set. This implementation uses redis ZSET. ZSET in redis uses scores to sort the elements. Score is a IEEE 754 floating point number, that is able to represent precisely integer numbers between -(2^53) and +(2^53) included. That is between -9007199254740992 and 9007199254740992. This will limit this sets precision to save element's action timestamp to 1 milli-seconds. Notice that time.Time precision is 1 nano-seconds by defaults. For this lack of precision all timestamps are rounded to nearest microsecond. Using redis can also cause latency cause by network or socket communication.
Example ¶
c, _ := redis.Dial("tcp", "localhost:6379")
s := RedisSet{Conn: c, Marshal: func(e interface{}) string { return e.(string) }, UnMarshal: func(e string) interface{} { return e }, SetKey: "TESTKEY"}
s.Init()
s.Set("Data", time.Unix(1451606400, 0))
ts, ok := s.Get("Data")
fmt.Println(ok)
fmt.Println(ts.Unix())
Output: true 1451606400
func (*RedisSet) Get ¶
Get returns timestmap of the element in the set if it exists and true. Otherwise it will return an empty timestamp and false.
func (*RedisSet) Init ¶
func (s *RedisSet) Init()
Init will do a one time setup for underlying set. It will be called from WLL.Init
type Set ¶
Set is a race free implementation of what WWL can use as udnerlying set. This implementation uses maps. To avoid race condition that comes by using maps it is using a locking mechanism. Set is using separete Read/Write locks. Map data structure have a practical performance of O(1) but locking instructions might make this implementation sub optimal for write heavy solutions.
Note: Elements of set type must be usable as a hash key. Any comparable in Go type can be used.
func (*Set) Get ¶
Get returns timestmap of the element in the set if it exists and true. Otherwise it will return an empty timestamp and false.
type TimedSet ¶
type TimedSet interface {
//Init will do a one time setup for underlying set. It will be called from WLL.Init
Init()
//Len must return the number of members in the set
Len() int
//Get returns timestmap of the element in the set if it exists and true. Otherwise it will return an empty timestamp and false.
Get(interface{}) (time.Time, bool)
//Set adds an element to the set if it does not exists. It it exists Set will update the provided timestamp.
Set(interface{}, time.Time)
//List returns list of all elements in the set
List() []interface{}
}
TimedSet interface defines what is required for an underlying set for WWL.
Source Files
Directories