大数据技术基础（2013版）

大数据技术基础 厦门大学计算机科学系厦门大学计算机系林子雨 ziyulin@xmu.edu.cn 2013 年新版 2013 年 9 月修订版 厦门大学计算机科学系研究生课程 大数据技术基础 第 12 章 Google Spanner (2013 年新版 ) 林子雨 厦门大学计算机科学系 E-mail: ziyulin@xmu.edu.cn 主页 :http://www.cs.xmu.edu.cn/linziyu

提纲 Spanner 背景 与 BigTable Megastore 对比 Spanner 的功能 体系结构 Spanserver Directory 数据模型 TrueTime Spanner 并发控制 参考文献 本讲义 PPT 存在配套教材, 由林子雨通过大量阅读 收集 整理各种资料后编写而成下载配套教材请访问 大数据技术基础 2013 班级网站 :http://dblab.xmu.edu.cn/node/423

Spanner Spanner 是个可扩展, 多版本, 全球分布式还支持同步复制的数据库 他是 Google 的第一个可以全球扩展并且支持外部一致的事务 Spanner 能做到这些, 离不开一个用 GPS 和原子钟实现的时间 API 这个 API 能将数据中心之间的时间同步精确到 10ms 以内 主要功能 : 无锁读事务, 原子模式修改, 读历史数据无阻塞 大数据技术基础 厦门大学计算机系林子雨 ziyulin@xmu.edu.cn 2013 年 9 月修订版

Spanner 背景 要搞清楚 Spanner 原理, 先得了解 Spanner 在 Google 的定位 Spanner 位于 F1 和 GFS 之间, 承上启下

F1 和众多互联网公司一样, 在早期 Google 大量使用了 Mysql Mysql 是单机的, 可以用 Master-Slave 来容错, 分区来扩展 但是需要大量的手工运维工作, 有很多的限制 因此 Google 开发了一个可容错可扩展的 RDBMS F1 F1 有如下特点 : 7 24 高可用 哪怕某一个数据中心停止运转, 仍然可用 可以同时提供强一致性和弱一致 可扩展 支持 SQL 事务提交延迟 50-100ms, 读延迟 5-10ms, 高吞吐

Colossus(GFS II) Colossus 是第二代 GFS Colossus 是 Google 重要的基础设施, 因为他可以满足主流应用对 FS 的要求 Colossus 的重要改进有 : 优雅 Master 容错处理 ( 不再有 2s 的停止服务时间 ) Chunk 大小只有 1MB ( 对小文件很友好 ) Master 可以存储更多的 Metadata( 当 Chunk 从 64MB 变为 1MB 后, Metadata 会扩大 64 倍, 但是 Google 也解决了 ) Colossus 可以自动分区 Metadata 使用 Reed-Solomon 算法来复制, 可以将原先的 3 份减小到 1.5 份, 提高写的性能, 降低延迟 客户端来复制数据

与 BigTable Megastore 对比 Spanner 主要致力于跨数据中心的数据复制上, 同时也能提供数据库功能 BigTable 在 Google 得到了广泛的使用, 但是他不能提供较为复杂的 Schema, 还有在跨数据中心环境下的强一致性 Megastore 有类 RDBMS 的数据模型, 同时也支持同步复制, 但是他的吞吐量太差, 不能适应应用要求 Spanner 不再是类似 BigTable 的版本化 key-value 存储, 而是一个 临时多版本 的数据库 Google 官方认为 Spanner 是下一代 BigTable, 也是 Megastore 的继任者

Google Spanner 设计 功能 体系结构 Spanserver 目录与放置 数据模型 TrueTime Google Spanner 并发控制 大数据技术基础 厦门大学计算机系林子雨 ziyulin@xmu.edu.cn 2013 年 9 月修订版

功能 从高层看 Spanner 是通过 Paxos 状态机将分区好的数据分布在全球的 数据复制全球化的, 用户可以指定数据复制的份数和存储的地点 Spanner 可以在集群或者数据发生变化的时候将数据迁移到合适的地点, 做负载均衡 用户可以指定将数据分布在多个数据中心, 不过更多的数据中心将造成更多的延迟 用户需要在可靠性和延迟之间做权衡, 一般来说复制 1,2 个数据中心足以保证可靠性

