README.md 4.6 KB
Newer Older
Yuqi Zhang's avatar
Yuqi Zhang committed
1
# Conflict-Free Replicated Data Types Based on Redis
2

Yuqi Zhang's avatar
Yuqi Zhang committed
3
Several Conflict-Free Replicated Data Types (CRDTs) implemented based on Redis(6.0.5).
4

5 6
Things we do for such implementation:

Yuqi Zhang's avatar
Yuqi Zhang committed
7 8
* Enable Redis to replicate in P2P mode.
* Implement the CRDT framework.
Yuqi Zhang's avatar
Yuqi Zhang committed
9
* Implement specific CRDTs according to their algorithms.
10

Yuqi Zhang's avatar
Yuqi Zhang committed
11 12 13
The CRDTs currently implemented:

* Replicated Priority Queue (RPQ)
Yuqi Zhang's avatar
Yuqi Zhang committed
14
  * [Add-Win RPQ](document/add-win-crpq.pdf)
Yuqi Zhang's avatar
Yuqi Zhang committed
15 16 17 18 19 20 21
  * [Remove-Win RPQ](document/rwf-tr.pdf)
  * [RWF-RPQ](document/rwf-tr.pdf)
* List
  * [Remove-Win List](document/rwf-tr.pdf)
  * [RWF-List](document/rwf-tr.pdf)

