Decentralised systems - SwayDB

TimeOrder in SwayDB 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 - 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.

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.

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

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).

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).

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.

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. It is used by all Levels to execute non-blocking reads and it decouples reads from compaction i.e. if compaction is running on a Segment it does not block or lock reads.

TimeOrder's public API is pending test-cases.