功能 Spanner 提供一些有趣的特性 : 应用可以细粒度的指定数据分布的位置 Spanner 还有两个一般分布式数据库不具备的特性 : 读写的外部一致性, 基于时间戳的全局的读一致

体系结构 Spanner 由于是全球化的, 所以有两个其他分布式数据库没有的概念 Universe 一个 Spanner 部署实例称之为一个 Universe 目前全世界有 3 个 一个开发, 一个测试, 一个线上 因为一个 Universe 就能覆盖全球, 不需要多个 Zones. 每个 Zone 相当于一个数据中心, 一个 Zone 内部物理上必须在一起 而一个数据中心可能有多个 Zone 可以在运行时添加移除 Zone 一个 Zone 可以理解为一个 BigTable 部署实例

体系结构 Universemaster: 监控这个 universe 里 zone 级别的状态信息 Placement driver: 提供跨区数据迁移时管理功能 Zonemaster: 相当于 BigTable 的 Master 管理 Spanserver 上的数据 Location proxy: 存储数据的 Location 信息 客户端要先访问他才知道数据在那个 Spanserver 上 Spanserver: 相当于 BigTable 的 ThunkServer 用于存储数据

体系结构 Spanner 由于是全球化的, 所以有两个其他分布式数据库没有的概念 Universe 一个 Spanner 部署实例称之为一个 Universe 目前全世界有 3 个 一个开发, 一个测试, 一个线上 因为一个 Universe 就能覆盖全球, 不需要多个 Zones. 每个 Zone 相当于一个数据中心, 一个 Zone 内部物理上必须在一起 而一个数据中心可能有多个 Zone 可以在运行时添加移除 Zone 一个 Zone 可以理解为一个 BigTable 部署实例

Spanserver 大数据技术基础 厦门大学计算机系林子雨 ziyulin@xmu.edu.cn 2013 年 9 月修订版

Spanserver 从下往上看 每个数据中心会运行一套 Colossus (GFS II) 和 BigTable 不同的是 BigTable 里面的 tablet 存储的是 Key- Value 都是 string,spanner 存储的 Key 多了一个时间戳 : (Key: string, timestamp: int64) ->string 每个 Tablet 上会有一个 Paxos 状态机 Paxos 是一个分布式一致性协议 Table 的元数据和 log 都存储在上面 每个 leader replica 的 spanserver 上会实现一个 lock table 还管理并发 每个 leader replica 的 spanserver 上还有一个 transaction manager 大数据技术基础 厦门大学计算机系林子雨 ziyulin@xmu.edu.cn 2013 年 9 月修订版

Directory 之所以 Spanner 比 BigTable 有更强的扩展性, 在于 Spanner 还有一层抽象的概念 directory, directory 是一些 key-value 的集合, 一个 directory 里面的 key 有一样的前缀 更妥当的叫法是 bucketing Directory 是应用控制数据位置的最小单元, 可以通过谨慎的选择 Key 的前缀来控制, 以在 paxos group 里面移来移去 Directory 可以在不影响 client 的前提下, 在后台移动 Directory 是一个抽象的概念, 管理数据的单元 ; 而 tablet 是物理的东西, 数据文件 在 paxos group 之间移动 directory 是后台任务 这个操作还被用来移动 replicas Directory 还是记录地理位置的最小单元

数据模型 Spanner 的数据模型来自于 Google 内部的实践 在设计之初, Spanner 就决心有以下的特性 : 支持类似关系数据库的 schema Query 语句 支持广义上的事务 数据模型是建立在 directory 和 key-value 模型的抽象之上的 Spanner 的数据模型也不是纯正的关系模型, 每一行都必须有一列或多列组件 大数据技术基础 厦门大学计算机系林子雨 ziyulin@xmu.edu.cn 2013 年 9 月修订版

数据模型 上图是一个例子 对于一个典型的相册应用, 需要存储其用户和相册

TrueTime TrueTime API 是一个非常有创意的东西, 可以同步全球的时间 上表就是 TrueTime API TT.now() 可以获得一个绝对时间 TTinterval, 这个值和 UnixTime 是相同的, 同时还能够得到一个误差 e TT.after(t) 和 TT.before(t) 是基于 TT.now() 实现的

