You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
The goal of this project is to provide an alternative to strong eventual consistency models in a
distributed system using multiple primitive data types. The use of conflict-free replicated data types (CRDTs)
can be used to prevent single point of failures as well as provide a good model for achieving strong eventual consistency.
CRDTs are data structures that can be used by applications without the need of a central server. They are able to
communicate with other applications to send and receive data. CRDTs work by using simple
mathematical rules to guarantee strong eventual consistency. CRDTs guarantee that if an application in
the distributed system goes offline, once it comes back online, it will eventually converge to the same
state as all the other applications in the system.
CRDTs can be used in offline systems, peer-to-peer communication networks, or traditional client
to server networks
📃 Features
This libary currently supports a combined of 12 CRDTs. We have also created a Trello-clone that utilizes different CRDTs in this libary.
This is to showcase how CRDTs can be used in a practical application.
⚙ Set Up
This libary has only been validated on Linux OS, and support for Windows/MAC will be provided at a later time. To use the libary itself:
./generate_prebuilt.sh : Generate prebuilt versions of test cases for GitHub Workflow
Run Scripts
run_performance.sh : Run performance binaries for all CRDTs
run_test_application.sh : Run test application
run_tests.sh : Run all tests
run_trello_application.sh : Run single instance of trello application
🐕🦺 Guide for CRDT data types
Each CRDT class has a handler and a metadata class. On each of your server, you create the handler once.
To actually instatiate the CRDT data structure use the metadata.
To add the CRDT to the server, add the metadata to the handler.
Handler fetches all the other handlers and does a merge. Equivalent of doing merge between multiple servers
Supported Operations (Metadata)
Functionality
.serialize()
Serialize the CRDT into a string
.serializeFile(std::string pathToFile)
Serialize the CRDT into a string and save it into a file
.deserialize(std::string s)
Deserialize a string into CRDT object
.deserializeFile(std::string jsonString)
Deserialize a string from a file into a CRDT object
.queryId()
Get the ID of the metadata
.queryPayload()
Get the payload of the metadata
.updatePayload(T payload)
Update the payload of of the metadata
.setPayload(T payload)
Set the payload of the metadata
Example
crdt::state::GCounterSB<uint32_t> handler(1); //Represents Server 1 with id = 1//Create several replicas all with key = 1 creating conflict
crdt::state::GCounterMetadata<uint32_t> replica1A(1,6);
crdt::state::GCounterMetadata<uint32_t> replica1B(1,15);
crdt::state::GCounterMetadata<uint32_t> replica1C(1,8);
crdt::state::GCounterMetadata<uint32_t> replica1D(1,2);
handler.addExternalReplica({replica1A,replica1B,replica1C,replica1D});
cout << handler.queryPayload() //Will print 15/*Replica1A, Replica1B, Replica1C, Replica1D ann have conflictsAll will converge to same state and have final value = 15*/
Positive Negative Counter
What is it?
Capability
Practical UseCases
Merging Policy
A counter that can go upwards and downwards
+Less memory efficient compared to other counters+Worst performance compared to other counters-Supports both increase and decrease increments
User is modifying Reddit Comment thread both on his laptop and phone at the same time
Take the max of the positive counter. Take the max of the negative counter. The payload is the sum of the positive and negative counter.
Name
Identifier
Supported Operations
Data types supported
Handler
PNCounterSB
.increasePayload(uint32_t replicaID, T payload), .decreasePayload(uint32_t replicaID, T payload), .updateInternalPayload(), .serializeObject()), .queryId(), .queryPayload(), .queryPayloadwithID(uint32_t replicaID), .addExternalReplica(std::vector<PNCounterMetadata<T>> external_replica_metadata), .updateLocalExternalPayload(std::vector<PNCounterSB> handlers)
Choose multiple verticies that is already inserted to be removed permanently
.queryEdges(),
Returns adjacency list of the graph
.queryEdgesTombstone()
Returns adjacency list of edges that are removed permanently
.insertVertice(T value)
Insert a vertex into the graph
.insertEdge(std::pair<T, T> value)
Insert a edge into the graph
.insertVertices(std::vector<T> values)
Insert multiple verticies of the graph with duplicates
.removeVertice(T value)
Remove a vertex from your graph permanently
.removeEdge(std::pair<T, T> value)
Remove an edge from yoru graph permanently
Example
crdt::state::TwoPTwoPGraphSB<uint32_t> handler(0); // Server 1
crdt::state::TwoPTwoPGraphMetadata<uint32_t> replica1A(1); // Replica 1
crdt::state::TwoPTwoPGraphMetadata<uint32_t> replica1B(2); // Replica 2
crdt::state::TwoPTwoPGraphMetadata<uint32_t> replica1C(3); // Replica 3
replica1A.insertVertice(20);
replica1B.insertVertice(21);
replica1C.insertVertice(22);
replica1A.insertEdge(std::pair<uint32_t, uint32_t>(20, 21));
replica1B.insertEdge(std::pair<uint32_t, uint32_t>(21, 22));
replica1C.insertEdge(std::pair<uint32_t, uint32_t>(22, 23));
// Handler now contains vertices and edges from all replicas
handler.addExternalReplica({replica1A,replica1B,replica1C});
Grow-Only Set
What is it?
Capability
Practical UseCases
Merging Policy
A set that only elements can be added to it
+Does not allow duplicate elements+Elements are sorted from least to greatest-Cannot remove an added element+Better performance and more memory efficient compared to other sets
Fetches all the other handlers and does a merge. Equivalent of doing merge between multiple servers
Supported Operations (Metadata)
Functionality
.serialize()
Serialize the CRDT into a string
.serializeFile(std::string pathToFile)
Serialize the CRDT into a string and save it into a file
.deserialize(std::string s)
Deserialize a string into CRDT object
.deserializeFile(std::string jsonString)
Deserialize a string from a file into a CRDT object
.queryId()
Get the ID of the metadata
.setPayload(std::set<T> payload)
Set the payload
.queryPayload()
Get all the elements inserted into the set
.insert(T value)
Insert an element into the set
.insert(std::vector<T> values)
Insert multiple elements into the set
Example
crdt::state::GSetSB<uint32_t> handler1(1); //Represents Server 1
crdt::state::GSetMetadata<uint32_t> replica1A(1,2); //id = 1, set = {2}
crdt::state::GSetMetadata<uint32_t> replica1B(1,4); //id = 1 --> First Conflict, set = {4}
crdt::state::GSetMetadata<uint32_t> replica1C(1,6); //id = 1 --> Second Conflict, set = {6}
handler1.addExternalReplica({replica1A,replica1B,replica1C}); //Add to server and resolve Conflictfor (int i: handler1.queryPayload()) cout << i; // Will print (2 4 6)
Or-Set
What is it?
Capability
Practical UseCases
Merging Policy
A set allowing to insert and remove elements. Similar to a 2PSet, but the element could be re-inserted after removal.
+Does not allow duplicate elements+Elements are sorted from least to greatest+Can remove elments-Worst performance and more memory efficient compared to other sets
A shopping list or grocery list where user can add or delete item from it
Fetch all the other handlers and does a merge. Equivalent of doing merge between multiple servers
Supported Operations (Metadata)
Functionality
.serialize()
Serialize the CRDT into a string
.serializeFile(std::string pathToFile)
Serialize the CRDT into a string and save it into a file
.deserialize(std::string s)
Deserialize a string into CRDT object
.deserializeFile(std::string jsonString)
Deserialize a string from a file into a CRDT object
.queryId()
Get the ID of the metadata
.setPayload(std::set<T> payload)
Set the payload
.queryORSet()
Get the payload of the ORSet metadata
.insert(T value)
Insert value into the set
.insert(std::vector<T> values)
Insert multiple values into the set
.remove(T value)
Remove value from the set
Example
crdt::state::ORSetSB<uint32_t> handler(1); //Represents Server 1
crdt::state::ORSetMetadata<uint32_t> replica1A(3,{1,2}); //id = 3 (Conflict) -> Set = {1,2}
crdt::state::ORSetMetadata<uint32_t> replica1B(3,{3,4}); //id = 3 (Conflict) -> Set = {3,4}
crdt::state::ORSetMetadata<uint32_t> replica1C(3,{5,6}); //id = 3 (Conflict) -> Set = {5,6}
replica1A.remove(2); //id = 3 (Conflict) -> Set = {1}
replica1B.remove(4); //id = 3 (Conflict) -> Set = {3}
std::vector<uint32_t> removed_items1 = {3,4};
handler.addExternalReplica({replica1A,replica1B,replica3C}, {{replica1A.queryId(),removed_items1}});
for (int i: handler.queryORSetwithID(3)) cout << i; //Converge and flix all conflicts// Will print (1, 5, 6)
Two-Phase Set
What is it?
Capability
Practical UseCases
Merging Policy
A set allowing to insert and remove elements
+Does not allow duplicate elements+Elements are sorted from least to greatest-Once an element is removed, cannot be added back in again+Average performance and more memory efficient compared to other sets
A MMORPG where the set holds user information. If the user is banned, cannot be added back in again.
A multi-set where allowing for insertion and deletion
+Allow duplicate elements+Support removing elements+Elements are sorted from least to greatest+More memory efficient compared to LWW
For the same shopping cart shared between multiple users
The last time stamp wins
Name
Identifier
Supported Operations
Data types supported
Handler
LWWMultiSetSB
.insert(uint32_t replicaID, long long int timestamp, T value) , .insert(uint32_t replicaID, long long int timestamp, std::vector<T> value) , .remove(uint32_t replicaID, long long int timestamp, T value) , .remove(uint32_t replicaID, long long int timestamp, std::vector<T> value) , .updateInternalPayload(), .queryId() , .queryLWWMultiSet(), .queryLWWMultiSetwithID(uint32_t replicaID), .addExternalReplica(std::vector<LWWMultiSetMetadata<T>> external_replica_metadata), .updateLocalExternalPayload(std::vector<LWWMultiSetSB> handlers)
int, char , bool, string, double
Metadata
LWWMultiSetMetadata
.serialize(),.serializeFile(std::string pathToFile), .deserialize(std::string s), .deserializeFile(std::string jsonString), .queryId(), .queryId() , .queryTime() , .insert(long long int timestamp, T value), .insert(long long int timestamp, std::vector<T> value), .remove(long long int timestamp, T value), .remove(long long int timestamp, std::vector<T> value), .queryPayload(), .setPayload(std::multiset<T> payload, long long int timestamp),
int, char , bool, string, double
Supported Operations (Handler)
Functionality
.insert(uint32_t replicaID, long long int timestamp, T value)
Insert element into multiset in handler via ID and timestamp
.insert(uint32_t replicaID, long long int timestamp, std::vector<T> value)
Insert multiple elements into multiset in handler via ID and timestamp
.remove(uint32_t replicaID, long long int timestamp, T value)
Remove element from multiset in handler via ID and timestamp
.remove(uint32_t replicaID, long long int timestamp, std::vector<T> value)
Remove multiple elements from multiset in handler via ID and timestamp
.updateInternalPayload(), .queryId()
Merges all the CRDTs that it contains. Equivalent to doing a localMerge
.queryLWWMultiSet()
Returns all the elements of all the multisets within the handler
Fetches all the other handlers and does a merge. Equivalent of doing merge between multiple servers
Supported Operations (Metadata)
Functionality
.serialize()
Serialize the CRDT into a string
.serializeFile(std::string pathToFile)
Serialize the CRDT into a string and save it into a file
.deserialize(std::string s)
Deserialize a string into CRDT object
.deserializeFile(std::string jsonString)
Deserialize a string from a file into a CRDT object
.queryId()
Get the id of the multiset
.queryTime() , .insert(long long int timestamp, T value)
Get the time of the last write for multiset
.insert(long long int timestamp, std::vector<T> value)
Insert element into multiset providing the time
.remove(long long int timestamp, T value)
Remove element from multiset proving the time. If time provided is less than the last write time, the remove operations will not remove
.remove(long long int timestamp, std::vector<T> value)
Remove multiple elements from multiset providing the time.
.queryPayload()
Return the multiset
.setPayload(std::multiset<T> payload, long long int timestamp)
Intialize the multiset
Example
crdt::state::LWWMultiSetSB<uint32_t> handler1(1); //Represents Server 1
crdt::state::LWWMultiSetMetadata<uint32_t> replica1A(0); //id = 0, time = 0, multiset = {}
crdt::state::LWWMultiSetMetadata<uint32_t> replica1B(0); //conflict id = 0, time = 0, multiset = {}
crdt::state::LWWMultiSetMetadata<uint32_t> replica1C(0); //conflict id = 0, time = 0, multiset = {}
replica1A.insert(0,{20,25,30}); //id = 0, time = 1, multiset = {20,25,30}
replica1B.insert(1,{30,35}); // id = 0, time = 1, multiset = {30,35}
replica1C.insert(2, {40,45,30,30}); // id = 0, time = 2, multiset = {30,30,40,45}
handler1.addExternalReplica({replica1A,replica1B,replica1C}); //Added 3 replicas to handler and converge to fix conflict// the last time id = 0 was written was @ time = 2 --> merge to the multiset at time = 2 --> multiset = {30,30,40,45}
handler1.remove(0,3,{30,30}); // id = 0, time = 3, multiset = {40,45}
handler1.remove(0,4,30); // id = 0, time = 4, multiset = {40,45}
handler1.remove(0,5,{30,30,45}); // id = 0, time = 5, multiset = {40}
handler1.insert(0,6,{30,30}); // id = 0, time = 6, multiset = {30,30,40}
handler1.remove(0,8,30); // id = 0, time = 8, multiset = {30,40}for (int i: handler1.queryPayload()) cout << i; //Should print (30, 40)
Grow-Only Vector
What is it?
Capability
Practical UseCases
Merging Policy
A array where only elements are allowed to be added
+Allow duplicate elements-Does not support removing elements+Elements are put in the order they come in
To view the order at which users clock in at work.
-Keys have to be unique+Keys do not have to be string-Value must be string-Does not support other data structures except string+Keys are sorted from least to greatest
Collaberated word document, where key = page number and value is the text on each page
Union of conflict strings
Name
Identifier
Supported Operations
Data types supported (Key)
Data types supported (Value)
Handler
GMapSBString
.fixlocalConflict(std::string StringA, std::string StringB, K key, int sysCall), .updateInternalPayload(GMapMetadata<K,T> metadata, bool externalCall = false), .queryId(), .queryAllKeys(), .queryAllValues(), .queryPayloadwithID(K mapId, K key) , .fixSameKeyConflict(GMapMetadata<K,T>& metadata), .addExternalReplica(std::vector<GMapMetadata<K,T>> external_replica_metadata), .updateLocalExternalPayload(std::vector<GMapSBString> handlers)
int, char , bool, string, double
string
MetaData is the same as Generic Map
Supported Operations (Handler)
Functionality
.fixlocalConflict(std::string StringA, std::string StringB, K key, int sysCall)
Helper function to fix conflcits between strings in metadata
+Support deletion of characters at any position+Support insertion of characters at any position+Ordering of characters in the string do not change-Does not always give the intended merge results that end-user wants
Fetches all the other handlers and does a merge. Equivalent of doing merge between multiple servers
Supported Operations (Metadata)
Functionality
.serialize()
Serialize the CRDT into a string
.serializeFile(std::string pathToFile)
Serialize the CRDT into a string and save it into a file
.deserialize(std::string s)
Deserialize a string into CRDT object
.deserializeFile(std::string jsonString)
Deserialize a string from a file into a CRDT object
.queryId()
Get the id of the String
.queryPayload()
Return the string
.setPayload(std::string payload)
Initialize the string to the intended value
.insert(int pos, std::string payload)
Insert text into the string given position
.clear()
Clear the entire string
.erase(int startIndex, int endIndex)
Erase text in the sting given position
Example
crdt::operation::StringOB<std::string> handler1(1);
crdt::operation::StringMetaData<std::string> replica1A(5, "Hello World");
//id = 5, string = "Hello World"
crdt::operation::StringMetaData<std::string> replica1B(5, "Hello Sun ");
// Conflict id = 5, string = "Hello Sun ")
handler1.addExternalReplica({replica1A,replica1B});
//Add to handler1, handler1, fix conflict and merge
cout << handler1.queryPayload(); //Will print ("Hello Sun World")
🖼 Showcase - TrelloRDT
Module
Description
1. Login Page
Create a new account or login.
2. Online User Display
CRDT used from the library: Grow Only Vector. Will show you who else is online.
3. Add New Board
Create a new board.
4. Displaying Boards
CRDT used from the library: Last-Write-Wins Multiset. Displays the board, click red button to delete.
5. Displaying Number of Boards used
CRDT used from the library: Postive-Negative Counter. Shows how many boards are in each category.
6. Task Priority List
CRDT used from the library: Grow-Only Map (Generic). Displays the priority of tasks needing to be complete.
7. Merge
Merge your board with everyone else.
8. Logout
Logout of application
9. Add Board Page
Assign the task to someone, list the task, and the urgency.
10. Text-Format Database
Stores all the user information
✅ CI/CD Integration - Catch2
For our testing framework and Github workflow we are using Catch2. All our unit tests can be found in the directory:
/tests/test.cpp. If you notice any issues, please leave an Issue Request.
If you want to contribute any new test cases, please add the test case in and create a PR.
🧪 Performance Analysis
Here is a showcase of our benchmark analysis. Our benchmark criteria was to measure how long it took for each CRDT to perform 100 merge and then divide the total time by 100 to get the average time for 1 merge operation. To better showcase the advantage of C++ has over other framework we decided to compare it with an existing Python libary: https://github.com/anshulahuja98/python3-crdt. Special Credits to Geetesh Gupta and Anshul Ahuja who are the rightful owners of this libary. Please go and check them out as well.
Lww-Multiset -> In the python libary a LWW-Set was used while ours is a LWW-Multiset. The difference is a multiset allows duplicate elements while a set does not.
Mutable String -> The algorithm for merging was different compared to our one. Furthermore strings in C++ are mutable while in Python they are not.
The raw data for the benchmark can be found under the folder: /benchmark
🤝 Contribute
Have an data structure in mind such as a binary tree or 2D arrays and want to attempt to make it into a CRDT? No open-source libary
can grow without the help of the community and would love your contributions in helping to add more CRDTs to this libary. To add a new
CRDT to this libary, go to either:
/src/operation_based
or /src/state_based and create your CRDT. Remember to add the CRDT in the
/src/CrdtObject.hpp. Once you are done create some unit tests for it under /tests/test.cpp to validate your results.
Then leave a PR and if everything looks good, it will get merged into the repository.
We greatly apperciate anyone who contributes or leaves feedback.
👏 Special Thanks
Special thanks to all the individuals, projects, creators and developers who have created awesome software for which we were able to build our library off of. A detailed list can be found in acknowledgements.txt.
📖 Summary
The image below highlights the key components of this open source library: https://mergerdt.tiiny.site/ <--(Click here for more clear image)
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
![](https://i.ibb.co/kXgDkwJ/Graph.jpg")
![](https://i.ibb.co/bXShyDC/Capstone-Board-Print-Edition.jpg")
