designing_data_intensive_applications/ch05

ch05

dz / designing_data_intensive_applications / ch05

Summary

Chapter 5: Replication

Node Tree

Nodes

replication
content replication
children chain_repl, consensus, copy_data_multi_machines_networked (description), detecting_concurrent_writes, eventual_consistency, guarantees, handling_data_changes, leaderless_replication, monitoring_staleness, multi_leader_replication, replica, sync_async

handling_data_changes
content Handling changes to data
children btwn_nodes
parents replication

copy_data_multi_machines_networked
content Keep copy of the same data on multiple machines, connected via a network
parents replication

sync_async
content Synchronous vs Asynchronous
children async, sync
parents replication

sync
content synchronous
children guaranteed_up_to_date, unresponsive_follower_blocks
parents sync_async

async
content asynchronous
children semi_sync, usually_async
parents sync_async

eventual_consistency
content Eventual Consistency
children guarantee_less_strong_greater_eventual
parents replication, read_scaling_arch

btwn_nodes
content Between Nodes
children leaderless, multi_leader, single_leader
parents handling_data_changes

single_leader
content Single Leader
parents btwn_nodes, second_write_blocks

multi_leader
content multi-leader
parents btwn_nodes

leaderless
content Leaderless
parents btwn_nodes

guarantees
content guarantees
children monotonic_reads, read_your_writes
parents replication

read_your_writes
content read-your-writes
parents guarantees, read_after_write_consistency

monotonic_reads
content monotonic reads
children guarantee_less_strong_greater_eventual, moving_backwards_in_time (monotonic reads prevent this)
parents guarantees

replica
content Replica
children ensure_data_on_all_reps
parents replication

ensure_data_on_all_reps
content How to ensure data ends up on all replicas?
children leader_based_replication (solution)
parents replica

leader_based_replication
content Leader-based replication
children LBR_lag_metrics, designated_leader, follower, handling_node_outage, read_after_write_consistency, read_scaling_arch, replication_lag, replication_methods, usually_async
parents ensure_data_on_all_reps

designated_leader
content Designated leader/primary/master
children client_reads, client_write_sent_to_leader
parents leader_based_replication

follower
content Followers/read replicas/slaves/secondaries/hot standby
children client_reads, new_follower, sends_data_to_reps, unresponsive_follower_blocks
parents leader_based_replication

client_write_sent_to_leader
content Client write requests sent to leader
children client_reads, leader_only_writes, write_local_storage
parents designated_leader

write_local_storage
content Write to local storage
children sends_data_to_reps (then)
parents client_write_sent_to_leader

sends_data_to_reps
content Sends data changes to other replicas
children replication_log
parents follower, write_local_storage

replication_log
content Replication Log / Change Stream
parents sends_data_to_reps

leader_only_writes
content Client write queries only accepted by leader
parents client_write_sent_to_leader

client_reads
content Client Reads: query leader or followers
parents client_write_sent_to_leader, follower, designated_leader

guaranteed_up_to_date
content guaranteed to have up-to-date copy
parents sync

unresponsive_follower_blocks
content Unresponsive follower doesn't process write, blocks all writes
children only_one_sync_follower (mitigation)
parents follower, sync

only_one_sync_follower
content Only one synchronous follower
children semi_sync (terminology)
parents unresponsive_follower_blocks

semi_sync
content semi-synchronous
parents async, only_one_sync_follower

usually_async
content Usually asynchronous
parents async, leader_based_replication

new_follower
content New Follower setup
children db_snapshot
parents follower

db_snapshot
content Database Snapshot (from leader)
children log_seq_num
parents new_follower

log_seq_num
content Log Sequence Number/binlog coordinates
children caught_up, changes_since_snap
parents db_snapshot

changes_since_snap
content Changes Since Snapshot
parents log_seq_num

caught_up
content Caught Up
parents log_seq_num

chain_repl
content Chain replication
parents replication

consensus
content Consensus
parents replication

handling_node_outage
content Handling node outage
children follower_failure, leader_failure
parents leader_based_replication

