Keyboard shortcuts

/ or ⌘/Ctrl K
Find a note
j / k
Next / previous section or linked note
h / l
Collapse or go to parent / expand or enter
e or Alt-click
Read a linked note here
o
Open focused note on its own
g g / G
First / last section or linked note
g h / g a
Home / all notes
g b / g t
Backlinks / table of contents
t
Cycle System, Light, Dark
? / Esc
Show / close this reference

Search: ↑/↓ or Ctrl N/P, Enter to open. Shortcuts pause while typing.

sectionDynamoDB [3949f1f8]

Part of Databases
  • Similar to Cassandra, has partition key and sort key
  • Can horizontally partition across different nodes, similar to cassandra
  • Similarly, need to split a partition when it gets hot
  • There's an automated systems that defines a read capacity unit and a write capacity unit. If it exceeds, it splits
  • Note that since almost always you have hot partitions

  • Each node has multiple partitions

    • Each partition has two buckets, an allocation bucket or a burst bucket
    • To handle a read, pick from any bucket
    • To handle a write, the node needs to check the token availability of buckets in the nodes of the entire replication group
  • There's a global admission control system, where each request router calls to a global token bucket

  • No fixed schema

    • composite key created from the partition key and the sort key hash(partition key), sort key
    • has secondary indexes like Cassandra
  • Similar to Cassandra
  • Automated adaption to traffic patterns, can move partitions around as needed

  • Uses multi-paxos for consensus

    • Leader election from multi-paxos
    • Write comes in to a laeder,
    • Leader prepares to send acceptors containing the WAL to acceptors
    • Acceptors acknolwledge the leader's WAL and returns
    • Leader will continue to renew lease as long as it is healthy

1. Partitioning

  • Hot partitions are possible
  • Alternatively, when a partition gets too big and needs to be pslit is throughput dilation.
  • Bursting a partition means using the unused capacity on co-resident partitions
  • Basically dynamo is organized into partitions, which contain collections of sstables. The hash value matches to a partition grouping, which are dynamic. Multiple partitions can be on the same machine, and bursts can be humored with

  • Meaning there's a problem of workload isolation on the co-resident partitions, we must find a way to maintain bursts (aka load balancing)

    • Token buckets!
    • When a node recieves a request, it checks for the available tokens in the allocation bucket.
    • If there's no space available, it checks the burst bucket
    • This allows it to smooth out traffic

  • Scaling this out, we can create a global admission control

    • Central master
    • Tracks the consumption of a table using tokens
    • Request routers maintain local token buckets
    • Request routers communicate to the GAC for new tokens
    • All GAC servers are tracked by the GAC on an independent hash rings
    • Request routers manage tokens and keep deducting tokens as they accept requests
    • GAC estimates global token consumption using the information
    • GAC allocates tokens that are available
  • Basically this is the equivilant of having a QPS measurer

2. Replication

  • WAL's are used, but actually data replication is pretty slow
  • Solved with log replicas, just replicate the logs themselves (metadata operations) rather than the whole memtable

  • Silent data errors

    • Hardware failures can also cause incorrect data writes, so it uses checksums underneath (presumably they have their own filesystem)

3. Availability

  • Similar to BigTable, replication groups are across different sets, and when a replication group is not healthy, the master replaces it

  • Master is done by leader election

    2024-03-02_20-26-40_screenshot.png

  • However, sometimes grey failures happen where one node cannot reach the leader. Before it triggers an election, it asks if a quorum of other nodes can reach the leader

    2024-03-02_20-30-11_screenshot.png