Os

GRADUATE COURSE: Intro. to Computer Systems Research

  • Concurrency
    • Mutex: Mesa (Processes and Monitors)
  • High-performance Web server
    • C10K problem
    • Event-driven, async I/O
    • Low-level: TCP flow-control (buffer), cong-control (packet loss), slow-start (estimate bandwidth)
    • Persistent connections
  • Concurrency Control & Recovery in DB
    • Motivation for concurrency: Performance (multi-core, I/O overlapping)
    • Programming model: Transaction: ACID
      • Serializability test
      • 2 Phase Locking
    • Data structures: Volatile/Non-volatile, buffer pool, paging, WAL
      • STEAL/NO-STEAL: flush before committing?
      • FORCE/NO-FORCE: flush every time immediately after committing?
    • Logging: UNDO/REDO, Physical/Logical
    • Recovery: Use log and checkpoint
  • Distributed Transactions
    • Why distribution? Partition of workload, Reliability by replication
    • Coordinator + Participants
    • DT Log on stable storage
    • 2PC: network failure tolerant
    • 3PC: Non-blocking
  • Distributed Computation:
    • Clocks, Event Ordering, and Global Predicate Computation
    • Stable RTT based scheme to sync physical clock
    • Lamport clock: can’t capture causality, hard to replay
    • Vector clock: better than above — capturing causality
  • Consensus protocol: Paxos
  • Distributed File System
    • Spanner
      • Baseline: simplest approach to implement distributed transactions in a sharded setting is to layer 2PC over Paxos