Decentralised systems - SwayDB
Tags: distributedsystems, scala, java, database
Published: 2020-11-12 17:13:55

`TimeOrder` in [SwayDB](https://swaydb.simer.au/) can be used by decentralised systems for managing un-ordered writes and/or replication requests.  

Before going into details I will briefly explain the two types of `Ordering` in SwayDB.
- [KeyOrder](https://swaydb.simer.au/ordering-data/?language=scala) - Similar to any sorted collection type this simply orders data by key. Simple stuff!
- `TimeOrder` - Orders the sequence in which updates occur on a **single key**. 

## How is Time used?
`Time` is always stored with **each write** (even for range updates).

In the following example we've inserted `key1`  with value `1` at time `0`  and then updated the value by **incrementing** it by `5` first and then **multiplying** it by `10` which sets the final value to `(1 + 5) * 10 = 60`.

```scala
map.put(key = "key1", value = 1, time = 0)  
map.update(key = "key1", value = oldValue => oldValue + 5, time = 1)  
map.update(key = "key1", value = oldValue => oldValue * 10, time = 2)
```

If we were to submit the same updates in reverse order the final value would still be the same (`60`) since compaction applies these updates based on `time` and not the actual request order. 
```scala
map.update(key = "key1", value = oldValue => oldValue * 10, time = 2)
map.update(key = "key1", value = oldValue => oldValue + 5, time = 1)  
```
Without time, the above updates would've resulted in different final value of `1 * 10 + 5 = 15`  and not our intended `60`.

## How can it be used by decentralised systems?

I'm going to consider the use-case that writes can occur on any machine, at any time, for any key which may or may not be replicated to other machines. 

SwayDB's job is to ensure that writes by a decentralised system should eventually result in the same final value regardless of when a write or replication request was received by the machine. The only requirement is that each machine's SwayDB instance is initialised with the same `TimeOrder` function (documented below). 

`Time` is just a serialisable type so it can be any `class` with any number of fields. For our example we will use the following `CustomTime` class with two fields
 
```scala
case class CustomTime(machineId: Int,   
                      machineLocalTime: Long)
```
- `machineId` - unique ID assigned to each machine on boot that does not change even if the machine reboots.
- `machineLocalTime` - assigned to each write (put, update, remove, expire etc) initialised by each machine that creates the write request.

### Example write behaviour

Suppose **machine0** receives the following requests (in any order) that are replicated to **machine1** (in any order).
```scala
map.put(key = "key1", value = 1, time = CustomTime(0, 0))  
map.update(key = "key1", value = oldValue => oldValue + 5, time = CustomTime(0, 1))  
map.update(key = "key1", value = oldValue => oldValue * 10, time = CustomTime(0, 2))
```

And **machine1** receives the following requests (in any order) that are also replicated to **machine0** (in any order).
```scala
map.update(key = "key1", value = oldValue => oldValue - 10, time = CustomTime(1, 1))  
map.update(key = "key1", value = oldValue => oldValue * 20, time = CustomTime(1, 2))
```

**Expectation** - We want the final value of `key1` to be `(1 + 5 * 10 - 10) * 20 = 820` on both machines regardless of the order in which the request were received.

### Custom TimeOrder

We can achieve the above expectation with just the following `TimeOrder` function which orders writes by `machineId` first and then `machineLocalTime`. 
```scala
val customTimeOrder =  
  new TimeOrder[CustomTime] {  
    override def compare(left: CustomTime, right: CustomTime): Int =  
      if (left.machineId == right.machineId)  
        left.machineLocalTime compareTo right.machineLocalTime  
      else  
        left.machineId compareTo right.machineId  
  }
```

## API Status
Currently `TimeOrder` API is private to SwayDB's `core` and is enabled when functions are [turned on](https://swaydb.simer.au/api/pure-functions/?language=scala). It is used by all [Levels](https://swaydb.simer.au/implementation/level/?language=scala) to execute non-blocking reads and it decouples reads from compaction i.e. if compaction is running on a [Segment](https://swaydb.simer.au/implementation/segment/?language=scala) it does **not** block or lock reads. 

`TimeOrder`'s public API is pending test-cases.