TrueTime TrueTime API 实现靠的是 GFS 和原子钟 实际部署的时候, 每个数据中心需要部署一些 Master 机器, 其他机器上需要有一个 slave 进程来从 Master 同步 每个 Slave 后台进程会每个 30 秒从若干个 Master 更新自己的时钟

Google Spanner 并发控制 Spanner 使用 TrueTime 来控制并发, 实现外部一致性 支持以下几种事务 读写事务 只读事务 快照读, 客户端提供时间戳 快照读, 客户端提供时间范围 大数据技术基础 厦门大学计算机系林子雨 ziyulin@xmu.edu.cn 2013 年 9 月修订版

Google Spanner 并发控制 单独的写操作都被实现为读写事务 ; 单独的非快照被实现为只读事务 时间戳的设计大大提高了只读事务的性能 对于快照读操作, 可以读取以前的数据, 需要客户端指定一个时间戳或者一个时间范围 Spanner 会找到一个已经充分更新好的 replica 上读取 还有一个有趣的特性的是, 对于只读事务, 如果执行到一半, 该 replica 出现了错误 客户端没有必要在本地缓存刚刚读过的时间, 因为是根据时间戳读取的 只要再用刚刚的时间戳读取, 就可以获得一样的结果

Google Spanner 并发控制 读写事务 正如 BigTable 一样,Spanner 的事务是会将所有的写操作先缓存起来, 在 Commit 的时候一次提交 这样的话, 就读不出在同一个事务中写的数据了 不过这没有关系, 因为 Spanner 的数据都是有版本的 在读写事务中使用 wound-wait 算法来避免死锁 leader 首先会上一个写锁, 他要找一个比现有事务晚的时间戳 通过 Paxos 记录 每一个相关的都要给 coordinator 发送他自己准备的那个时间戳 Coordinatorleader 一开始也会上个写锁, 当大家发送时间戳给他之后, 他就选择一个提交时间戳 这个 Coordinator 将这个信息记录到 Paxos 在让 replica 写入数据生效之前,coordinator 还有再等一会 需然后 coordinator 将提交时间戳发送给客户端还有其他的 replica 他们记录日志, 写入生效, 释放锁 大数据技术基础 厦门大学计算机系林子雨 ziyulin@xmu.edu.cn 2013 年 9 月修订版

Google Spanner 并发控制 只读事务 对于只读事务,Spanner 首先要指定一个读事务时间戳 还需要了解在这个读操作中, 需要访问的所有的读的 Key Spanner 可以自动确定 Key 的范围 如果 Key 的范围在一个 Paxos group 内 客户端可以发起一个只读请求给 group leader leader 选一个时间戳, 这个时间戳要比上一个事务的结束时间要大 然后读取相应的数据 这个事务可以满足外部一致性, 读出的结果是最后一次写的结果, 并且不会有不一致的数据 如果 Key 的范围在多个 Paxos group 内, 就相对复杂一些 其中一个比较复杂的例子是, 可以遍历所有的 group leaders, 寻找最近的事务发生的时间, 并读取 客户端只要时间戳在 TT.now().latest 之后就可以满足要求了 大数据技术基础 厦门大学计算机系林子雨 ziyulin@xmu.edu.cn 2013 年 9 月修订版

参考文献 [1] James C. Corbett, Jeffrey Dean, Michael Epstein, etc. Spanner: Google s Globally-Distributed Database.OSDI'2012.

主讲教师和助教 主讲教师 : 林子雨 单位 : 厦门大学计算机科学系 E-mail: ziyulin@xmu.edu.cn 个人网页 :http://www.cs.xmu.edu.cn/linziyu 数据库实验室网站 :http://dblab.xmu.edu.cn 助教 : 赖明星 单位 : 厦门大学计算机科学系数据库实验室 2011 级硕士研究生 ( 导师 : 林子雨 ) E-mail: mingxinglai@gmail.com 个人主页 :http://mingxinglai.com 欢迎访问 大数据技术基础 2013 班级网站 :http://dblab.xmu.edu.cn/node/423 本讲义 PPT 存在配套教材 大数据技术基础, 请到上面网站下载

Department of Computer Science, Xiamen University, Sep, 2013 大数据技术基础 厦门大学计算机系林子雨 ziyulin@xmu.edu.cn 2013 年 9 月修订版