Distributed Systems: Replication

If you are not doing replication, you are not fault-tolerant.

The more availability we want from replication, more work is required. The more consistent we want writes and reads to be, the more work is required.

Six consistency levels have varying cost in terms of performance and availability.

Guarantee	Consistency	Performance	Availability
Strong consistency	Excellent	Poor	Poor
Eventual consistency	Poor	Excellent	Excellent
Consistent prefix	Okay	Good	Excellent
Bounded staleness	Good	Okay	Poor
Monotonic reads	Okay	Good	Good
Read-your-writes	Okay	Okay	Okay

Different clients may require different levels of consistency guarantee while reading the same piece of data.

Baseball example

Say there is a baseball game on-going. There are two teams: (1) “visitors” (2) “home”. The game has seven innings. Each inning takes about fifteen minutes to complete. The two teams start with score 0-0. In one inning, the team “visitors” bat first until three outs happen, then the team “home” bat. The scores of the two teams are being kept in a key-value store with just two keys: (1) “visitors” (2) “home” like below:

kvs = {
    "visitors": 0,
    "home": 0
}

The game can be described like:

kvs.write("visitors", 0)
kvs.write("home", 0)
for inning in range(1, 8):
    outs = 0
    while outs < 3:
        visiting player bats
        for each run scored:
            score = kvs.read("visitors")
            kvs.write("visitors", score + 1)
    outs = 0
    while outs < 3:
        home player bats
        for each run scored:
            score = kvs.read("home")
            kvs.write("home", score + 1)

Say half of the seventh inning is done and the scores look like below:

Possible scores received by reads are different across consistency levels. The higher the number of possibilities, the lower is the guarantee.

Level	Possible scores	Observation
Strong consistency	(2, 5)	Latest score
Eventual consistency	Any of 18 mathematical possibilities: {0, 1, 2} X {0, 1, 2, 3, 4, 5}	May include fake scores or for multiple reads may give decreasing scores.
Consistent prefix	Any of 8 possible scores ever existed during the game: (0, 0), (0, 1), (1, 1), (1, 2), (1, 3), (2, 3), (2, 4), (2, 5)	No fake score but multiple reads can give decreasing scores.
Bounded staleness [bound = one-inning out-of-date]	(2, 3), (2, 4), (2, 5)
Monotonic reads [after reading (1, 3)]	(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5)	May give fake scores like (1, 4) but on multiple reads does not give decreasing scores.
Read-your-writes	For writer: (2, 5) For others: 18 mathematical possibilities {0, 1, 2} X {0, 1, 2, 3, 4, 5}	For the writer of the data, it works like strong consistency, for others it works like eventual consistency.

There are six roles who need to read the score.

Score-keeper

Per inning, below two reads:

score = kvs.read("visitors")
kvs.write("visitors", score + 1)

score = kvs.read("home")
kvs.write("home", score + 1)

Umpire

if first_half of last_inning:
    vscore = kvs.read("visitors")
    hscore = kvs.read("home")
    if vscore < hscore:
        end game

Radio-reporter

while True:
    vscore = kvs.read("visitors")
    hscore = kvs.read("home")
    report vscore and hscore
    if is_complete(game):
        break
    else:
        sleep(30 minutes)

Sportswriter

while not is_complete(game):
    drink beers
    smoke cigars
go to dinner
vscore = kvs.read("visitors")
hscore = kvs.read("home")
write article with vscore and hscore

Statistician

Say for “home” team:

wait until game is complete
score = kvs.read("home")
stat = kvs2.read("season-runs")
kvs2.write("season-runs", stat + score)

Stats-watcher

while True:
    stat = kvs2.read("season-runs")
    discuss stat with friends
    sleep(1 day)

Using strong consistency will work for all roles but they do not have to pay the cost. The sufficient consistency gurantees might be:

Role	Needed consistency
Score-keeper	Read-your-writes
Umpire	Strong consistency
Radio-reporter	Consistent prefix + monotonic reads
Sportswriter	Bounded staleness
Statistician	Strong consistency (kvs), read-your-writes (kvs2)
Stat-watcher	Eventual consistency

unreasonably effective