Spanner: Google's Globally-Distributed Database

• Spanner is Google’s scalable, multi-version, globally-distributed, and synchronously-replicated database. It is the first system to distribute data at global scale and sup-port externally-consistent distributed transactions. (可扩展，多版本，全局分布式，同步复制的数据库系统，扩展性到全球级别，并且支持外部一致性的分布式事务)
• This paper describes how Spanner is structured, its feature set, the rationale underlying various design decisions, and a novel time API that exposes clock uncertainty. （主要分为两个方面，一个方面是组织结构以及关键特性还有各种设计上的权衡，另外一个就是支持时钟不确定性的时间API）
• This API and its implementation are critical to supporting exter-nal consistency and a variety of powerful features: non-blocking reads in the past, lock-free read-only transac-tions, and atomic schema changes, across all of Spanner.（主要是使用这个API才能够保证外部一致性以及一些非常强大的功能，non-blocking read历史数据，lock-free read-only事务，以及原子schema变化）

• At the high-est level of abstraction, it is a database that shards data across many sets of Paxos state machines in data- centers spread all over the world. Replication is used for global availability and geographic locality; clients auto-matically failover between replicas. （数据是进行shard的，每个shard实例之间的同步都是通过paxos状态机来完成的，实例可能散步于世界的各个地方。replication主要是为了提供全球可用性以及地理位置上的局部性，client能够自动地在replicas之间做failover切换）
• Spanner automati-cally reshards data across machines as the amount of data or the number of servers changes, and it automatically migrates data across machines (even across datacenters) to balance load and in response to failures. (spanner对于data shard是自动完成的，当server数量变化的时候会reshard然后重新做balance)
• Spanner is designed to scale up to millions of machines across hun-dreds of datacenters and trillions of database rows.(扩展到百万机器，上百个数据中心，10^12 rows)
• Spanner’s main focus is managing cross-datacenter replicated data, but we have also spent a great deal of time in designing and implementing important database features on top of our distributed-systems infrastructure（虽然spanner主要focus是在跨机房的数据replication上，但是也花了相当多的时间来在分布式结构上设计和实现很多database特性，
  • Bigtable不能够支持复杂并且变化的schema，并且对于wide-area下面不能够很好地实现强一致性
  • Megastore可以解决Bigtable这个问题但是write throughput太差（使用MVCC方式造成的冲突）
  • Spanner has evolved from a Bigtable-like versioned key-value store into a temporal multi-version database.
  • Data is stored in schematized semi-relational tables; 数据存放在schema化的半关系表里面
  • data is versioned, and each version is automati-cally timestamped with its commit time; old versions of data are subject to configurable garbage-collection poli-cies; and applications can read data at old timestamps. （data都通过timestamp进行version，这样允许application读取历史数据，而old version数据能够被GC清除）
  • Spanner supports general-purpose transactions, and pro-vides a SQL-based query language.（支持ACID事务，上层提供查询语言）
• As a globally-distributed database, Spanner provides several interesting features.（在扩展性和并发方面还提供了下面几个特性）
  • First, the replication con-figurations for data can be dynamically controlled at a fine grain by applications. （application能够精确控制data方式位置以及replication方式）
    • which datacenters contain which data
    • how far data is from its users (to control read latency)
    • how far replicas are from each other (to control write la-tency)
    • how many replicas are maintained (to con-trol durability, availability, and read performance).
  • Second, Spanner has two features that are difficult to implement in a distributed database:
    • provides externally consistent reads and writes, （读写外部一致性）
    • and globally-consistent reads across the database at a time-stamp.（全局一致性地读取历史数据）
