proxy.golang.org : github.com/kavehmz/lww
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 package implements LWW data structure in a modular way. It defines a TimedSet interface for underlying storage. lww package includes two storage underlying. 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. Maps are by nature vulnerable to concurrent access. To avoid race problems Set uses a sync.RWMutex as its locking mechanism. 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. 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: 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.
Registry
-
Source
- Documentation
- JSON
- codemeta.json
purl: pkg:golang/github.com/kavehmz/lww
License: MIT
Latest release: over 9 years ago
First release: over 9 years ago
Namespace: github.com/kavehmz
Stars: 3 on GitHub
Forks: 0 on GitHub
See more repository details: repos.ecosyste.ms
Last synced: about 1 month ago