5. Replication

5. Replication

Leaders and Followers

• synchronous replication

• asynchronous replication

• setting up new followers

  • take consistent snapshot of leader → pass to follower
  • follower connects to the leader and requests the changes after the snapshot

• leader failure: failover

  • HOW-TO

    • declare leader has failed(usually with timeout)
    • choose new leader: best candidate - node with latest data changes.
    • configure system with new leader. Let previous leader know he is not the leader anymore

  • problems

    • loss of data from previous leader
    • synchronizing with different storage system
    • two leaders at the same time
    • appropriate timeout for the declaration of leader's death

  • Implementation of replication log

    • statement-based
    • WAL(Write Ahead Log)
      • PostgreSQL, Oracle
      • low level - storage engine dependent
    • Logical log replication(row-based)
      • sequence of records describing writes to DB in row-level
        • insert : new value of column
        • delete : unique identifier of row
        • update : unique identifier, and new value
    • trigger based
      • big overhead

  • Problems of replication log

    • Read After Write Consistency
    • Monotonic Read : Do not read older value than previous read
    • Consistent Prefix Read : data read should appear in the same sequence with writes
    MultiLeader replication

  • Usecases

    • multi-datacenter
    • clients with offline operation
    • collaborative editing ex. google docs

  • Handling write conflicts

    • avoiding conflict

      • certain user writes to certain datacenter → not always the case

    • converging toward a consistent state

      • apply already codede script
      • read both values
      • automatifc conflict resolution
        • conflict-free replicated datatype
        • mergeable persistent data structure: three-way merge like git
        • operational transformation : algorithm

    • topology

      • circular : each write has tag

      • star

        • circular and star may fail if only one node fails.

      • all-to-all : result may be over taken

        Leaderless Replication

      • with coordinator node / or client write to several nodes

      • writing to DB when a node is down

        • write to/read from several nodes
        • read repair : when stale response is found, client writes back
        • anti-entropy process : on background, compare with other nodes

      • quorums for reading and writing

        • w + r > n
        • sloppy quorum: w and r may have nodes that are not included in n home nodes
        • hinted handoff: any writes that was temporarily accepted on behalf of another node are sent to the appropriate home node

      • detecting concurrent writes

        • not so much in database level. application developer should understand DB and handle them.
        Issues

      • last write wins

        • ambiguity of "recent"
        • only safe way of LWW is to use immutable, unique key like uuid

      • happens-before relationship

        • server and clients hold version number for every key.
        • when client reads, compare the version number with the previous read.
        • when server writes, write with new version number

      • version vector : collection of version number from multiple nodes