follower_failure
content follower failure
children leader_failure (Trickier), recover_from_log
parents handling_node_outage

recover_from_log
content Recover From Log
parents follower_failure

leader_failure
content Leader Failure
children failover
parents handling_node_outage, follower_failure

failover
content Failover
children automatic_failover, select_follower_become_leader (description)
parents leader_failure

select_follower_become_leader
content Selecto Follower to become leader
parents failover

automatic_failover
content Automatic Failover
children things_that_go_wrong
parents failover

things_that_go_wrong
content things that go wrong
children discarded_writes, split_brain, unnecessary_failover
parents automatic_failover

split_brain
content Split Brain
parents things_that_go_wrong

discarded_writes
content Discarded Writes
parents things_that_go_wrong

unnecessary_failover
content Unncessary Failover (timeout too small)
parents things_that_go_wrong

replication_methods
content Replication Methods
children logical_log, statement_based, trigger_based, wal_shipping
parents leader_based_replication

trigger_based
content Trigger-Based Replication
parents replication_methods

statement_based
content Statement-based Replication
parents replication_methods

logical_log
content Logical Log
children decouple_log_from_storage
parents replication_methods

wal_shipping
content WAL Shipping
parents replication_methods

read_scaling_arch
content Read Scaling Architecture
children eventual_consistency
parents leader_based_replication

decouple_log_from_storage
content Decouple replication log from storage engine
parents logical_log

read_after_write_consistency
content Read after write consistency
children cross_device_RAW, read_your_writes (AKA)
parents leader_based_replication

cross_device_RAW
content cross device read-after-write consistency
parents read_after_write_consistency

replication_lag
content Replication lag
children transactions, violations_of_causality
parents leader_based_replication

moving_backwards_in_time
content Moving backwards in time
parents monotonic_reads

guarantee_less_strong_greater_eventual
content Lesser guarantee than strong consistency. Stronger guarantee than eventual consistency
parents monotonic_reads, eventual_consistency

violations_of_causality
content Violations of Causality
children consistent_prefix_reads (solution), network_messages_overtake (causality problem)
parents replication_lag

consistent_prefix_reads
content consistent prefix reads
children users_see_data_in_state_that_makes_sense (description that popped up in summary of chapter), write_seq_order_read_order
parents violations_of_causality

write_seq_order_read_order
content If sequence of writres happen in certain order, anyone reading those writes will read them in same order
parents consistent_prefix_reads

transactions
content transactions
children dont_think_replication_lag
parents replication_lag

dont_think_replication_lag
content Designed so that programmers don't have to think about replication lag.
parents transactions

multi_leader_replication
content Multi-leader replication
children clients_offline_operation, collab_editing, handling_write_conflicts, more_than_one_node_writes, multi_datacenter_operastion, replication_topology, same_as_conflict_resolution
parents replication

more_than_one_node_writes
content More than one node can accept writes
parents multi_leader_replication

multi_datacenter_operastion
content Multi Datacenter Operation
parents multi_leader_replication

clients_offline_operation
content Clients with offline operation
parents multi_leader_replication

collab_editing
content Collaborative Editing
parents multi_leader_replication

handling_write_conflicts
content Handling Write Conflicts
children auto_conflict_resolution, avoiding_conflicts, convergence_consistency, same_as_conflict_resolution, write_async, write_sync
parents multi_leader_replication

write_sync
content Synchronous Writes
children second_write_blocks, wait_for_write_before_success
parents handling_write_conflicts

write_async
content Asynchronous Writes
children accepts_writes_independently
parents handling_write_conflicts

second_write_blocks
content Second write: block and wait, or abort
children single_leader
parents write_sync

accepts_writes_independently
content Accepts writes independently
children defeats_multi_leader_advantage (by contrast, asynchronous works better with MLR)
parents write_async

wait_for_write_before_success
content Wait for write to be replicated before success
children defeats_multi_leader_advantage
parents write_sync

defeats_multi_leader_advantage
content Defeats advantage of multi-leader replication
parents accepts_writes_independently, wait_for_write_before_success

