flashfxp上传多个网站,山东省济宁市建设厅官方网站,ssp网站怎么做,中国电力建设股份有限公司网站1. INTRODUCTION
Spanner可以扩展到跨数百个数据中心的数百万台机器与数万亿个数据库行。 Spanner是一个可伸缩、全球化分布的数据库#xff0c;其由Google设计、构建、并部署。在抽象的最高层#xff0c;Spanner是一个将数据分片#xff08;shard#xff09;到分布在全世…1. INTRODUCTION
Spanner可以扩展到跨数百个数据中心的数百万台机器与数万亿个数据库行。 Spanner是一个可伸缩、全球化分布的数据库其由Google设计、构建、并部署。在抽象的最高层Spanner是一个将数据分片shard到分布在全世界的多个数据中心中的跨多个Paxos状态机集合上的数据库。 Spanner的有趣特性
应用程序可以细粒度地动态控制数据的副本配置。包括那个数据中心包含哪些数据、数据离它的用户多远以控制读取延迟、副本间多远以控制写入延迟、维护了多少份副本以控制持久性、可用性、和读取性能。Spanner有两个在分布式数据库中难以实现的两个特性Spanner提供了外部一致性externally-consistent读写和对某个时间戳上的跨数据库全局一致性读取。
这些特性有效的原因在于Spanner会为事务分配在全局有效的提交时间戳尽管事务可能是分布式的。该时间戳反映了串行顺序。另外串行顺序满足外部一致性或等价的线性一致性[20]如果事务$T_1$在另一个事务$T_2$开始前提交那么$T_1$的时间戳比$T_2$的小。Spanner是首个能在全球范围提供这些保证的系统。 实现这些属性的关键是一个新的TrueTime API及其实现。该API直接暴露了时钟不确定度且对Spanner的时间戳的保证基于该API的实现提供的界限内。如果不确定度较大Spanner会减速以等待该不确定度。Google的集群管理软件提供了TureTime API的一种实现。该实现通过使用多种现代参考时钟GPS和原子时钟来让不确定度保持较小通常小于10ms。 外部一致性即可线性化Linearizability也就是你对一个数据写入操作成功了那么立刻去读取它就会读到刚刚写入的值。 2. IMPLEMENTATION
基本概念 directory用来管理副本和局部性locality它还是数据移动的单位。 universe一份Spanner的部署被称为一个universe。因为Spanner在全球范围管理数据所以只有少数的几个运行中的universe。我们目前运行了一个测试/练习场universe、一个开发/生产universe、和一个仅生产的universe。 zone每个zone都大致类似于一份Bigtable服务器集的部署。zone是部署管理的单位。zone的集合还是数据副本能够跨位置分布的位置集合。当有新的数据中心加入服务或旧的数据中心被关闭时zone可以加入运行中的系统或从运行中的系统移除。zone也是物理隔离的单位例如如果不同的应用程序的数据必须跨同数据中心的不同的服务器的集合分区时那么在一个数据中心中可能有一个或多个zone。 图1描述了Sppanner universe中的服务器。一个zone有一个zonemaster和几百到几千个spanserver。前者为spannerserver分配数据后者向客户端提供数据服务。客户端使用每个zone的location proxy来定位给它分配的为其提供数据服务的spanserver。universe master和placement driver目前是单例。universe master主要是一个控制台其显示了所有zone的状态信息以用来交互式调试。placement driver分钟级地处理zone间的自动化迁移。placement driver定期与spanserver交互来查找需要移动的数据以满足更新后的副本约束或进行负载均衡。
2.1. Spanserver Software Stack
软件栈如图2所示。在最底层每个spanserver负责100到1000个被称为tablet的数据结构实例。每个tablet都类似于Bigtable的tablet抽象其实现了一系列如下的映射(key:string, timestamp:int64) - string 不像BigtableSpannner为数据分配时间戳这是Spanner更像多版本数据库而不是键值存储的重要原因之一。tablet的状态被保存在一系列类B树的文件和一个预写日志write-ahead logWAL中它们都在一个被称为Colossus的分布式文件系统中Google File System的继任者。 为了支持副本每个spanserver在每个tablet上实现了一个Paxos状态机。每个状态机在它相关的tablet中保存其元数据和日志。我们的Paxos实现通过基于定时的leader租约lease来支持长期领导者租约的默认长度为10秒。
在实现一致性的多副本映射的集合时使用了Paxos状态机。每个副本的键值映射状态被保存在其对应的tablet中。写操作必须在leader处启动Paxos协议读操作直接从任意足够新的副本处访问其底层tablet的状态。副本的集合是一个Paxos group。
lock tablegroup内2阶段锁状态。在每个spanserver的每个leader副本中都实现了一个lock table来实现并发控制。lock table包括2阶段锁two-phase lock状态它将键的区间映射到锁状态。值得注意的是长期Paxos leader对高效管理lock table来说十分重要。在Bigtable和Spanner中lock table都是为长期事务设计的例如报告生成其可能需要几分钟的时间它在存在冲突的乐观并发控制协议下表现不佳。需要获取同步的操作如事务性读取会在lock table中请求锁其它的操作会绕过lock table。
transaction manager跨group事务时选择coordinator leader。在每个spanserver的每个leader副本中还实现了一个transaction manager来提供分布式事务支持。实现participant leader时使用了transaction managergroup中的其它副本称为participant slave。如果事务仅有一个Paxos group参与大多数事务都是这种情况它可以绕过transaction manager因为lock table和Paxos在一起能够提供事务性。如果事务有超过一个Paxos group参与那些group的leader会相互配合执行两阶段提交two-phase commit2PC。参与的group之一会被选为coordinator该group的participant leader会作为coordinator leader该group的salve会作为coordinator slave。每个transaction manager的状态会被保存在底层Paxos group中因此它也是多副本的。
2.2. Directories and Placement
directory在键值映射集合的上层Spanner的实现支持一种被称为directory目录的bucket桶抽象它是一系列共享相同的前缀prefix的连续的键的集合。 directory是数据放置的单位。也是paxos groups之前移动数据的最小单位。如下图 什么情况下会移动directory
为分流Paxos group的负载而移动directory为了把经常被一起访问的directory放在同一个group中而移动directory为了使directory靠近其访问者而移动directory
如何移动directory movedir是用来在Paxos group间移动directory的后台任务[14]。movedir也被用作为Paxos group添加或移除副本因为Spanner目前不支持Paxos内的配置修改。movedir没被实现为单个事务这样可以避免阻塞大量数据移动时进行的读写。取而代之的是moveidr会在开始移动数据时注册该事件并在后台移动数据。当它已经移动完几乎所有数据时它会启动一个事务来原子性地移动剩余的少量数据并更新两个Paxos group的元数据。
为了让我们的描述简介我们对其做了简化。事实上如果directory增长得过大Spanner会将其分片成多个fragment段。fragment可能由不同的Paxos group提供服务即由不同的服务器提供。事实上movedir在group之间移动的是fragment而不是整个directory。
2.3. Data Model
应用程序数据模型在Spanner的实现提供的“directory-bucket”键值映射directory-bucketed key-value mapping的上层。应用程序会在universe中创建一个或多个数据库database。每个数据库可以容纳数量无限的模型化的表table。表看上去像关系型数据库的表它有行、列、和版本号。我们不会深入Spanner的查询语言的细节。它看上去像支持以protocol-buffer为值的字段的SQL。
Spanner的数据模型不是纯关系型的行必须有行名。更精确地说每个表要求有一个由一个或多个主键列组成的有序集合。这一需求让Spanner看起来仍然像一个键值存储主键构成了行名每张表定义的是主键列到非主键列的映射。行仅当其键的某个值即使是NULL被定义时才存在。采用这种结构很有用因为它让应用程序能够通过它们对键的选择来控制数据的局部性。
CREATE TABLE Users {uid INT64 NOT NULL, email STRING
} PRIMARY KEY (uid), DIRECTORY;
CREATE TABLE Albums {uid INT64 NOT NULL, aid INT64 NOT NULL,name STRING
} PRIMARY KEY (uid, aid),INTERLEAVE IN PARENT Users ON DELETE CASCADE;图4中有一个照片元数据的Spanner模型的示例每个用户的每个相册album都有有一条元数据。该模型语言与Megastore的类似另外它还要求每个Spanner数据库必须通过客户端分区到一个或多个有层次结构的表。客户端程序通过INTERLEAVE IN在数据库模型中声明该结构层次。结构层次上层的表是directory table。directory table的每行的键为$K$它与所有后继descendant表中按字典序以K开头的行一起构成一个directory。ON DELETE CASCADE表示删除directory table中的行时删除所有相关的子行。图中还阐释了样例数据库的交错结构interleave例如Albums(2,1)表示Albums表中user id 2, album id 1的行。这种通过表交错形成directory的方式十分重要因为这让客户端可以描述多个表间存在的局部性的关系这是高性能分布式分片数据库必须的。如果没有它Spanner将无从得知最重要的局部性关系。
3. TRUETIME tt TT.now() tt.ealierst tabs(enow) tt.latest
tabs(e)表示事件e的绝对时间 enow表示“调用”事件
如何实现的呢 使用原子钟和GPS组合提供时间。
选用两种硬件组合的原因也是为了“容错”。原子钟和 GPS 都有可能出现故障但是出现故障的原因不一样GPS 可能会因为天线和接收器失效之类出现故障。而原子钟也会出错但是和外部的天线接收器之类无关。通过两个独立没有关联的系统互为备份使得整个系统失效的概率就降低了。
Google 在每个数据中心里都会部署一些 timemaster 机器大部分的 timemaster 上都会安装 GPS 天线和接收器还有一些 timemaster 则安装了原子钟。timemaster 之间会互相校验时间如果某个 timemaster 发现自己的本地时间和其他 timemaster 相比差异很大它就会主动下线把自己设置成离线状态。 原子钟会定期广播一个逐步增长的时间漂移确保其他服务器能够知道随着时间不断过去原子钟也慢慢会有时间误差。当然定期原子钟会同步一次时间把这个漂移重置为 0。而 GPS 时钟则会广播一个时间上的不确定性Uncertainty一般来说这个数据基本接近于 0。
数据中心里的其他服务器呢则会查询多个 timemaster 进行时钟同步有些是本数据中心的有些是其他数据中心的有些是 GPS 时钟有些则是原子钟。这个也是为了容错避免某个 timemaster 或者某个数据中心的数据不准确而影响结果。
4. CONCURRENCY CONTROL
4.1. Timestamp Management 表2列出了Spanner支持的操作类型。Spanner的实现支持读写事务read-write transaction、只读事务read-only transaction即预先声明了的快照隔离事务(predeclared snapshot-isolation transactions、和快照读取snapshot read。单独的写入作为读写事务实现单独的非快照读作为只读事务实现。二者都在内部重试。客户端不需要自己编写重试循环。
4.1.1. Paxos Leader Leases
Spanner的Paxos实现使用了基于定时的租约来长期保持领导权默认为10秒。潜在的leader会发送请求以获得基于定时的lease vote租约投票当leader收到一定数量的lease vote后leader会得知它持有了租约。副本会在成功的写入操作中隐式地延长其lease vote且leader会在lease vote快要过期时请求延长lease vote。定义leader的lease interval租约时间范围 的起始时间为leader发现了它收到了一定数量的lease vote的时间结束时间为它不再有一定数量的lease vote的时间因为一些lease vote过期了。Spanner依赖如下的不相交的定理invariant在每个Paxos group中每个Paxos的leader的lease interval与所有其它的leader的lease interval不相交。附录A描述了该定理是如何成立的。 Spanner的实现允许Paxos leader通过让slave释放其lease vote的方式来退位abdicate。为了保持不相交性不变Spanner对可以退位的时间进行了约束。定义$s_{max}$为leader使用的最大的时间戳。后面的章节会说明何时可以增大$s_{max}$的值。在退位前leader必须等到$TT.after(s_{max})$为true.
读写事务Read-Write Transaction读锁和写锁及伤停等待保证顺序和避免死锁 快照事务Snapshot Transaction 快照读取Snapshot Read无锁执行的对过去数据的读取操作。客户端设置时间戳或者时间戳上限让spanner选择一个时间戳 当时间戳确定后$s_{read} t_{safe} $
4.1.2. Assigning Timestamps to RW Transactions
事务的读写使用两阶段锁。因此可以在已经获取了所有锁之后与任何锁被释放之前的任意时间里为其分配时间戳。对一个给定的事务Spanner为其分配的时间戳是Paxos为Paxos write分配的表示事务提交的时间戳。 Spanner依赖如下的单调定理在每个Paxos group内Spanner以单调增加的顺序为Paxos write分配时间戳即使跨leader也是如此。单个leader副本可以单调递增地分配时间戳。通过使用不相交定理可以在跨leader的情况下保证该定理leader必须仅在它的leader租约的期限内分配时间戳。注意每当时间戳$s$被分配时$s_{max}$会增大到$s$以保持不相交性。 Spanner还保证了如下的的外部一致性定理如果事务$T_2$在事务$T_1$提交之后开始那么$T_2$的提交时间戳一定比$T_1$的提交时间戳大。定义事务$T_i$的开始事件与提交事件分别为$e_i^{start}$和$e_i^{commit}$、事务$T_i$的提交时间戳为$s_i$。该定理可以使用$t_{abs}(e_1^{commit}) t_{abs}(e_2^{start}) \implies s_1 s_2$表示。这一用来执行事务与分配时间戳的协议遵循两条规则二者共同保证了定理如下所示。定义写入事务$T_i$的提交请求到达coordinator leader的事件为$e_i^{server}$。 开始Start 写入事务$T_i$的coordinator leader在$e_i^{server}$会为其计算并分配值不小于$TT.now().latest$的时间戳$s_i$。注意participant leader于此无关章节4.2.1描述了participant如何参与下一条规则的实现。 提交等待Commit Wait coordinator leader确保了客户端在$TT.after(s_i)$为true之前无法看到任何由$T_i$提交的数据。提交等待确保了$s_i$比$T_i$的提交的绝对时间小或者说$s_i t_{abs}(e_i^{commit})$。该提交等待的实现在章节4.2.1中描述。证明 $$ s_1 t_{abs}(e_1^{commit}) \tag{commit wait} $$ $$ t_{abs}(e_1^{commit}) t_{abs}(e_2^{start}) \tag{assumption} $$ $$ t_{abs}(e_2^{start}) \le t_{abs}(e_2^{server}) \tag{causality} $$ $$ t_{abs}(e_2^{server}) \le s_2 \tag{start} $$ $$ s_1 s_2 \tag{transitivity} $$
4.1.3 Serving Reads at a Timestamp
章节4.1.2中描述的单调性定理让Spanner能够正确地确定副本的状态对一个读取操作来说是否足够新。每个副本会追踪一个被称为safe time安全时间 的值$t_{safe}$它是最新的副本中的最大时间戳。如果读操作的时间戳为$t$那么当$t \le t_{safe}$时副本可以满足该读操作。 定义$t_{safe} \min(t_{safe}^{Paxos},t_{safe}^{TM})$其中每个Paxos状态机有safe time $t_{safe}^{Paxos}$每个transaction manager有safe time $t_{safe}^{TM}$。$t_{safe}^{Paxos}$简单一些它是被应用的序号最高的Paxos write的时间戳。因为时间戳单调增加且写入操作按顺序应用对于Paxos来说写入操作不会发生在$t_{safe}^{Paxos}$或更低的时间。 如果没有就绪prepared的还没提交的事务即处于两阶段提交的两个阶段中间的事务那么$t_{safe}^{TM}$为$\infty$。对于participant slave$t_{safe}^{TM}$实际上表示副本的leader的transaction manager的safe timeslave可以通过Paxos write中传递的元数据来推断其状态。如果有任何的这样的事务存在那么受这些事务影响的状态是不确定的particaipant副本还不知道这样的事务是否将会提交。如我们在章节4.2.1中讨论的那样提交协议确保了每个participant知道就绪事务的时间戳的下界。对group $g$来说每个事务$T_i$的participant leader会给其就绪记录prepare record分配一个就绪时间戳prepare timestamp$s_{i,g}^{prepare}$。coordinator leader确保了在整个participant group $g$中事务的提交时间戳$s_i \ge s_{i,g}^{prepare} $。因此对于group $g$中的每个副本对$g$中的所有事务$T_i$$t_{safe}^{TM} \min_i(s_{i,g^{prepare}})-1$。
解释$t_{safe} \min(t_{safe}^{Paxos},t_{safe}^{TM})$ 只要$S_{read} t_{safe}$读到的就是一致的快照。 $t_{safe}^{Paxos}$ : 被应用的序号最高的Paxos write的时间戳也就是最近一个完成事务的时间戳。 $t_{safe}^{TM}$ : 保证比正在进行的所有事务开始的是时间戳更小。
这样就保证了在这个时间节点之前的所有数据当前副本都已经同步完成了。
4.1.4. Assigning Timestamps to RO Transactions
只读事务以两阶段执行分配时间戳$s_{read}$然后在$s_{read}$处以快照读取的方式执行事务的读取。快照读取能够在任何足够新的副本上执行。 $s_{read}TT.now()$在事务开始后的任意时间分配它可以通过像章节4.1.2中针对写入操作提供的参数的方式来保证外部一致性。然而对这样的时间戳来说如果$t_{safe}$还没有足够大在$s_{read}$时对块的读取操作可能需要被阻塞。另外在选取$s_{read}$的值的时候可能还需要增大$s_{max}$的值来保证不相交性。为了减少阻塞的可能性Spanner应该分配能保证外部一致性的最老的时间戳。章节4.2.2解释了如何选取这样的时间戳。
4.2 Details
4.2.1. Read-Write Transactions
像Bigtable一样事务中的写入操作在提交前会在客户端缓冲。这样事务中的读取操作无法看到事务的写入操作的效果。在Spanner中这也是很好的设计因为读操作会返回任何读取的数据的时间戳而未提交的写入操作还没有被分配时间戳。 读写事务中的读操作使用了伤停等待wound-wait来避免死锁。客户端将读取提交给相应的group中的leader副本它会获取读取锁并读取最新的数据。当事务保持打开open时它会发送保活消息keepalive message以避免participant leader将其事务超时。当客户端完成了所有的读取并缓冲了所有的写入后它会开始两阶段提交。客户端选取一个coordinator group并向每个participant的leader发送带有该coordinator的标识和和所有缓冲的写入的提交消息。让客户端驱动两阶段提交能够避免跨广域链路发送两次数据。 非coordinator participant的leader会先获取写入锁。然后它会选取一个必须大于任意它已经分配给之前的事务的就绪时间戳以保证单调性并通过Paxos将就绪记录写入日志。然后每个participant会通知coordinator其就绪时间戳。 coordinator leader同样会获取写入锁但是跳过就绪阶段。它在收到其它所有的participant leader的消息后为整个事务选取一个时间戳。该提交时间戳$s$必须 大于或等于所有的就绪时间戳以满足章节4.1.3中讨论的约束、 大于coordinator收到其提交消息的时间$TT.now().latest$、 大于任何该leader已经分配给之前事务的时间戳同样为了保证单调性。 然后coordinator leader会通过Paxos将提交记录写入日志或者如果在等待其它participant是超时那么会打断它。 在允许任何coordinator副本应用该提交记录之前coordinator leader会等到$TT.after(s)$以遵循章节4.1.2中描述的提交等待规则。因为coordinator leader基于$TT.now().latest$选取$s$且等待该时间戳变成过去时所以期望等待时间至少为$2*\bar{\epsilon}$。这一等待时间通常会与Paxos通信重叠。在提交等待后coordinator会将提交时间戳发送给客户端和所有其它的participant leader。每个participant leader会将事务的结果通过该Paxos记录。所有的participant会在相同的时间戳处应用事务然后释放锁。 总结
也是通过两个锁读锁和写锁实现事务通过伤停等待wound-wait确保之前当前事务执行时上一个事务已经执行完成避免死锁
4.2.2. Snapshot Transactions
分配时间戳是在所有参与读取的的Paxos group间的协商阶段negotiation phase执行的。这样对每个只读事务Spanner都需要一个作用域scope表达式 该表达式总结了将将要被整个事务读取的键。Spanner自动地为单独的查询推导作用域。 如果作用域的值通过单个Paxos group提供服务那么客户端会向该group的leader提出只读事务。当前的Spanner只会在Paxos leader为一个只读事务选取一个时间戳。该leader分配$s_{read}$并执行读取操作。对于单站点single-site的读取操作Spanner通常能提供比$TT.now().latest$更好的支持。定义$LastTS()$为一个Paxos group最后一次已提交的写入的时间戳。如果该没有就绪的事务则分配$s_{read}LastTS()$就能满足外部一致性事务将会看到最后一次写入的结果也因此它发生在写入之后。 如果作用于的值由多个Paxos group提供服务那么有很多种选择。最复杂的选择是与所有的group的leader做一轮通信来基于$LastTS()$协商$s_{read}$。目前Spanner实现了一个更简单的一种选择。客户端避免了一轮通信仅让它的读操作在$s_{read}TT.now().latest$时执行可能需要等到safe time增加。事务中的所有读取能被发送到足够新的副本。
总结
当个Paxos group直接由leader分配$s_{read}$多个Paxos group在$s_{read}TT.now().latest$时执行但是可能需要等到safe time增加。
4.2.3. Schema-Change Transactions
TrueTime让Spanner能够支持原子模型修改。使用标准的事务执行模型修改是不可行的因为participant的数量数据库中group的数量可能有上百万个。Bigtable支持在一个数据中心中的原子性模型修改但是其模型修改会阻塞所有操作。 Spanner的模型修改事务是更加通用的非阻塞标准事务的变体。第一它会显式地分配一个未来的时间戳该时间戳是在就绪阶段注册的。因此跨数千台服务器的模型修改对其它并发活动的干扰最小。第二读取和写入操作隐式依赖于模型它们与所有注册时间为$t$的模型修改时间戳是同步的如果它们在时间戳$t$之前那么它们能继续执行但是如果它们的时间戳在$t$之后那么必须阻塞到模型修改事务之后。如果没有TrueTime定义在时间$t$发生的模型修改是没有意义的。
4.2.4. Refinements
之前定义的$t_{safe}^{TM}$有一个弱点单个就绪的事务会阻止$t_{safe}$增长。这样即使时间戳在后面的读取操作与事务不冲突读取操作也不会发生。通过使用从键区间到就绪的事务的时间戳的细粒度的映射来增加$t_{safe}^{TM}$可以避免这种假冲突。该信息可以保存在lock table中该表中已经有键区间到锁元数据的映射了。当读取操作到达时只需要检查与读操作冲突的键区间的细粒度的safe time。 之前定义的$LastTS()$也用类似的弱点如果有事务刚被提交无冲突的只读事务仍必须被分配时间戳$s_{read}$并在该事务之后执行。这样读操作会被推迟。这一弱点可通过相似的手段解决通过lock table中细粒度的从键区间到提交时间戳的映射来增强$LastTS()$。目前我们还没有实现这一优化。当只读事务到达时可将与该事务冲突的键区间的最大$LastTS()$的值作为时间戳分配给该事务除非存在与它冲突的就绪事务可以通过细粒度的safe time确定。 之前定义的$t_{safe}^{Paxos}$的弱点是如果没有Paxos write它将无法增大。也就是说如果一个Paxos group的最后一次写入操作发生在$t$之前那么该group中发生在时间$t$的快照读取无法执行。Spanner通过利用leader租约时间范围不相交定理解决了这一问题。每个Paxos leader会通过维持一个比将来会发生的写入的时间戳更大的阈值来增大$t_{safe}^{Paxos}$Paxos leader维护了一个从Paxos序号$n$到可分配给Paxos序号为$n1$的最小时间戳的映射$MinNextTS(n)$。当副本应用到$n$时它可以将$t_{safe}^{Paxos}$增大到$MinNextTS(n)$。 单个leader实现其$MinNextTS()$约定很容易。因为$MinNextTS()$约定的时间戳在一个leader租约内不相交定理能保证在leader间的$MinNextTS()$约定。如果leader希望将$MinNextTS()$增大到超过其leader租约之外那么它必须先延长其leader租约。注意$s_{max}$总是要增大到$MinNextTS()$中最大的值以保证不相交定理。 leader默认每8秒增大一次$MinNextTS()$的值。因此如果没有就绪事务空闲的Paxos group中的健康的slave在最坏情况下会为读操作提供超过8秒后的时间戳。leader也会依照来自slave的需求增大$MinNextTS()$的值。
5. EVALUATION
5.1. Microbenchmarks 表3展示了Spanner的一些小批量benchmark。这些测量是在分时机器上运行的每个spanserver都在4GB RAM和4核AMD Barcelona 2200MHz的调度单元上运行。客户端运行在不同的机器上。每个zone中包含1个spanserver。client和zone被放置在网络距离小于1ms的一系列数据中心中。这种布局是很常见的大多数应用程序不需要将它们的数据分布到全球范围内。测试数据库由50个Paxos group和2500个directory构成。操作有单独的读取操作和4KB写入操作。为所有的读操作提供服务即使在内存规整后也会用尽内存因此我们仅测量了Spanner调用栈的开销。另外我们首先进行了一轮没有测量性能的读操作来为本地缓存热身。
对于延迟实验客户端会发出很少的操作以避免在服务器上排队。从1路副本实验得出提交等待大约为5msPaxos的延迟大约为9ms。随着副本数的增加延迟大概恒定且标准差更小因为Paxos在一个group的副本汇总并行执行。随着副本数的增加达到大多数投票quorum的延迟不再对单个较慢的slave副本敏感。
对于吞吐量实验客户端会发出很多的操作以使服务器的CPU饱和。快照读取可以在任何足够新的副本上执行因此它们的吞吐量几乎随着副本数量线性增加。只有一次读取的只读事务仅在leader执行因为时间戳分配必须在leader中发生。只读事务的吞吐量会随着本书增加而增加因为有效的spanserver的数量增加了在实验的配置中spanserver的数量等于副本的数量leader随机地分布在zone中。写入的吞吐量受益于相同的实验因素这解释了副本数从3增长到5时的吞吐量增加但是随着副本数的增加每次写入执行的工作量线性增加其开销超过了带来的好处。 表4展示了两阶段提交能够扩展到合理的参与者数量其对跨3个zone运行的一系列实验进行了总结每个实验有25个spanserver。在扩展到50个participant时均值和99%比例的延迟都很合理而扩展到100个participant时延迟开始显著增加。
5.2. Availability 图5阐释了在多个数据中心运行Spanner在可用性上的好处。其展示了出现数据中心故障时的三个实验的结果所有的实验都在相同的时间范围内。该测试universe有5个zone $Z_i$组成每个Zone有25个spanserver。测试数据库被分片到了1250个Paxos group中100个测试客户端持续地以总速率50K次读取/秒发出非快照读取操作。所有的leader都被显式地放置在$Z_1$中。在每个实验的5秒后一个zone内的所有服务器都被杀掉具体情况如下非leader杀掉$Z_2$leader强行杀掉$Z_1$hard killleader杀掉$Z_1$soft kill但是它会通知所有的服务器应先移交领导权。
杀掉$Z_2$对读取吞吐量没有影响。在杀掉$Z_1$时给leader时间来将领导权移交给另一个zone的影响最小其吞吐量的减小在图中看不出大概在3~4%。而另一方面不进行警告就杀掉$Z_1$的影响最严重完成率几乎降到了0.然而随着leader被重新选举出系统的吞吐量升高到了约100K读取/秒其原因在于我们实验中的2个因素系统还有余量、leader不可用时操作会排队。因此系统的吞吐量会增加然后再慢慢回到其稳定状态下的速率。 我们还能看出Paxos的leader租约被设置为10秒带来的影响。当我们杀掉zone的时候leader租约的过期时间应在接下来的10秒中均匀分布。在每个死去的leader的租约过期不久后新的leader会被选举出来。大概在杀掉的时间的10秒后所有的group都有的leader且吞吐量也恢复了。更短的租约时间会减少服务器死亡对可用性的影响但是需要个更多的刷新租约使用的网络流量总量。我们正在设计并实现一种机制让slave能在leader故障时释放Paxos leader租约。
5.3. TrueTime
关于TrueTime必须回答两个问题$\epsilon$真的是时钟不确定度的界限吗$\epsilon$最坏是多少对于前者虽重要的问题是本地时钟漂移是否会大约200us/sec这回打破TrueTime的假设。根据我们对机器的统计CPU的故障率是时钟故障率的6倍。也就是说相对于更严重的硬件问题而言时钟问题极少发生。因此我们认为TrueTime的实现与Spanner依赖的所有软件一样值得信赖。 图6给出了在距离高达2200km的数据中心间的几千台spanserver机器上获取的TrueTime数据。图中绘出了第90%、99%和99.9%个的$\epsilon$其在timeslave daemon查询time master后立即采样。采样中去掉了$\epsilon$因本地时钟的不确定度而产生的锯齿波因此其测量的是time master的不确定度通常为0加上到time master的通信延迟的值。 数据表明通常来说决定了$\epsilon$的这两个因素通常不是问题。然而其中存在明显的尾延迟tail-latency问题这会导致$\epsilon$的值更高。尾延迟在3月30日减少了这时由于网络得到了改进其减少了瞬时的网络链路拥堵。$\epsilon$在4月13日变大了约一个小时这是由于一个数据中心例行维护中关闭了master两次。我们将继续调查并消除TrueTime峰值的原因。
5.4. F1
Spanner于2011年初开始在生产负载下进行实验评估其作为F1Google重写的广告系统后端系统的一部分[35]。起初该后端基于MySQL数据库并手动将其按多种方式分片。其未压缩的数据集有数十TB虽然这与许多NoSQL的实例相比很小但是已经足够大以至于需要MySQL中的难用的分片机制。MySQL的分片策略会将每个消费者与所有相关数据分配到一个固定的分片中。这种布局让每个消费者可以使用索引与复杂的查询但是这需要有对程序的业务逻辑的分片有所了解。随着消费者的数量与其数据量的增长重新分片的开销对数据库来说十分昂贵。最后一次重分片花费了两年多的时间涉及到数十个团队的协作与测试以降低其风险。这样的操作太过复杂而不能定期执行因此该团队不得不将一些数据存储在额外的Bigtable中以限制MySQL数据库的增长这对影响了事务表现和跨所有数据的查询能力。
F1团队选择使用Spanner的原因有很多。第一Spanner消除了手动重分片的需求。第二Spanner提供了副本同步和自动化故障转移。在MySQL的master-slave的副本策略下实现故障转移很困难且有数据丢失的风险与停机时间。第三F1需要强事务语义这使得其无法使用其它的NoSQL系统。应用程序的语义需要跨任意数据上的事务和一致性读取。F1团队还需要在他们的数据上使用辅助索引secondary index因为Spanner尚未为辅助索引提供自动支持而他们可以使用Spanner的事务来实现他们自己的一致全局索引。
目前所有应用程序的写入操作默认通过F1发送给Spanner以取代基于MySQL的程序栈。F1在美国的西海岸有2份副本在东海岸有3份副本。副本站点的选择基于潜在的重大自然灾害造成停电的可能性与它们的前端站点位置。有趣的是Spanner的自动故障转移对它们来说几乎是不可见的。尽管最近几个月发生了计划外的集群故障但是F1团队需要做的最大的工作是更新他们的数据库模型以让Spanner知道在哪里优先放置Paxos leader从而使其接近其前端移动后的位置。
Spanner的时间戳语义让F1可以高效地维护从数据库状态计算出的内存数据结构。F1维护了所有修改的逻辑历史纪录其作为每个事务的一部分写入了Spanner本身。F1会获取某一时间戳上完整的数据快照以初始化它的数据结构然后读取增量的修改并更新数据结构。 表5阐述了F1中每个directory中的fragment的数量的分布。每个directory通常对应于一个F1上的应用程序栈的消费者。绝大多数的directory即对绝大多数消费者来说仅包含一个fragment这意味着对那些消费者数据的读写操作能保证仅发生在单个服务器上。包含100多个fragment的directory都是包含F1辅助索引的表对于这种不止有几个fragment的表的写入是极为少见的。F1团队仅在他们以事务的方式处理未优化的批数据负载时见到过这种行为。 表6给出了从F1服务器测出的Spanner操作延迟。在东海岸的数据中心在选取Paxos leader方面有更高的优先级。表中的数据是从这些数据中心内的F1服务器测量的。写入延迟的标准差更大这是由因锁冲突而导致的一个长尾操作导致的。读取延迟的标准差甚至更大其部分原因是Paxos leader分布在两个数据中心中其中只有一个数据中心有装有SSD的机器。此外我们还对两个数据中心中的系统的每个读取操作进行了测量字节读取量的均值与标准差分别约为1.6KB和119KB。
6. RELATED WORK
Megastore[5]和DynamoDB[3]中提供了跨数据中新的一直副本服务。DynamoDB给出了键值接口且副本仅在一个区域内。Spanner像Megastore一样提供了半结构化的数据模型和一个与其相似的模型语言。Megastore没有达到很高的性能。因为Megastore位于Bigtable之上这增加了高昂的通信开销。Megastore还不支持长期leader可能有多个副本启动写入操作。在Paxos协议中来自不同副本的所有写入必将发生冲突即使它们在逻辑上并不冲突这会导致单个Paxos group上的每秒钟写入吞吐量下降。Spanner提供了更高的性能、通用的事务、和外部一致性。
Pavol等人[31]对比了数据库和MapReduce[12]的性能。他们指出在分布式键值存储上探索数据库功能一些其它工作[1, 4, 7, 41]是这两个领域正在融合的证据。我们同意这一结论但是我们证明了在多层上进行集成也有它特有的优势例如在多副本上集成并发控制减少了Spanner中提交等待的开销。
在多副本存储上的分层事务的概念至少可以追溯到Gifford的论文[16]。Scatter[17]是一个最近出现的基于DHT的键值存储它在一致性副本上实现了分层事务。Spanner着眼于提供比Scatter更高层的接口。Gray和Lamport[18]描述了一直基于Paxos的非阻塞提交协议。与两阶段提交相比他们的协议产生了更多的消息开销这将增加分布更广的group的提交开销的总量。Walter[36]提供了一种快照隔离的变体其适用于数据中心内而不适用于跨数据中心的场景。相反我们的只读事务提供了更自然的语义因为我们的所有操作都支持外部一致性。
最近有大量关于减少或消除锁开销的工作。Calvin[40]去掉了并发控制它预先分配时间戳并按时间戳的顺序执行事务。HStore[39]和Granola[11]都支持它们自己的事务类型其中一些事务可以避免锁。这些系统都没有提供外部一致性。Spanner通过提供快照隔离的方式解决了争用问题。
VoltDB[42]是一个内存式分片数据库其支持广域下的master-slave的多副本策略以支持容灾恢复但是不支持更通用的副本配置。它是NewSQL的一个例子支持可伸缩的SQL[38]是其亮点。大量的商业数据库如MarkLogic[26]和Oracle的Total Recall[30]都实现了对过去数据的读取。Lomet和Li[24]描述了一种用于这种时态数据库的实现策略。
对于可信参考时钟方面Farsite得出了时钟不确定度的界限比TrueTime的界限宽松很多[13]Farsite中的服务器租约与Spanner维护Paxos租约的方式相同。在之前的工作中[2, 23]松散的时钟同步已经被用于并发控制。我们已经给出了使用TrueTime作为Paxos状态机间全局时间的原因之一。
7. FUTURE WORK
在去年的大部分时间里我们都在与F1团队合作将Google的广告后端从MySQL迁移到Spanner。我们正在积极地提供监控与支持工具并对其性能调优。另外我们一直在改进我们的备份/还原系统的功能与性能。目前我们正在实现Spanner的模型预言、辅助索引的自动化维护、和基于负载的自动化分片。对于更长期来说我们计划去调研一些功能。乐观地并行读取可能是一个很有价值的策略但是初步试验表示想要正确地实现它并非易事。此外我们计划最终支持对Paxos配置的直接修改[22, 34]。 因为我们期望许多用应程序会将数据副本分布到彼此较近的数据中心中TrueTime $\epsilon$可能会明显影响西能。我们认为将$\epsilon$降低到1ms以内没有不可逾越的障碍。可以减小time master的查询间隔时间并使用相对便宜的石英钟。可以通过改进网络技术的方式减小time master的查询延迟或者甚至可以通过其它分布式时钟技术来避免这一问题。 最后还有很多明显需要改进的地方。尽管Spanner能扩展到大量节点上节点内的本地数据结构在在执行复杂的SQL查询时性能相对较低因为它们是为简单的键值访问设计的。数据库领域的文献中的算法与数据结构可以大幅改进单节点的性能。其次能够自动化地在数据中心间移动数据以响应客户端中负载的变化长期以来一直是我们的目标之一但是为了实现这一目标我们还需要能够自动化、协作地在数据中心间移动客户端程序进程的能力。移动进程会让数据中心间的资源获取与分配的管理更加困难。
8. CONCLUSIONS
总而言之Spanner结合并扩展了两个研究领域的观点在更接近的数据库领域需要易用的半结构化接口、事务、和基于SQL的查询语言在系统领域需要可伸缩、自动分片、容错、一致性副本、外部一致性、和广域分布。自从Spanner诞生以来我们花了5年多的时间迭代设计与实现。这漫长的迭代部分原因是人们很久才意识到Spanner应该做的不仅仅是解决全球化多副本命名空间的问题还应该着眼于Bigtable锁缺少的数据库特性。
我们的设计中的一方面十分重要Spanner的特性的关键是TrueTime。我们证明了通过消除时间API中的始终不确定度能够构建时间语义更强的分布式系统。此外因为底层系统对时钟不确定度做了更严格的限制所以实现更强的语义的开销减少了。在这一领域中在设计分布式算法时我们应该不再依赖宽松的时钟同步和较弱的时间API。
