Replication

Question 1

What are the three main Leader based approaches for replicating changes between nodes?

Answer 1

Single-Leader, Multi-Leader, and Leaderless replication.

Question 2

What is a reason to replicate data?

Answer 2

To keep data geographically close to your users.

Question 3

What is a reason to replicate data?

Answer 3

To allow the system to continue working even if some of its parts have failed.

Question 4

What is a reason to replicate data?

Answer 4

To scale out the number of machines that can serve read queries (and thus increase read throughput).

Question 5

What are other terms for leader-based replication?

Answer 5

Active-Passive or Master-Slave replication

Question 6

How is the data exchanged from the user in leader-based replication?

Answer 6

One replica is designated the leader. Clients must send all write requests to the leader. The leader write that data to its local storage and then sends the data change to all of its followers as part of a replication log. Each follower takes the log from the leader and updates its local copy of the databse accordinly by applying all writes in the same order as the leader.

Question 7

What is the advantage of synchronous replication?

Answer 7

All followers are guaranteed to have and up-to-date copy of the data that is consistent with teh leader. If the leader suddenly fails we can be sure the data is still available to the on the follower.

Question 8

What is the disadvantage of synchronous replication?

Answer 8

If any synchronous follower doesn’t respond for any reason, the write cannot be processed and hte leader must block all writes and wait until the synchronous replica is available again.

Question 9

Is leader-based replication usually configured to be synchronous or asynchronous?

Answer 9

Asynchronous

Question 10

Why aren’t writes durable in asynchronous replication?

Answer 10