avoiding_conflicts
content Avoiding Conflicts
children particular_record_writes_same_leader
parents handling_write_conflicts

particular_record_writes_same_leader
content Ensure all writes for a particular record go through the same leader
children breaks_when_leader_changes
parents avoiding_conflicts

breaks_when_leader_changes
content Breaks down when leader changes
parents particular_record_writes_same_leader

convergence_consistency
content Convergence Towards Consistency
children last_write_wins
parents handling_write_conflicts

last_write_wins
content Last Write Wins
children discards_concurrent_writes
parents convergence_consistency

auto_conflict_resolution
content Automatic Conflict Resolution
children CRDT, mergeable_persistant_data_structs, operational_transformation
parents handling_write_conflicts

mergeable_persistant_data_structs
content Mergeable Persistant Data Structures
parents auto_conflict_resolution

CRDT
content Conflict-free Replicated Data Types (CRDT)
parents clients_merging_concurrent_vals, auto_conflict_resolution

operational_transformation
content Operational Transformation
parents auto_conflict_resolution

replication_topology
content Replication Topology
children all_to_all, circular_topology, star_topology
parents multi_leader_replication

all_to_all
content All to all
children common_topology, every_leader_writes_every_leader (description), fault_tolerant, network_messages_overtake
parents replication_topology

every_leader_writes_every_leader
content Every leader sends writes to every other leader
parents all_to_all

fault_tolerant
content Fault Tolerant
children one_failure_interrupts_writes (not fault tolerant)
parents all_to_all

common_topology
content Most common topology used
parents all_to_all

circular_topology
content Circular Topology
children mysql_default, one_failure_interrupts_writes, one_node_receive_forward_another (description)
parents replication_topology

mysql_default
content MySQL default
parents circular_topology

one_node_receive_forward_another
content Receives writes from one node, forwards writes to another node
parents circular_topology

star_topology
content Star Topology
children designated_node_writes (description), one_failure_interrupts_writes
parents replication_topology

designated_node_writes
content One designated root node writes to all other nodes
parents star_topology

one_failure_interrupts_writes
content One node failure can interrupt write flows
parents circular_topology, star_topology, fault_tolerant

network_messages_overtake
content Some network links may be faster, messages may overtake others
parents violations_of_causality, all_to_all

leaderless_replication
content Leaderless replication
children dynamo_style (AKA), failover_does_not_exist, quorum_reads_writes, write_implementations
parents replication

dynamo_style
content Dynamo-style
parents leaderless_replication

write_implementations
content Write Implementations
children client_writes_directly, coordinator_node
parents leaderless_replication

client_writes_directly
content client writes directly to several replicas
children parallel_read_requests
parents write_implementations

parallel_read_requests
content Parallel Read Requests
parents client_writes_directly

coordinator_node
content Coordinator node, manages writes to replicas on behalf of client
parents write_implementations

failover_does_not_exist
content Failover does not exist
children potentially_stale_data
parents leaderless_replication

potentially_stale_data
content Potentially stale data
children node_catch_up_missed_writes, read_requests_parallel
parents failover_does_not_exist

read_requests_parallel
content Read requests sent to many nodes in parallel
parents potentially_stale_data

node_catch_up_missed_writes
content how does node catch up on missed writes?
children anti_entropy_process, read_repair
parents potentially_stale_data

read_repair
content Read Repair
children versions
parents node_catch_up_missed_writes

versions
content Versions
children version_number_per_replica ([I think this connection makes sense?])
parents read_repair

anti_entropy_process
content anti-entropy process
children background_process_differences_replicas (description)
parents node_catch_up_missed_writes

background_process_differences_replicas
content Background process that looks for differences between replicas
parents anti_entropy_process

quorum_reads_writes
content Quorum reads and writes
children assurance_of_durability, sloppy_quorum, w_plus_r_greater_n
parents leaderless_replication

w_plus_r_greater_n
content w + r > n
children accept_writes_reachable_nodes_atypical (the "n" in this equation), n3w2r2_one_unavail, n5w3r3_two_unavail, n_w_r, r_less_n_still_reads, smaller_wr, w_less_n_still_writes
parents quorum_reads_writes

