Austin's SWE Notes 😭

    Vector Clock

    Note that vector clock does not resolve conflict, it only used for conflict detection.

    In the case conflict happens, we have 2 options to resolve:

    1. Latest write win (problematic)
      1. System clock is not reliable, clock can Clock drift or skewed. Even using Network Time Protocol (NTP) we still have 10ms - 500ms inconsistency
      2. The only solution for it would be using TrueTime for true atomic clock. However complexity
    2. Return result back for user to resolve conflict (Safest)

    See: Merkle Tree vs Vector Clock

    Implementation

    Is a [server, version] pair with a data item $D$ to detect conflicts in a distributed system. For example a data item can look like this:

    D([S1, V1], [S2, V1], [S3, V2], ... [Sn,Vn])

    This means the data is distributed equally to different servers. Each server keeps track of a version of the data. In this case, our data $D$ was distributed in $n$ different server. In which in $S_1$ it has version 1, and in $S_3$ it was version 2 - which means was modified twice.

    Rules for writing data

    When writing data $D$ to the server Sx. The server must then increase its corresponding Vi for [Sx, Vi] if its exists. Otherwiese it should add a new entry.

    For example:

    1. Client write data D that handled by S1.
    2. S1 now add D as a vector clock with value D([S1,V1])
    3. Client read data D and write data D that again received by S1.
    4. S1 now increment its vector clock in D which results into D([S1,V2])
    5. Client read data D and write data D that received by S2.
    6. S2 now add D as a vector clock with value D([S1,V2], [S2, V1])

    Conflict detection

    In order to resolve a conflict, we need to start code our own client to do it. However, Vector Clock provides an easy way to detect confliction. A conflict happens if you can detect different in version if your ancestor (the previous change) vector's clock has any participant that greater than your current vector clock.

    For example, supposed we have

    D1([S0, 1], [S1, 2]) -> D2([S0, 2], [S1, 1])

    In this case, D1 is the parent of D2, we compare each element in D1 and make sure it's < than each corresponding element in D2.

    • [S0, 1] < [S0, 2]: No conflict
    • [S1, 2] > [S1, 1]: Conflict

    Therefore this 2 keypair in here is a conflicts. Of course now you need to know which one comes first. So in a real-world system, a timestamp or other criteria is necessary to be tie-breaking rule.

    Example

    Considering the following scenario:

    1. Client write data D that served by S1.
    2. S1 now add D as a vector clock with value D([S1,V1])
    3. Client write data D to the server.

    Now for whatever reasons, network partition happens and the servers are not able to talk to eachother

    1. S1 picks up the write and update D([S1, V2])
    2. S2 also picks up the write and update D([S1, V1], [S2, V1])

    Now network has been recovered. and the servers can talk to each other again.

    1. Client read D, however there is a conflict. Server doesn't know how to resolve this conflict and send both back to our client. Therefore our client see:
      • D([S1, V2]): value for the data is foo
      • D([S1, V1], [S2, V1]): value for the data is bar
    2. The client now needs to resolve this conflict. Let's supposed that the client decided to merge these changes and determined that the latest value is bar. We have the final value
      • D([S1, V2], [S2, V1]) with value bar
    3. This value is then sent to the server let's say S1 takes this value. This value is then get updated and store in the server:
      • D([S1, V3], [S2, V1]) with value bar

    Note

    • For DynamoDB, conflict resolvation decided to resolve when there is a client that reads the conflicted value. Otherwise, it stays conflicted — therefore eventually consistentcy

    • Due to the keypair [server, version] keeps growing, DynamoDB has set a threshold to remove the oldest pair when the size exceeded this limit. So far Amazon has not encountered any problem with this approach in production.

    Resources: Vector Clocks and Conflicting Data - Grokking the Advanced System Design Interview (designgurus.io)

    ← Unix
    Vertical Scaling →