ddia/ch09.md - DDIA

TCP

• Features
  • keep packets ordered
  • checksum of packets to detect corruption
  • network congestion control = flow control = backpressure
• Problems
  • Dedup and ordering feature applies only for single connections, so if you reinstantiate connection, data can be duplicated.
  • ACK from packet delivery means that KERNEL has accepted the packet, not that the destination app has processed the request. In this case you need additional ACK from this app.

Circuit switching vs packet switching

• Circuit switching
  • Circuit = channel
  • First, connection (=channel) is established between 2 nodes
  • No other nodes are allowed to use this channel until connection is closed.
  • Low latency. Bandwidth is fixed (=> not used efficiently).
• Packet switching
  • Not connection oriented (no connection has to established!)
  • Data is broken into packets and independently make its way to the destination (=> not arrive in the correct order)
• Hybrid networks
  • ATM (Asynchronous Transfer Mode) was a competitor to Ethernet in 80s

Clocks

• Quartz clocks drift: ~6ms per 30s (~17s each 24h)
• Leap seconds will no longer be used from 2035 on, so this problem will fortunately go away
• MiFID II European regulation forces high-frequency trading funds to sync their clocks to max. 100us drift of UTC
  • Achieved using atomic clocks and GPS receivers, PTP protocol
• Keep in mind that process may be paused, so ifs based on current time might not hold during execution.
• How to work around the clients unreliable clock? Use lock service and prepend the lock version to timestamp.

Getting time from OS

• Time-of-day clocks
  • Return ms since epoch (midnight UTC 1 Jan 1970). Not counting leap seconds
  • Synchronized with NTP
  • Can jump back to sync
  • Used to measure point in time
• Monotonic clocks
  • Guaranteed to only move forward
  • The absolute value is meaningless (can be number of ns since boot)
  • Might even differ between CPU sockets
  • NTP may adjust the speed
  • Used to measure duration

How to fence off zombies?

• Use "versions" (= fencing tokens = ) on messages. When client acquires a lock, client gets version V and on every write client MUST include version V with the request. If the lock version increased in the meantime, the request is rejected.
  • If ZooKeeper is your lock service, you can use the transaction ID zxid or the node version cversion as a fencing token.
  • With etcd, the revision number along with the lease ID serves a similar purpose
• Approach ^ assumes that storage has access to current lock version.
• Cloud providers have interfaces for this functionality (S3 - "conditional writes", GCP Storage - "request preconditionals")

Google Spanner

• We want global ordering
  • Why: it provides linearizability and consistency over a set of objects
    • Causal consistency is not enough because it doesn't guarantee consistency of the whole system
    • Example: A has 0 money. if C sends money to A, and A sends money to B; we should not observe the second without the first. In causal consistency it is possible.
• Problems
  • Shards => distributed transactions => atomic commits over multiple nodes
    • Approaches:
      • State machine replication within a shard
      • 2PL for serializability
      • 2PC for cross-shard atomicity
• Feature: read-only transactions require no locks
• Uses MVCC
• TrueTime
  • system of physical clocks which captures uncertainty

References:

• Getting Real About Distributed System Reliability https://blog.empathybox.com/post/19574936361/getting-real-about-distributed-system-reliability
• There's Just No Getting around It: You're Building a Distributed System https://queue.acm.org/detail.cfm?id=2482856
• TCP vs QUIC vs SCTP (used in WebRTC), uTP
• Spanner
  • https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/45855.pdf
  • https://sookocheff.com/post/time/truetime/
  • https://storage.googleapis.com/gweb-research2023-media/pubtools/1974.pdf
  • Spanner and external consistency https://docs.cloud.google.com/spanner/docs/true-time-external-consistency
  • Why not Lamport clocks? https://news.ycombinator.com/item?id=27640107
• Byzantine faults
  • How PBGP works
• Testing
  • How TG does testing https://tigerbeetle.com/blog/2023-07-11-we-put-a-distributed-database-in-the-browser/
  • How AWS does testing https://spawn-queue.acm.org/doi/pdf/10.1145/3712057