Please enable JavaScript.

Coggle requires JavaScript to display documents.

Replication - Coggle Diagram

- - - - Inter-region network delay is hidden from users -> ^ perceived performance
      - In case of leader failure reroute traffic to another region instead of failover
      - Better tolerance of network problems
    - - Much weaker consistency
      - Fundamental limitation of distr systems
  - - - Bidirectional for 2 leaders
      - All-to-all
        
        Every L sends Ws to every other L
        
        Better fault tolerance since allows for diff paths
      - More restricted
        
        Circular
        
        Each node receives Ws from 1 node and forwards all its + own Ws to 1 other node.
        
        Star
        
        1 root node forwards Ws to all other nodes
        
        In those 2 a write may need to go through several nodes before it reaches all replicas
        
        To avoid infinite replication/duplication each W is tagged with the ID of all nodes it has been written on.
    - - C and S
        
        1 node goes down the flow is broken and need to wait
        
        Reconfig done manually
      - All-to-all
        
        Some network links faster - some replication messages may "overtake" others -> wrong order of writes
        
        Use version vectors
  - - - Google Docs, Figma
      - Low latency
      - Multi-leader architecture (both online and offline)
      - App needs to receive changes from collaborators and merge them into the user's local file copy
      - Sync engine
        
        Software lib supports this
        
        Offline-first app - allows for offline editing
        
        Local-first software
        
        Also designed to continue working
        if all online services go down
        
        Pros
        
        Local data -> faster UI
        
        Some apps respond to user input in the next frame of the graphics system
        
        Available to work with while offline (treated like having a very ^ network delay
        
        Simplified frontend model allows for more declarative programming style
        
        Allows when combined with reactive programming to display edits from other users in real time
        
        Cons
        
        Not suitable if user has access to a ^^ amount of data
        
        Reverse of the dominant way of building apps : You have persistent state on the client and server is moved into a bg process
  - - - Not possible for sync engines
    - - Each write has timestamp
      - Use the value with the most recent one
      - If have same timestamp predefine rules
      - Ensures eventual consistency at the cost of data loss
      - If data loss is unacceptable this approach won't cut it
      - Real-time clocks
        
        Problems
        
        Drift accumulation
        
        Jumps bw
        
        Skew issues
        
        Use Logical clock
    - - In the context of a DB impractical to stop entire repl. process until a human resolves it
      - DBs store all concurrently written values / siblings
      - Next time you query that record DB returns all of them and prompts you to resolve them
      - Problems
        
        The API of the DB changes - data fields changes may make data work to become awkward
        
        User has a lot of work
        
        Merging siblings automatically can lead to surprising behavior if it is not done carefully
        
        Concurrent merges may result in another more-complicated
        conflict
    - - Ensures all replicas have same state regardless of order in which Ws occurred
      - Eventual consistency + convergence guarantee = strong eventual consistency
      - Depending on the type of data being modified we can provide different rules for resolution that ensure minimum problems
      - The best way for many apps
      - Algorithms
        
        CRDTs
        
        Conflict-Free Replicated Datatypes
        
        Found in distr DBs such as Redis Enterprise and Riak
        
        OT
        
        Operational Transformation
        
        Most often used for real-time collab editing of text
- - - - Client sends R to several nodes in parallel
      - Compares their version numbers or timestamps
    - - Read repair
      - Hinted handoff
        
        Another replica stores writes on its behalf in the form of hints
      - Anti-entropy
        
        Significant delay
  - - - If w < n we can still process writes if a node is unav
      - If r < n we can still process reads if a node is unav
      - If n = 10, r = 6, w = 6 we can tolerate 4 unav nodes
      - If fewer than needed are available return an error
      - If w + r > n we can tolerate n / 2 unav nodes
        
        Smaller than
        
        More likely to serve stale data
        
        Lower latency
        
        Not always returns latest value
  - - - Sends the W to a node in its local region (coordinator node)
      - Coordinator node propagates the W to all replicas in its own region and to 1 replica in every other region which does the same
  - - - No causal dependency between the operations
      - Both nodes are unaware that the other one is attempting
        to W to the same key
      - Capturing the happens-before relationship
        
        Algorithm
        
        Every key stores a version number assigned by the server along with its value
        
        It's incremented on every W
        
        When a R is requested the server returns all siblings + the latest version number
        
        Upon W the client merges the prior values in the ver. n. along with incrementing the current one
        
        When server receives the W it overwrites all values that have ver. n. lower than the received one but keeps the higher versions (they're concurrent with this one)
    - - Needed when multiple replicas accept Ws
      - We need a ver n per replica and per key
      - The collection of ver n from all the replicas
        that have edited a part. key
      - Very similar to vector clocks
- - - - Locking the DB is bad for availability
      - Steps:
        
        Take a snapshot of leader's DB
        
        Or use an archived repl. log from the object store
        
        Copy snapshot to new foll. node
        
        Foll req from leader all changed data since snapshot
        
        Need exact position in the leader's replication log
        
        Log sequence number
        
        Binlog coordinates
        
        Global transaction identifiers
        
        Follower's caught up
  - - - Obj storage is inexpensive compared to other cloud storage
      - Obj stores have multi-region replication w/ ^^ durability guarantees -> DB bypasses inter-zone network fees
      - DBs can use obj store's conditional write feature (compare-and-set(CAS) operation) to implement transactions and leadership election
      - Storing data from mult. DBs in same obj store simplifies data integration
    - - Much higher latency
      - Many providers charge per-API call which forces systems to batch R and W to reduce cost -> ^ latency
      - Objects are immutable -> random Ws are ^^^ resource-intensive op
      - Many obj stores don't offer standard filesystem interfaces
- - - - Most times changes propagate in less than second
      - No guarantee how long it would take
      - If problems arise it might take many mins
    - - Leader crashes -> promote replica will have latest data
      - Followers will always have the latest data
    - - -> Impractical for all followers to be sync
  - - - Eventual consistency
      - Systems using consensus protocol for leader election
- - - - L may've del its prev log
        
        Has to fetch from object storage backup
        
        In order to save space
      - Both leader and follower can exp. high load during recovery
  - - - 1 of the folls needs to be promoted as the new leader
      - Clients to be reconfig. to send Ws to the new leader
      - Other folls need to start consuming data changes from new leader
    - - Determine leader has failed. E.g. 30s no responses
      - Choose a new leader
        
        Leader election
        
        By a controller node
        
        Best cand. is most up-to-date node
        
        Replica with highest log-sequence number
      - Reconf. sys to recogn new L
        
        That includes the old leader if and when it comes back
    - - No durability
        
        New async repl. L may not have latest data
        
        When old one comes back discard the lost writes to avoid conflicts
      - Discarding Ws really dangerous if other storage syss outside of the DB need to be coordinated with the DB contents
      - Split brain
        
        Shut down one node
        
        Careful not to shut down both
        
        Risk of corrupted data
        
        Fencing
        
        Limiting/Shutting down old leaders
      - Tricky to figure out perfect timeout for declaring leader dead
        
        Too short = unnecessary failovers which are fatal comb. with already high load
        
        Too long = longer time to recover
- - - - A problem with async replication
        
        Reads from stale replica
        
        User makes a write
      - Read from leader or sync updated foll
      - Otherwise read from async updated foll
      - Simple rule: always read user's own profile/data from leader, and others' data from a foll
      - For lots of editable user data, R from L updates only from last 1 minute and prevent R from F if repl lag is larger than 1 min
      - Client tracks most recent W tmstmp
        and compares to replica's repl log's last W
        
        Wait
        
        Route to another replica
      - If replicas are dist across regions req routes to L's region
      - If user has multiple devices MD needs to be centralized
        (Cross-device R-a-W consistency)
      - Monotonic reads
      - Read-your-writes
        (read-after-write) consistency
    - - Consecutive Rs hit diff replicas
      - 2nd replica is lagging more than 1st one
      - Solved with monotonic reads
        
        < strong consistency * > eventual consistency
        
        Read from same replica
    - - Can R events in wrong order (folls have diff lag)
      - Solved through consistent prefix reads
        
        Any Ws that are causally related to each other are W on same shard
      - Diff shards operate independently -> no global ordering of Ws
    - - Using DBs that provide strong consistency
        
        Linearizability
        
        ACID transactions
        
        NewSQL
        
        SQL
        
        Strong consistency, high availability and fault tolerance
- - - - If statement calls a nondeterministic func its results will most likely differ on each replica
      - If autoincrement is used each statement must be executed in the same order on each replica - limiting when there are mult. conc. executing transactions
      - Statements having side effects may result in diff side effects occuring on each replica
    - - Make transactions deterministic
      - When leader calls a nondeterministic function it should write in the log the result of the operations
  - - - PostgreSQL
      - Oracle
    - - Data is logged at a very low level - which bytes were changed in which disk block -> replication tightly coupled to the storage engine
      - For that reason upgrades require downtime as follower with new software version/storage format change can't happen without leader being down
  - - - For inserting a row, the log contains the new values of all columns
      - For updating or deleting the row specifies enough info to identify it
      - Transaction modifying multiple rows creates a record for each row