If the leader fails and is not recoverable, any writes that have not yet been replicated to followers are lost. This means that a write is not guaranteed to be durable to a client even after it has been confirmed. (However a fully asynchronous configuration can allow for the leader to continue processing writes even if all of its followers have fallen behind.

Question 11

How to set up new followers?

Answer 11

1. Take a snapshot of leasder’s database at some pont in time (without taking a lock on entire DB if possible).
2. Copy teh snapshot to the new follower node.
3. The follower connects to the leader and requests all data changes that have occurred since snapshot was taken.
4. When the follower has processed the backlog of data changes it can then continue to process changes from the leader as they happen.

Question 12

Follower Failure: Catch-up Recovery

Answer 12

Each follower keeps a log of data change it has received from the leader. If network is interrupted or a follower crashes it can request all data changes since the last transaction before it disconnected and it can get caught up. Once caught up it can continue receiving a stream of data changes as before.

Question 13

What is Failover?

Answer 13

The process that occurs confugring (sending all write requests and having other followers start consuming changes from new leader) a new leader to when the current leader fails.

Question 14

What are the three steps that occur during the Automatic Failover process?

Answer 14

1. Determining that the leader has failed.
2. Choosing a new leader.
3. Reconfiguring the system to use the new leader.

Question 15

How to determine when a leader has failed? (Failover Step 1)

Answer 15

There is no foolproof way of detecting what has gone wrong so most systems use a timeout. Nodes frequently send messages between one another and if a node doesn’t respond for a period of time it is assumed to be dead. (Gossip Protocol)

Question 16

How to choose a new leader? (Failover step 2)

Answer 16

This could be done through an election process (Consensus) or a new leader can be appointed by a previously elected controller node. The best candidate for leadership is usually the replica with the most up-to-date changes from the old leader.

Question 17

What needs to happen to reconfigure a system to use a new leader? (Failover step 3)

Answer 17

Clients need to send all write requests to the new leader (Request Routing), have all followers now follow the new leader, and take precautions if the old leader comes back and still thinks it is the current leader.

Question 18

What are some issues that an occur in failover?

Answer 18

1. new leader may have not received all the writes form old leader before it failed (only in asynchronous replication).
2. Two nodes both believe they are the same leader (Split Brain).
3. Having a timeout that is too short (unnecessary failovers) or too long (longer time to recovery).

Question 19

What are the four implementations of Replication Logs?

Answer 19

1. Statement-based replication
2. Write-ahead log (WAL) shipping
3. Logical (row-based) log replication
4. Trigger-based replication

Question 20

How does statement-based replication work?

Answer 20

The leader logs every write request that it executes and sends it to its followers. Ex: For a relation database every INSERT, UPDATE, or DELETE statement gets sent.

Question 21

Issues with statment based replication

Answer 21

• Any statement that calls nondeterministic funtion such as NOW() or RAND() could generate a different value.
• If statments use autoincrementing columns or depend on existing data in the DB they must be executed conurrently which could be hard with multiple concurrently executing transactions.
• Since there are so many edge cases other repliation methods are generally preferred

Question 22

How does Write-ahead log shipping work?

Answer 22

The log is an append-only sequence of bytes containing all writes to the DB. We can use the exact same log to build a replica on another node. When follower processes this log it build a copy of the exact same data strucutre as found on the leader (B-Tree, SSTables and LSM-Trees).

Question 23

How does Logical (row-based) log replication work?

Answer 23

A sequence of records describing writes to database tables at the granularity of a row (which allows the log to be decoupled from the storage engine internals). A transaction that modified several rows generates several such log records followed by a record indicating the transaction was committed. This process allows for different versions or entire storage engines and is easier for backward compatibility.

Question 24

How doe Trigger-based replication work?

Answer 24

Occurs in the appication layer instead of being implemented by the DB system. A trigger lets you register custom application code that is automatically executed when a data change occurs in a DB system. A change is logged in a separate table that an external process can read and apply any necessary changes to another system.

Question 25

3 Main Issues with Replication Lag

Answer 25

1. If the user views data shortly after making a write the new data may not have reached the replica. (Reading your own writes)
2. It’s possible for a user to see things moving backward in time due to reading from different replicas (Monotonic Reads).
3. No global ordering of writes so some so users may see some parts of the DB in an older state and some in newer state. (Consistent-Prefix Reads)

Question 26

What is Reading Your Own Writes

Answer 26

It provies read-after-write consistency. A guarantee that if user reloads a page they will always see any updates they committed themselves.

Question 27

What are 3 Techniques for implementing Read-After-Write Consistency?

Answer 27

• Only read information that could be modified by the user from the leader (Ex: Users Profile information reads from leader and all other profiles read from replicas)
• Client can remember timestamp from most recent write and system can ensure the replica serving any reads for that user refelcts updates at least until that timestamp
• Might also need to account for multiple DCs and routing necessary reads to the leader which requires additional complexity (Also handle reqs from different device types)

Question 28

What are Monotonic reads?

Answer 28

A lesser guarantee than strong consistency but a stronger guarantee than eventual consistency that when a user reads data they may see an old value, but if they make several reads in a sequence they won’t see time go backward (see reads that were even older than the previous read).

Question 29

How are Monotonic Reads achieved?

Answer 29

By making sure that each user always makes their reads from the same replica. Ex: The replica can be chosen based on a hash of the user ID rather than randomly.

Question 30

What are Consistent-Prefix Reads?

Answer 30

A guarantee that says if a sequence of writes happens in a certain order, then anyone reading those writes will see them appear in the same order. (Particularly important in Partitioned/Sharded DBs).

Question 31

What are other names for Multi-Leader Replication?

Answer 31

Master-Master or Active-Active replication. This is because each leader simultaneously acts as a follower to the other leaders.

Question 32

What are three possible solutions to replication lag?

Answer 32

1. Reading your own writes / read-after-write consistency
2. Monotonic Reads
3. Consistent Prefix Reads

Question 33

In what situation does it rarely make sense to use Multi-Leader replication?

Answer 33

When you are only using a single datacenter, because the benefits rarely outweigh the added complexity.

Question 34

What are the three use cases for Multi-Leader Replicaton?

Answer 34

1. Multi-datacenter operation
2. Clients with offline operation
3. Collaborative Editing

Question 35

Single-Leader vs Multi-Leader Performance in multi-datacenter deployment

Answer 35

In single-leader configuration every write must go over the inernet to the DC with the leader. In multi-leader every write can be processed in the local DC and is replicated asynchronously to the other datacenters which hides network delay from the user
(the perceived performance may be better).

Question 36

Single-Leader vs Multi-Leader Tolerance of DC outages

Answer 36

In single-leader configuration if the DC with the leader fails failover promotes new leader in another DC, but in multi-leader each DC can continue operating independently of hte others and replication catches up once the DC is back online.

Question 37

Single-Leader vs Multi-Leader Tolerance of Network Problems in a Multi-Datacenter environment

Answer 37

Single-leader configuration is sensitive to problems in inter-datacenter link because writes are made synchronously over this link. Multi-leader with asynchronous replication can usually tolerate network problems better.

Question 38

What is the biggest problem with multi-leader replication?

Answer 38

Deciding how to handle write conflicts between two leaders.

Question 39

Synchronous vs Asynchronous Conflict Detection

Answer 39

In single-leader teh second writer will either block and wait or abord the second write transaction forcing the user to retry the write. In multi-leader both writes are successful and conlict is detected asynchronously at some point later.

Question 40

Is it a good idea to make the conflict detection synchronous? (Wait for write to be replicated to all replias before telling the user that the write was successful.)

Answer 40

No, by doing this you lose the main advantage of multi-leader replication: allowing each replica to accept writes independently. For synchronous conflict detection you might as well use single-leader replication.

Question 41

What is the recommended approah to handling write conflicts in a multi-leader environment?

Answer 41

Conflict Avoidance. Since most multi-leader impementations are bad at handling write conflits it’s best to avoid them. Ex: Ensure that requests from a particular user are always routed to hte same DC and use the leader in that DC for reading and writing. From the user’s POV the configuration is essentially single-leader.

Question 42

What are options for custom conflict resolution logic?

Answer 42

1. On Write - when the DB detects a conflicts in log of repicated changes it calls a conflict handle to pick the proper value ( Ex: use a UUID, timestamp, hash value and pick the highest one)
2. On Read - When a conclit is detected all the conflicting writes are stored and next time the data is read these values are returned to the application and the user can be prompted to select the appropriate value.

Question 43

3 Most Common Multi-Leader Replication Topologies

Answer 43

Circular, Star, and All-to-All

Question 44

What is the main issue with Star and Circular topologies?

Answer 44

If one node fails it can interrupt the flow of replication messages between other nodes causing them to be unable to communicate until the node is fixed. (Tere is a Single Point of Failure)

Question 45

What is a major issue with all-to-all topologies?

Answer 45

There can be a problem of causality where some nodes receive updates in a different order than others. This could be due to a difference in speed between network links.

Question 46

How does leaderless replication handle node outages?

Answer 46

It doesn’t because failover does not exist. As long as the minimum amount of replicas respond with an OK the client’s write is successful. When the failed node(s) is back online it will receive multiple responses for a read and can use versioning numbers to know which is the most updated write to avoid any stale data.

Question 47

In leaderless environments how does a node catch up on missed writes after it comes back online?

Answer 47

Two mechanisms are often used:

1. Read Repair
2. Anti-Entropy Process

Question 48

How does read repair work in leaderless environments?

Answer 48

When a client makes a read from several nodes in parallel, it can detect any stale responses. This approach works well for values that are frequenly read.

Question 49

How does anti-entropy process work in leaderless environents?

Answer 49

Some datastores have a background process that constantly looks for differences in the data between replicas and copies any missing data from oen replica to another.

Question 50

How do Quorums work for reading and writing in leaderless environments?

Answer 50

If there are n replicas then every write must be confirmed by w nodes and we must query r nodes for every read. As long as r + w > n wer’re good.

Question 51

How are n, r, and w usually configured when using quorums?

Answer 51

Typically n is an odd number w = r = (n+1) / 2. A workload with few writes an many reads would benefit from setting w = n and r = 1. (This could be a disadvantage though since just one failed node causes all writes to fail).

Question 52

Limitations of Quorum Consistency

Answer 52

• You also could have issues with a sloppy quorum
• Two writes occur concurrently as it is not clear which happened first.
• Node carrying a new value fails and its data is restored from replica carrying an old value
• If a write happens concurrently with a read

Question 53

What is a sloppy quorum and hinted handoff?

Answer 53

In a large cluster it’s likely a client can connect to some database nodes during the interruption but not the nodes to assemble a quorum for a particular value. Designers choose to accept writes anyway and write them to some nodes that are reachable but aren’t among the n nodes on which the value usually lives. Once network is fixed any writes that one node temporarily accepted are sent to the appropriate “home” nodes (Hinted Handoff).

Question 54

Are there any benefits to sloppy quorums?

Answer 54

Yes, that are particularly useful for increasing write availability: as long as any w nodes are available the DB can accept writes. This means that you can’t be guaranteed to ever read current data. More of an assurance of durability than an actual quorum.

Question 55

Quorums In Multi-Datacenter Operations

Answer 55

Number of replicas n includes nodes in all DCs. Each write from a client is sent to all replicas regardless of DC but client usually only waits for the ACK from a quorum of nodes within its local DC so it’s unaffected by delays and interruptions on the cross-datacenter link.

Question 56

How does leaderless environments handle concurrent writes?

Answer 56

Last Write Wins is the approach of making each replica only store the most “recent” value as long as there is a way to dtermine which write is more “recent” each write will be eventually copied to every replica and all replicas will eventually converge to the same value. (Cassandra)

Merging Concurrently Written Values where you take the union (shopping card) or just include extra code in the application to handle this.

Question 57

Because of the problems with clocks in distributed systems how can we determine where two events were concurrent or which event came first?

Answer 57

Using Version Vectors and the properties of causality (An operation A happens before another operation B if B knows about A or depends on A or builds upon A in some way).

Question 58

How do Version Vectors (Vector Clocks, Lamport Timestamp) work?

Answer 58

It’s a data structure used for determining the partial ordering of events in a distributed system and detecting causality violations. We use a vesion number per replica as well as per key. Each replica increments its own version number when processing a write and also keeps track of the version numbers it has seen from each of the other replicas. This information indicates which values to overwrite and which values to keep as siblings.

Question 59

What is the algorithm for Vector Clocks?

Answer 59

Initially all clocks are zero.

Each time a process experiences an internal event, it increments its own logical clock in the vector by one.

Each time a process sends a message, it increments its own logical clock in the vector by one (as in the bullet above, but not twice for the same event) and then sends a copy of its own vector.

Each time a process receives a message, it increments its own logical clock in the vector by one and updates each element in its vector by taking the maximum of the value in its own vector clock and the value in the vector in the received message (for every element).