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.
Top comments (0)