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.

sectionMegastore [4dbf8b11]

Part of Databases
  • SQL based system
  • Built on top of bigtable
  • Main goal was to facilitate ACID transactions

1. Design

  • Application server

    • Used to deploy megastore, local replica on each application server, which writes to the local bigtable

  • Megastore library

    • Connects and implements paxos and replica picking

  • Replication server

    • Checks for unfinished writes, similar to a garbage collector, which provides paxos no-op commands

  • Coordinator

    • Keeps track of entity groups which its replicas has seen every Paxos write

  • Bigtable

    • Handles arbitrary reads and write throughputs

2024-02-22_19-02-48_screenshot.png

2. Replication Strats

  • Async primary/secondary - write ahead logs are replciated to at least one secondary node, but log appends are recognized and serialized at the primary node while being sent down to the secondary nodes. Primary is responsible for ACID, but it is acceptable to have a node fail and a secondary take on a primary.
  • Sync primary/secondary, primary node waits until its actually been replicated before doing a tx
  • Optimistic replication, where no primary, and any node can accept the changes and propagate them async to other nodes. Better availability and latency, but transactions are not possible.

3. Paxos

  • Megastore implements paxos, which has issues being slow

  • But Paxos gives

    • NO primary but a group
    • WAL is replciated to all nodes
    • Any node can start read/write
    • Every log adds the changes only if a majority acks
    • Remaining nodes eventually catch up
    • Communication is hindered if a majority is down
  • Entity groups are used to replicate

2024-02-22_19-06-43_screenshot.png

  • In entity groups, entities are changed using single-phase ACID transactions, which paxos uses to replicate the common record

    • 2pc can also be used
  • Megastore async replicates between different entity groups. Local indexes have strong consistenty, but global ones have weak consistenty

2024-02-22_19-14-17_screenshot.png

4. Megastore Data Model

  • API design

    • Relatively stable performance benefits
    • Shift work from read time to write time since there's definitely going to be more reads than writes
  • Data model is strongly typed, similar to RDMS, where schemas and a collection of tables are named and typed.

  • Key distinctions: root tables and child tables

    • Child table needs to specificy a foreign key referring to a root table, and a root table and all its child tables make up an entity group

  • Prejoining with keys

    • normally, primary keys have surrogate values that idenitfy each row in a table

  • Two layers of secondary indexes

    • Local index: each group's local index is used as a distinct index, which locates data inside an entity group
    • Global index: encompasses many entity groups, used to locate entities without knowing which entity groups include them in advance

  • All of this is splayed on top of big table to get atomicity, consistency, isolation, and durability

    • Uses the versioning feature of bigtable to implement multi-version concurrency control

  • Read consistency

    • Gives you three levels

      • Current: makes sure all committed writes have been executed, and does a read
      • Snapshot: reads the latest committed write operation
      • Inconsistent: reads the most recent value without considering the log's state

  • Writes

    • Writes do a current read before doing a write so it can find the latest offset for the log, then uses paxos to get all nodes to buy in, then commits it and updates it in bigtable

  • Queues

    • Transactional messaging among groups of entities are handled through queues, which is used for batching many changes into a single transaction

5. Replication in Megastore

  • Paxos WAL is mostly where it sits
  • Also allows local reads from anywhere, since paxos is used to make sure everyone is together
  • Each log position is a paxos usage, which optimizes to skip the preparation phase and enter the acceptance phase when the same proposer makes continous proposals
  • Leader decides which values are allowed ot use proposal 0

  • Different types of replicas

    • Witness replicas

      • Have WALs and vote in Paxos
      • Reduced storage costs because they don't actually store the data
      • Are able to avoid the need for an additional round trip when unable write

    • Read only replicas

      • Can't vote
      • Contain snapshots of the data
      • Read only replicas can distribute the data over large geographic area, basically a CDN

5.1. Replicated Logs

  • Replicated logs have many shapes, but we also allow holes in the logs for when consensus was not found

  • Catching up

    • Node checks if the entity group is up-to-date locally by contacting the coordinator of the local replica
    • Then finds the position, which detemrines and picks a replica that has applied through the highest possibly commited log position
    • Catches up by reading the values from the different replicas. Empty no-op values for ones that are disputed, Paxos then forces all the majority of the replicas to accept the no-op or previously comimtted write
  • Coordinators oversee the entire process, and they themselves are locked in Chubby