w_less_n_still_writes
content if w < n, can still process writes if node is unavailable
parents w_plus_r_greater_n

n_w_r
content n replicas, w successfully confirmed writes, at least r nodes queried for each read
parents w_plus_r_greater_n

r_less_n_still_reads
content if r < n, can still process reads if node is unavailable
parents w_plus_r_greater_n

n3w2r2_one_unavail
content n=3, w=2, r=2 can tolerate one unavailable node
children n5w3r3_two_unavail
parents w_plus_r_greater_n

n5w3r3_two_unavail
content n=5, w=3, r=3 can tolerate two unavailable nodes
parents w_plus_r_greater_n, n3w2r2_one_unavail

smaller_wr
content w+r < n stale values more likely, but lower latency and higher availablility
children stale_possible_for_greater_n
parents w_plus_r_greater_n

stale_possible_for_greater_n
content stale is also possible for w+r > n in certain situations
parents smaller_wr

monitoring_staleness
content Monitoring staleness
children LBR_lag_metrics, leaderless_more_difficult
parents replication

LBR_lag_metrics
content Leader-based replication: uses metrics for the replication lag
parents leader_based_replication, monitoring_staleness

leaderless_more_difficult
content Leaderless: more difficult
parents monitoring_staleness

assurance_of_durability
content Quorum is an assurance of durability
parents quorum_reads_writes

sloppy_quorum
content Sloppy Quorum
children accept_writes_reachable_nodes_atypical, not_in_designated_home_nodes
parents quorum_reads_writes

accept_writes_reachable_nodes_atypical
content Accepts writes, write to reachable nodes where value doesn't typically live (not in "n")
parents sloppy_quorum, w_plus_r_greater_n

not_in_designated_home_nodes
content Nodes not in designated "home" nodes
children hinted_handoff
parents sloppy_quorum

hinted_handoff
content Hinted Handoff
children temp_values_sent_home (description)
parents not_in_designated_home_nodes

temp_values_sent_home
content Temporarily accepted values on node sent to "home" node when it comes back online
parents hinted_handoff

detecting_concurrent_writes
content Detecting Concurrent Writes
children happens_before
parents replication

discards_concurrent_writes
content Discards concurrent writes
parents last_write_wins

happens_before
content Happens-before
children clients_merging_concurrent_vals, happens_before_AB_combos
parents detecting_concurrent_writes

happens_before_AB_combos
content A happens before B, B happens before A, A and B are concurrent
parents happens_before

clients_merging_concurrent_vals
content Clients merging concurrently written values
children CRDT (CRDTs for auto-merge (Riak)), siblings, union_reasonable_approach
parents happens_before

same_as_conflict_resolution
content Essentially same as conflict resolution in multi-leader replication
parents multi_leader_replication, handling_write_conflicts

siblings
content Concurrent values sometimes called "siblings" (Riak)
parents clients_merging_concurrent_vals

union_reasonable_approach
content Reasonable approach is to take a union
children doesnt_work_with_removing
parents clients_merging_concurrent_vals

doesnt_work_with_removing
content Doesn't work with removing
children tombstone (solution)
parents union_reasonable_approach

tombstone
content Tombstone: deletion marker indicating item has been removed.
parents doesnt_work_with_removing

version_vector
content Version Vector
children causal_context, collection_from_all_replicas, dotted_version_vecotr (variation on version vector), vector_clock
parents version_number_per_replica

collection_from_all_replicas
content collection of version numbers from all replicas
parents version_vector

version_number_per_replica
content Version Number per replica
children version_vector
parents versions

dotted_version_vecotr
content Dotted Version Vector (Riak)
parents version_vector

vector_clock
content Vector Clock: almost like version vector
parents version_vector

users_see_data_in_state_that_makes_sense
content Users should see data in a state that makes sense
parents consistent_prefix_reads

causal_context
content Causal context: version vector encoded as string sent to client
parents version_vector