• These features are enabled by the fact that Spanner as-signs globally-meaningful commit timestamps to trans-actions, even though transactions may be distributed. The timestamps reflect serialization order.（上面这些特性主要是因为spanner为事务提供了全局的提交时间戳，时间戳的顺序决定了串行顺序）
• The key enabler of these properties is a new TrueTime API and its implementation. The API directly exposes clock uncertainty, and the guarantees on Spanner’s times-tamps depend on the bounds that the implementation pro- vides. （提供全局时间戳关键就是TrueTime API，API实现上暴露了时钟的不确定性，提供当前时钟的范围）
  • If the uncertainty is large, Spanner slows down to wait out that uncertainty. Google’s cluster-management software provides an implementation of the TrueTime API. 如果这个不确定性太大的话，那么spanner就需要slowdown等待这个uncertainty降下来
  • This implementation keeps uncertainty small (gen-erally less than 10ms) by using multiple modern clock references (GPS and atomic clocks). 通过GPS和原子钟来keep uncertainty small

• A Spanner deployment is called a universe. Given that Spanner manages data globally, there will be only a handful of running universes. We currently run a test/playground universe, a development/production uni-verse, and a production-only universe.（一个spanner实例称为universe）
• Spanner is organized as a set of zones, where each zone is the rough analog of a deployment of Bigtable servers（spanner由多个zones组成，每个zone可以认为是一个bigtable servers的部署实例）
  • Zones are the unit of administrative deploy-ment. The set of zones is also the set of locations across which data can be replicated. （zone是用管理和部署的单元，可以认为数据的每个replication在一个zone里面最多存在一份）
  • Zones can be added to or removed from a running system as new datacenters are brought into service and old ones are turned off, respec-tively. （zone能够自由地进入和从数据中心移除）
  • Zones are also the unit of physical isolation: there may be one or more zones in a datacenter, for example, if different applications’ data must be partitioned across different sets of servers in the same datacenter.（zone也是物理隔离的单元，可以在一个datacenter里面存在几个zone实例，这样在一个datacenter就可以存在同一个数据的replication多份）

• zonemaster 选择spanserver来serve data
• spanserver serve data
• location proxy 用来定位spanserver location
• universe master和plaecment driver都是单例
  • The universe master is primarily a console that displays status information about all the zones for inter-active debugging. （汇总信息）
  • The placement driver handles auto-mated movement of data across zones on the timescale of minutes. （在zone之间进行分钟级别自动balance）
  • The placement driver periodically commu-nicates with the spanservers to find data that needs to be moved, either to meet updated replication constraints or to balance load.（直接和spanserver通信）

true time api看上去非常简洁，也非常好理解。就是说请求当前时间点的时候，得到的不是具体的时间点而是一个区间[a,b]. 没有办法准确地告诉这个时间点，但是可以确信这个时间点是在我[a,b]之间，也就是clock uncertainty.

• The underlying time references used by TrueTime are GPS and atomic clocks. TrueTime uses two forms of time reference because they have different failure modes. (TTAPI底层实现上使用了两个计时工具，GPS和atomic clock，之所以使用两种不同的工具是因为他们失效的方式不同)
  • GPS reference-source vulnerabilities include an-tenna and receiver failures, local radio interference, cor-related failures (e.g., design faults such as incorrect leap-second handling and spoofing), and GPS system outage （GPS的失效主要是因为参考源抵抗力不好，包括天线或者是接收器的失效，本地电波的干扰，cor-related失效就是说其他错误造成的失败，设计失误比如不正确的闰秒处理，GPS欺骗，还有GPS系统的掉电）
  • Atomic clocks can fail in ways uncorrelated to GPS and each other, and over long periods of time can drift signif- icantly due to frequency error.（而atomic block和GPS失效方式没有关系，主要是因为频率错误造成的时间漂移）
  • 简单地说就是GPS时间非常精确但是容易受到外部的影响，而atomic可能不非常精确但是不容易受到外部的影响，时钟的参考应该主要着重在GPS，而atomic clock应该只是为了能够应急一些GPS出现问题的情况。
• TrueTime is implemented by a set of time master ma-chines per datacenter and a timeslave daemon per ma-chine. （多个time master机器会部署在一个datacenter，和一个timeslave机器。time master机器用来相互之间校准时间，而timeslave则是同来提供始终查询服务）
  • The majority of masters have GPS receivers with dedicated antennas; these masters are separated physi-cally to reduce the effects of antenna failures, radio in-terference, and spoofing.（大部分机器使用GPS来校准时钟）
  • The remaining masters (which we refer to as Armageddon masters) are equipped with atomic clocks. An atomic clock is not that expensive: the cost of an Armageddon master is of the same order as that of a GPS master. （剩余的机器使用atomic clock，这些机器相比GPS并没有贵很多）