For more details of our implementation, please read the linked article of the CRDTs above. Also you can read the *Performance measurements* section of [the technical report](https://arxiv.org/abs/1905.01403). Note that the **Remove-Win RPQ** in this technical report corresponds to the **RWF-RPQ** here.
22

Yuqi Zhang's avatar
Yuqi Zhang committed
23
## Build
24

Yuqi Zhang's avatar
Yuqi Zhang committed
25
Our modified Redis is in folder *redis-6.0.5*. Please build it in the default mode:
26

Yuqi Zhang's avatar
Yuqi Zhang committed
27
```bash
Yuqi Zhang's avatar
Yuqi Zhang committed
28 29 30 31
cd redis-6.0.5
make
sudo make install
```
Yuqi Zhang's avatar
Yuqi Zhang committed
32

Yuqi Zhang's avatar
Yuqi Zhang committed
33
## Test
34

Yuqi Zhang's avatar
Yuqi Zhang committed
35
In the folder *experiment/redis_test* there are scripts for testing our modified Redis and RPQ implementations. By default, the test will start 5 Redis server instances on the local machine, listening on port 6379, 6380, 6381, 6382 and 6383. You may choose to start some of these server instances by using parameters when you run the scripts.
36

Yuqi Zhang's avatar
Yuqi Zhang committed
37
Here we focus on 5 scripts:
38

Yuqi Zhang's avatar
Yuqi Zhang committed
39 40 41 42 43
* **server.sh [parameters]** Start the 5 Redis instances, or the Redis instances specified by parameters.
* **construct_replication.sh [parameters]** Construct P2P replication among the 5 Redis instances, or the Redis instances specified by parameters.
* **client.sh <server_port>** Start a client to connect to the Redis server listening on the specified port.
* **shutdown.sh [parameters]** Close the 5 Redis instances, or the Redis instances specified by parameters.
* **clean.sh [parameters]** Remove the database files (.rdb files) and log files (.log files) of the 5 Redis instances, or the Redis instances specified by parameters.
44

Yuqi Zhang's avatar
Yuqi Zhang committed
45 46
Here we show an example to test our implementation using all the 5 Redis server instances.

Yuqi Zhang's avatar
Yuqi Zhang committed
47
Firstly go to the *experiment/redis_test*, **start** the Redis server instances and **construct P2P replication** among them.
Yuqi Zhang's avatar
Yuqi Zhang committed
48

Yuqi Zhang's avatar
Yuqi Zhang committed
49
```bash
Yuqi Zhang's avatar
Yuqi Zhang committed
50 51 52 53
cd experiment/redis_test
./server.sh
./construct_replication.sh
```
54

Yuqi Zhang's avatar
Yuqi Zhang committed
55
Now you can start redis clients to connect to Redis servers and do RPQ read/write operations. Here shows **start a client** to connect one Redis server.
56

Yuqi Zhang's avatar
Yuqi Zhang committed
57
```bash
Yuqi Zhang's avatar
Yuqi Zhang committed
58 59
./client.sh <server_port>
```
60

Yuqi Zhang's avatar
Yuqi Zhang committed
61
When you've finished testing, you may **close** the Redis server instances.
62

Yuqi Zhang's avatar
Yuqi Zhang committed
63
```bash
Yuqi Zhang's avatar
Yuqi Zhang committed
64 65
./shutdown.sh
```
66

Yuqi Zhang's avatar
Yuqi Zhang committed
67
Finally, you can **remove** the Redis database files (.rdb files) and log files (.log files).
68

Yuqi Zhang's avatar
Yuqi Zhang committed
69
```bash
Yuqi Zhang's avatar
Yuqi Zhang committed
70 71
./clean.sh
```
72

Yuqi Zhang's avatar
Yuqi Zhang committed
73
To further redo the experiment of our work our please check [here](experiment/README.md).
Yuqi Zhang's avatar
Yuqi Zhang committed
74

Yuqi Zhang's avatar
Yuqi Zhang committed
75 76 77 78 79 80 81 82 83 84 85 86 87 88 89
## CRDT Operations

Different implementations of the same type of CRDT offer the same operations for users. We use **[type][op]** to name our CRDT operations. The operations name contains of an implementation type prefix and an operation type suffix. For example, the name of operation of RWF-RPQ to add one element is **rwfzadd**, where **rwf** is the implementation type prefix and **zadd** is the operation type suffix.

### RPQ operations

The **[type]** prefix of different RPQs are:

* Add-Win RPQ : **o**
* Remove-Win RPQ : **r**
* RWF-RPQ : **rwf**

The operations of RPQs are:

* **[type]zadd Q E V** : Add a new element *E* into the priority queue *Q* with initial value *V*.
90
* **[type]zincrby Q E I** : Add the increment *I* to the value of element *E* in the priority queue *Q*.
Yuqi Zhang's avatar
Yuqi Zhang committed
91 92 93 94 95
* **[type]zrem Q E** : Remove element *E* from the priority queue *Q*.
* **[type]zscore Q E** : Read the value of element *E* from the priority queue *Q*.
* **[type]zmax Q** : Read the element with the largest value in the priority queue *Q*. Returns the element and its value.

### List operations
Yuqi Zhang's avatar
Yuqi Zhang committed
96

Yuqi Zhang's avatar
Yuqi Zhang committed
97
The **[type]** prefix of different Lists are:
Yuqi Zhang's avatar
Yuqi Zhang committed
98

Yuqi Zhang's avatar
Yuqi Zhang committed
99 100
* Remove-Win List : **r**
* RWF-List : **rwf**
Yuqi Zhang's avatar
Yuqi Zhang committed
101

Yuqi Zhang's avatar
Yuqi Zhang committed
102
The operations of Lists are:
Yuqi Zhang's avatar
Yuqi Zhang committed
103

Yuqi Zhang's avatar
Yuqi Zhang committed
104 105 106
* **[type]linsert L prev id content font size color property** : Add a new element *id* after *prev* into the list *L*, with the content *content*, and the initial properties *font* *size* *color* and *property*(bitmap that encodes bold, italic and underline). If *prev* is "null", it means insert the element at the beginning of the list. If *prev* is "readd", it means to re-add the element that is previously added and then removed, and restore its position.
* **[type]lupdate L id type value** : Update the *type* property with *value* for element *id* in list *L*.
* **[type]lrem L id** : Remove element *id* from the list *L*.