Paper Title: Spanner: Google’s Globally-Distributed Database

Why this paper?

Issues similar to Computer Architecture:

  • Consistency: make decisions with respect to future (Overlap with Distributed Systems)
  • Reliability: Continuously deliver services even as components fail
• Delivering Services mean to provide correct results regardless of failing components over long time periods
  • Availability: Access to services for requesting results
  • Availability vs. Reliability :
• Not same
• More reliable if time between failures is large
• Better available if total failure time is less without considering when the machine fails
  • Synchronization Issues
  • Performance metrics (latency, Throughput)

Problem

  • Globally distributed Storage System that provides:
• High Availability
• High Reliability
  • Global Consistency
• Snapshot consistency
• Supports transactional access
  • Automatic Replication/sharding management with some user input
  • Eventual Consistency based on who you ask
  • Useful Interface (SQL)

Users

  • Application (developers) that want key-value store support
  • Infrastructure apps
  • F1 :
• database with transactional semantics to maintain relations and tables to provide ACID properties
  • Gmail :
• uses Megastore to guarantee ACID but with bad write throughput

Solution

1. Global Synchronized time

  • Use order of Events to define ordering
  • Enabling Technology: True Time (unique aspect) which gives interval based global time:
• Use of special Hardware like atomic clocks and GPS

2. Correct Ordering Systems

• Paxos: guarantees forward progress for distributed machines but give consistent order
• Two Phase Commit: protocol similar to bus handshake protocol in order to agree on something
  • Issue with Correct Ordering Systems: What if Response or request does not reach servers
  • Solution: Use time bounds to get different versions

3. Replication of data

• guarantee Durability
  • PROTOCOL:
• Integration of concurrency control, global synchronization ordering, replication and 2PC in order to obtain correctness and good performance
  • Lock free distributed read transactions
• Read should specify timestamp otherwise the latest will be selected
  • Read-writes
• Need locks to prevent clashes with other transactions

Evaluation

Conducted evaluation in the following directions:

  • Distributed System:
• Measured by scalability
• Relatively small scale experiments
  • Reliability:
• Kill nodes and the system still operates
• Add new nodes to the existing system without disruption
  • Synchronization: Uncertainty of clock
  • Performance: Latency and Throughput
  • F1 application

Conclusion

  • Spanner provides Globally distributed Storage System
  • Spanner uses hardware support to get True Time : interval based global time