• All masters’ time references are regularly compared against each other. Each mas-ter also cross-checks the rate at which its reference ad-vances time against its own local clock, and evicts itself if there is substantial divergence. （所有的机器都会相互之间进行交叉校准，如果偏差较大的话那么就停止工作）
• Between synchroniza-tions, Armageddon masters advertise a slowly increasing time uncertainty that is derived from conservatively ap-plied worst-case clock drift. GPS masters advertise un-certainty that is typically close to zero.（在实际同步的过程中，使用atomic clock的机器有缓慢增长的时间偏差区间因为时钟漂移，而GPS的机器的时间偏差基本为0）
• Every daemon polls a variety of masters to re-duce vulnerability to errors from any one master. Some are GPS masters chosen from nearby datacenters; the rest are GPS masters from farther datacenters, as well as some Armageddon masters. （timeslave daemon轮询一系列的master来确定时间以降低因为任何一台master出现错误的风险，一些是从附近的datacenter GPS master，一些是从更远的datacenter GPS master，还有一些是armageddon也就是配备atomic clock master.
• Daemons apply a variant of Marzullo’s algorithm to detect and reject liars, and synchronize the local machine clocks to the non-liars.(daemon使用marzullo算法来检测liars，并且将本地时钟同步到non-liars) To protect against broken local clocks, machines that exhibit frequency excursions larger than the worst-case bound derived from component specifications and operating environment are evicted.(为了防止错误的本地时钟带来的影响，那些时钟偏差超过worst-case bound的频繁发生的机器会直接下线，具体worst-case bound是根据组件规格和操作环境推算出来的)
• Between synchronizations, a daemon advertises a slowly increasing time uncertainty. e is derived from conservatively applied worst-case local clock drift. also depends on time-master uncertainty and communication delay to the time masters.（在两次同步期间，daemon会反应出缓慢增长的time uncertainty,这个范围可以从本地时钟偏移worst-case保守地计算出来，也取决于time-master uncertainty以及comminucation的延迟）
  • In our production environ-ment, is typically a sawtooth function of time, varying from about 1 to 7 ms over each poll interval. is there-fore 4 ms most of the time. （实际生产环境下面这个延迟呈现一个锯齿状的，从1增加到7ms, 平均值在4ms）
  • The daemon’s poll interval is currently 30 seconds, and the current applied drift rate is set at 200 microseconds/second, which together account for the sawtooth bounds from 0 to 6 ms. The remain-ing 1 ms comes from the communication delay to the time masters.（上面的计算是这样出来的，平均30s同步一次，估算出来当前偏移是200us / s,因此30s是从0-6ms的偏移，在加上和master通信的1ms的延迟）
  • Excursions from this sawtooth are possi-ble in the presence of failures. For example, occasional time-master unavailability can cause datacenter-wide in-creases in . Similarly, overloaded machines and network

links can result in occasional localized spikes.（但是如果出现故障的话那么超过这个锯齿装的还是可能的，比如偶尔的timemaster不可用，或者是机器和网络出现overload的情况会造成延迟加大等）

<大规模分布式存储系统>: 为了实现并发控制，数据库需要给每个事务分配全局唯一的事务id。然而在分布式系统中很难生成全局唯一id。一种方式才哦那个percolator中的做法，专门部署一套Oracle数据库用于生成全局唯一id。虽然Oracle逻辑上是一个单点，但是实现的功能单一，因而能够做得很高效。

我的理解是，整个uncertainity分为3个部分：

1. time masters上的，GPS以及atomic clock估计出来的时间偏差。
2. local clock上的，200us/s的drift. 这个drift可以认为是有上限保证的。
3. network latency, 上限认为是1ms。

完全看不懂。。。。