BYR Achieve · 镜像论坛

GOOGLE分布式数据库技术演进研究 --从Bigtable、Dremel到Spanner 精武2014-04-04 12:20:38发表于：大数据先锋 --- *** 『码小农第四期』分布式数据库专题 *** GOOGLE分布式数据库技术演进研究--从Bigtable、Dremel到Spanner *** 菜鸟学习HBase *** HIVE开发那些事儿 --- 1 引言在传统RDBM系统中，对于事务处理必须保证为一个完整的逻辑处理过程，具备ACID四个特性，A Atonomy事务处理的原子性，要么成功，要么失败，C Consistency一致性，数据库必须保持原有约束的关系，数据之间必须符合数据完整性，I Isolation事务处理必须要彼此隔离，由RDBM保证能够并发处理事务，而不需要用户显示的干预，D Durability数据能够被持久化下来，不会出现事务涉及数据丢失的情况。此4个特性是RDBM系统的基础要素和必须遵循的原则。事物总是发展的，人类社会信息总量在不断增大，对于RDBM系统管理的数据容量已经从GB级别演进到TB级别，又从TB级别演进到PB级别，数据量不断增大，原有的RDBM已经力不从心。如何解决该问题？软件设计很多思想都来自于建筑领域，先回到建筑领域，房屋建造有2要素，建筑高度、基础构造，建筑高度决定基础构造，而基础构造又会影响到建筑高度，建设一栋三层小房，专混结构就可以了，建设十一层房子，就需要上框架结构，摩天大楼，需要采用钢和框架的混合结构方式来支撑。软件设计也有相同的道理，也存在2个要素，一个容量要素，软件能够管理多少数据规模，一个是软件构造要素，软件运行的物理硬件、操作系统、采用何种架构来组织软件各功能模块。二者对应关系，“建筑高度”对应于“容量”，“基础构造”对应于“软件构造”，但是，二者有所不同，由于建筑物需要考虑成本、实用性、安全性和各种限制，建筑高度一定是有限的，总有一个极限，而软件则有所不同，一个大容量系统数据量已经从GB级增加到了TB级，从TB级到PB级，跃升了6个数量级，软件容量呈现指数级的增加，使得软件设计面临比建筑领域更大的挑战。如何解决数据容量持续增加带来的挑战，第一提升系统的计算能力，可以并行对应数据进行分区域或者分块计算，然后对应计算结果进行汇集处理，第二提升数据的读取速度，单存储节点的读取速度必定存在限制，需要指出多存储节点的DB系统，分布式数据库DDBS系统诞生了，分布式数据库系统可以支持多个存储节点，从GOOGLE的BIGTBALE数据库原理相对应的HBASE数据库，就可以支持多个存储节点，存储节点的数量可以根据要求进行扩展，无理论上限。但是分布式数据库采用对存储节点构造后，带来了一个新的问题，这个问题就是CAP理论的魔咒，CAP为英文Consistent、Availablity、Partition Tolerance的缩写，一致性，可用性、分区容忍性，通常认为CAP理论是只能满足二个要求，不可兼得（这种限制，其实已经被GOOGLE的SPanner系统打破）。常见的DDBS系统可以保证AP，但是无法保证C，一致性，比如HBASE数据库，就无法保证多个存储区域的外部事务的一致性，如果数据跨了多个存储节点，数据可能存在冲突的可能，不一致的可能，无法做到数据表外的事务支持。ACID特性是一个数据库完美解决的要求，但DDBS要满足ACID特性中的原子性和各存储节点数据的外部一致性存在很大的困难，如果对二种不同的特征描述进行关联，AC---Consistent事务的原子性和一致性对应于DDBS一致性属性要求，ID---Availablity,事务的隔离性和持久化对应于DDBS可用性属性要求，而DDBS的Partition Tolerance会带来满足AC或者ID属性的困难，因此很多DDBS会进行特性取舍。因此，如果让DDBS系统，使之完全满足ACID的特性，必须要解决数据Partition后带来的困难，数据分成多个存储节点，如何在满足事务隔离和持久化特性的基础上，保证这些不同存储节点上的数据一致性可用性，让DDBS呈现出完全的ACID特性，打破CAP的魔咒，最常用的方式是不同数据节点的同步和全局锁控制，如果采用这种控制机制，必然会带来系统网络同步开销增加，系统的Availability能力下降，而且会出现全局锁瓶颈点，影响到系统的扩展性，出现扩展后的瓶颈点，因此这条解决方案很难走通。那我们是否能够从不一致和不确定基础上，构造出一个可靠和确定的DDBS系统，GOOGLE的SPanner数据库设计思想为解决该问题带来的新的希望，以一种全新的视角和思路来解决该问题，在可以期待的将来，开源社区也能够出现与SPanner方式对应的产品出现，使得DDBS系统应用范围更加宽广。综上所述，从CAP特性理论看，面对传统的权威理论，技术上要敢于去挑战，勇于分析，可以另辟蹊径解决技术问题，解决这些问题最大困难还是改善软件开发人员的认识，一旦认识成为定势，势必陷入到死胡同中，同时必须具备深厚的技术功底和高超编程技巧，从开源社区现在还缺乏类似于Spanner技术看，充分说明了这个技术要从思想走到实现，存在非常多的技术设计难点，要搞定这些设计难点绝无易事，但值得庆幸的，已经有人做到了，而且还在不断的完善它。 GOOGLE的分布式数据库系统从BIGTABLE的正式推出后，先后对外发布了Bigtable、Dremel、Spanner等不同的分布式数据库产品，有的是引入新的设计实现，有的是针对原有的技术进行改进和优化，用于满足GOOGLE不同的应用场景，支持日益增加的数据量管理要求。 GOOGLE分布式数据库技术，从个人理解看，可以分为三个阶段，第一阶段以Bigtable产品为代表，实现了数据的分布式存储、行数据的事务性管理和较好的扩展性，从存储WEB页面而生，创造性提出了KEY-VALUE这种MAP数据结构，并广泛应用到GOOGLE的各种应用中，与GOOGLE的MapReduce GFS技术搭配，构成了GOOGLE分布式云计算的三架马车，对应开源社区推出HBASE产品，也在近年得到了广泛应用。第二个阶段以Dremel产品为代表，Dremel产品采用了与Bigtable不同的数据结构，立足实时对于海量数据进行分析，据说在秒级可以完成PB级别的数据分析和处理，可以做是分布式数据库实时处理的杰作，其实时处理能力达到令人惊艳的速度。第三阶段以Spanner数据库技术为代表，Spanner数据库在可以做到多数据表事务一致性管理，利用原子时钟（TrueTime）和Paxos协议解决了分布式数据库多表事务一致性管理的难题，打破的CAP不可三者兼得的理论神话，使得分布式数据库技术得到了革命性的进步。严格来讲Dremel与Bigtable和Spanner解决的问题有所不同，Dremel侧重于对应海量数据的实时处理，而Bigtable和Spanner更侧重于传统的关系型数据库支持功能对齐和替换，并不是简单产品替换关系。从GOOGLE分布式数据库技术发展历程看，这些技术得以成功推出，有创造性的新锐视角和解决方案，更有其坚持在廉价PC服务器上面构筑海量数据处理系统的理想和情怀，更有起高超的技术实力和团队合作，这些因素的结合，使得技术难关被不断的突破，分布式数据库产品得以大成，这些产品的确值得技术人员去深入学习和体会。为了更好的对比和分析GOOGLE的分布式数据库技术，本文从Bigtable、Dremel、Spanner数据模型、系统架构、数据查询原理、应用场景和关键技术进行深入分析，最后对于其特点进行对比，从而使得读者对应GOOGLE的分布式数据库技术有一个初步的认识。 2 BIGTABLE开山壁祖 2.1Bigtable的数据模型 2.1.1Bigtable的Key-Value数据结构 Bigtable采用Key-Value数据结构，Key由行关键字、列关键字、时间戳组合而成，Value为对应数据内容，行关键字和列关键字都是字符串数据类型，时间戳是一个64位的长整数，精确到毫秒的时间戳，这三个属性在一个数据库中全局唯一，由Key和Value构成的KV数据结构称为一个数据项，考虑到分布式数据库的多副本的特性，数据项会按照时间戳进行排序，并对于过期的数据项进行过期回收，其数据结构如图2-1所示。图2-1 Bigtable KV结构示意图 2.1.2Bigtable的数据模型层次 Bigtable数据模型由下而上，主要部件可以初分为四个层面，最底层为SSTABLE，存放在GFS分布式文件系统中，为数据存储MAP结构体，第二层TABLET结构体，一个表可以由一个或者多个Tablet构成，由一系列的SSTABLE构成，第三层TABLET服务器，管理一组TABLET数据体，最上层Bigtable数据库，由多个TABLET服务器和一个Master服务器、客户端访问连接支持软件构成，最终形成了一个分布式数据库，对外提供数据库服务，层次关系如图2-2所示。图2-2 Bigtable各级数据模型视图数据项基于一种叫做SSTABLE的数据格式，SSTABLE是一种持久化、排序的、不可更改的MAP数据结构，每一个SSTABLE由一系列数据块构成，在每一个SSTABLE的最后存储着块索引，SSTABLE使用这些索引来定位数据块，在每一个SSTABLE被打开时，块索引会自动加载到内存中。SSTABLE提供了二种数据访问方式，第一种方式，使用二分法查找内存中的块索引，根据对应的块索引把对应的数据块读取到内存中，此种方式只会发起一次磁盘寻址，第二种方式是把整个SSTABLE都整体加载到内存中。SSTABLE基于GOOGLE GFS全局文件系统基础上，实现对应文件系统层面的负载均衡和IO能力分担，从特点看，BIGTABLE不直接支持对应数据的修改操作，通过时间戳方式来间接支持数据修改。数据读取方式，提供了二种不同的机制，二分法的块索引定位加载，类似于ORACLE提供的索引访问方式；SSTABLE的全部加载，类似于ORACLE提供的全表扫描机制，从技术角度看，不管分布式数据库技术本身如何发展，对小粒度数据精确加载和整体数据加载的场景，从这点看,所有的数据库存储结构应该都是殊途同归。一个TABLET由TABLET Log存储TABLET的提交数据的Redo记录数据，MEMTABLE是内存缓存，存储最近访问的记录数据，数据持久化到一组SSTABLE文件中。最上层Bigtable数据库服务层，对外提供Bigtable的数据库服务功能，为Bigtable的最顶层结构。 2.2Bigtable的系统架构 Bigtable由客户端连接库、Master服务器、TABLET服务器组构成，客户端链接库提供数据库客户端访问功能，提供服务端访问，比如对于数据寻址的缓存信息； Master服务器负责TABLET服务器组的管理，根据负载情况，可以动态的增加和删除TABLET服务器，维护TABLET服务器组；TABLET服务器管理该服务器上面的TABLET集合，完成TABLET数据读取和写入操作，当TABLET太大时，对TABLET进行拆分，在一个Bigtable中只能有一个Master服务器，通过Chubby保证Master服务器的唯一性；Chubby服务提供了TABLET根信息服务、系统Master管理和TABLET服务出错的善后处理任务，保存Bigtable数据库Schema信息。Bigtable整个系统架构如图2-3所示。图2-3 Bigtable系统架构图 2.3Bigtable的数据查询 2.3.1Bigtable的数据定位 Bigtable数据查询，首先是对于数据所在tablet进行定位，Bigtable的位置定位，分为三个步骤。第一步，客户端程序在缓存中查找tablet位置是否在缓存中存在，如果在缓存中存在就直接读取，如果不存在，通过Chubby服务器查询tablet的根节点，取到Bigtable根节点tablet信息；第二步，根据Bigtable根节点的tablet信息，找到数据对应METADATA的数据表，该数据表中存储着所有的用户数据tablet的位置信息；第三步，根据METADATA的数据表存储的用户数据tablet信息，找到数据对应tablet信息，根据该位置信息，读取到tablet数据到客户端。 2.3.2Bigtable的数据读取 Bigtable数据读取时以Tablet为单位，必须读取到构成该Tablet所有涉及到SSTABLE，发起读取操作时，首先要对操作完整性和权限做检查，检查通过后，首先在Tablet服务器所在的缓存里面查找，Bigtable提供二级缓存缓存，一种是以Key-Value形式的一级数据缓存，如果在这种级别中的缓存中无法找到，访问二级数据缓存，二级数据是SSTABLE的BLOCK数据缓存，对于热点局部性数据来讲，这种BLOCK环境命中率很高，对于系统性能改善更加有效。在数据缓存中如果没有找到对应的读取数据，启动数据定位的三个步骤，完成对于TABLET的位置信息读取，TABLET信息读取转换为对应SSTABLE数据，根据SSTABLE数据是否进行了压缩，对于涉及到该TABLET的SSTABLE进行解压操作，完成读取后返回到客户端。 2.3.3Bigtable的数据写入 Bigtable数据写入时，首先是坚持该操作数据格式是否正确，并判断该操作发起者是否有该操作的权限，权限判断是通过存储在Chubby服务器上面的权限控制表来判断。判断操作发起者具备该操作的权限后，会发起具体写入数据动作，该动作是一个事务操作，操作必须保证对于Tablet中数据写入成功，否则不会写入TABLET，如果写入成功后，会把提交该操作修改到Tablet对应的Redo日志中，同时该写入内容会插入到MEMTABLE中。 2.4应用场景和关键技术 2.4.1应用场景 Bigtable从数据存储特点看，属于行式数据库存储模型，虽然Bigtable具备把列分配到不同的SSTABLE，形成不同的列簇的情况。由于Bigtable采用按照行存储模型，因此对于数据表中的一行可以实现事务性操作，实现数据单表上的事务控制，虽然Bigtable提供了批量数据的访问接口，但是还不支持跨行的事务操作。而Bigtable采用的KV结构，可以按照Key中的行关键字和列关键字，对于海量数据进行列维度和行维度的切片管理，分别到同步到TABLET服务器上面。在一个BIGTABLE系统中，TABLET服务器的数量可以根据负载要求，做动态的调整，对于TABLET服务器数量无上限，这样就可以支持对于数据库负载的水平扩展，根据GOOGLE提供的数据，单TABLET服务器在BLOCK为64KB时，KEY-VALUE中的VALUE为1K的长度是，可以支持1200次请求，一个TABLET服务器可以处理75M数据读取，当TABLET服务器数量增加后，其读取数据的能力可以提升，当并不会严格的遵循线性关系，可以从GOOGLE在BIGTABLE中提供的测试数据看出，TABLET服务器增加和整体系统吞吐能力提升的关系，参见图2-4。可以看出对于TABLET的扫描和在TABLET中内存中的随机读，提升效率最为明显，这是由于在TABLET服务器增加过程中，此类操作都是在内存中进行，因此服务器越多，支持吞吐量就会更大。顺序读、随机写、顺序写提升比率低于前两种操作，顺序读由于读取SSTABLE到TABLET服务器时，一个BLOCK被读取时，SSTABLE中相邻接的BOLCK会被加载到BLOCK缓存中，后续会在缓存中被读取到该BLOCK，不在需要在从SSTABLE中读取。随机写和序列写在采用了批量提交的方式，通过数据流的方式来进行处理，此种操作方式随TABLET的增加，提升效果还是比较明显。谁TABLET服务器提升效果最低的为随机读，原因是随机读取时，为了访问KEY-VALUE值中，VALUE为1K的数据时，会同步把整个SSTABLE中一个BLOCK都读取出来，当随机读取请求数量增加时，整个网络带宽会急剧上升，导致每个TABLET服务器吞吐能力下降，整个系统能够处理的随机请求数量变少。图2-4 tablet服务器与系统IO吞吐量关系图 2.4.2关键技术从Bigtable应用场景看，BIGTABLE系统设计需要解决下面的核心技术技术难题一系统鲁棒性对于分布式环境，对于网络受损、内存数据损坏、时间误差，机器硬件损坏这这种常见的问题出现后，系统的容错处理能力，要求Bigtable系统具有较强的鲁棒性和容错性。技术难题二系统容错和负载与效率的平衡 TABLET副本数量增加会增加系统容错能力，但是会增加系统管理代价和同步成本，效率就会相应的下降；系统负载和效率增加，有限制了数据副本数量、副本数量下降会导致系统容错性减低，GOOGLE具体处理算法，这些在GOOGLE对外公布的论文中没有进行详细的描述，在开源产品HBASE遇到问题看，这些都是一些技术难点。技术难题三不同查询特点的应对由于系统不同查询特点，数据特点，对于BIGTABLE中的各种关键配置参数的配置方式，比如SSTABLE中BLOCK大小的选择、缓存算法设计细节。上面的这些技术难题相信已经被GOOGLE很好的解决，不过这些解决经验和具体技术细节GOOGLE并没有进行公开。 2.4.3BIGTABLE后续发展 Bigtable做为GOOGLE公布的第一代分布式数据库技术，结合下层的GFS文件系统，上结合MAP-REDUCE框架完成数据的分片计算，构成了GOOGLE的分布式计算体系。而BIGTABLE目前只有在一个系统只支持一个Master服务器，同时对于多表事务性无法支持，这些都是Bigtable后续要解决的技术问题。对于不同特点数据库查询请求，不同特点存放数据， BIGTABLE的关键参数应该如何配置，是否有一种完美的配置参数，可以完全满足各种不同特点的查询场景，从目前来看，还不能做到的，还必须根据数据特点，对BIGTABLE的参数做相应定制，包括一些BIGTABLE要使用的GFS文件配置参数、网络配置参数，这些都成为使用Bigtable数据库过程中一些较为复杂问题，整个Bigtable数据库使用技术门槛仍然比较高。 3 Dremel 3.1背景大规模交互性数据分析处理在整个行业中应用越来越广泛，对于交互型分析对于数据处理的响应时间要求比较高，而原有Bigtable数据库设计上并没有考虑对于交互式场景要求，对于大大规模交互数据分析处理响应性不够，因此Dremel就应运而生，Dremel解决大规模交互数据分析的实时性问题，可以做到秒级的数据响应，GOOGLE在测试中宣称，可以在3秒钟的时间处理1PB数据。在大规模交互数据分析中，会有这样一种场景，需要参加数据分析的原始数据量非常大，但是最终结果集数据量会很小，往往是一个分析结果或者是汇总型的数据，这种场景就是大型交互时数据分析的典型场景。从GOOGLE分布式数据库产品的战略定位看，Dremel和Bigtable的定位有所不同，Dremel更适合对于交互式场景，而Bigtable通常会跟MapReduce配置，做为大数据处理搭配处理，当然Dremel同样可以与MAPReduce结合使用。因此Dremel并不是取代Bigtable的一种分布式数据库，而是一种补充，从技术演进角度看，由于Dremel数据库公开时间晚于Bigtable，因此做为Google第二代分布式数据库代表之一。 3.2Dremel的数据模型 3.2.1Dremel嵌套列数据模型 Dremel采用是嵌套列数据模型，该数据模型把嵌套数据拆分为列结构加以存储，在查询时把数据重建为嵌套数据，原有列存储数据库通常属于关系型数据库，在嵌套类型的数据处理还未采用这种结构，GOOGLE创造性的把嵌套数据处理为列数据库，并且技术指标还能大幅提升，满足大型数据的交互式查询要求，不得不说这个GOOGLE的一个新创造，但为什么是这样的列嵌套结构，而不是其他数据结构，这点GOOGLE并没有进行介绍说明，因此这一点理解上面有一定困难，不过在后续介绍中，会发现这种结构在数据查询处理时的优势和特点。一提起数学模型，很多程序员就会晕，不过仔细看看，稍微有一点数据知识的人，应该就能够看明白，Dremel的数学模型如下： π = dom | <A1 : π[*|?],…,An : π[*|?]> π是数据库中的一条记录类型，Ai是数据库记录的一个字段，*为一个重复字段，?为可选字段，这个数据模型说明该一条记录是由多个字段构成，字段类型由可选字段、必选字段、重复字段组成，可选字段可以出现，也可以不出现；必选字段必须会出现，重复字段则会出现多次。在GOOGLE公开的资料中，在图3-1给出嵌套记录样例和数据模式定义，Document是一个网页类型的数据模式，该网页有整形的DocId和可选的Link分组属性，Link分组属性包含了多个Backword和Forward可图3-1 嵌套式记录样例和数据模式定义重复的整型属性构成列表，一个网页包括了多个可以重复的名字分组，每个名字分组，可以包括多个语言分组和可选的URL地址，语言分组包括必选的CODE字段，可选的Country属性。整个Document嵌套层次关系如图3-2：图3-2嵌套层次关系图 3.2.2Dremel的重复深度和定义深度在Dremel中如何对于嵌套式数据结构，在列存储后进行重建，依赖于二个重要参数，一个是Repetition Level重复深度，一个是Definition Level定义深度.重复深度和定义深度仅针对重复字段来计算层次，用于描述这个值什么重复字段的此值重复了，以此确定重复的位置；定义深度描述多个嵌套层次的路径上，有多少个字段是有值的，通过这二个参数可以完成嵌套数据的列式化存储。 3.2.3Dremel的存储和重构 Dremel存储是采用列式模型，按照列进行嵌套式数据的存储，读取数据时，根据定义在列式模型中的数据，按照顺序，把列式存储数据还原到原有的嵌套式数据结构。 3.3Dremel的系统架构和查询 Dremel采用的是多层次服务树架构，最上层Dremel的根服务器，根服务器接收所有的查询请求，读取数据库相关的元数据，并把相关请求下发到下一级查询服务器查询。中间层查询服务器负责根服务器请求的派发和叶子服务器的查询结果的处理。叶子服务器与具体存储层直接通讯，完成存储系统上相关数据的读取和查询动作，整个系统架构图如下图所示。图3-3 Dremel多层次查询树架构 Dremel查询语句基于SQL语法，并根据自身列存储模型进行了定制，构成在Dremel的存储结构上面高效的执行，对于Dremel查询树结构，会对于根查询服务器收到查询请求进行层层拆分，最终传递到叶节点的查询服务器，叶节点查询服务器获取的数据结果后，进行过滤和汇总这样的计算，然后在上传到上级查询服务器，层层汇总结果后，最终返回结果数据。 Dremel支持多客户端并发查询，通常情况下查询请求会被同时运行，查询派发器，会根据系统的负载情况和查询优先级进行一定的查询调度操作，并提供容错性，对于查询节点响应缓慢和访问数据不达的情况进行调整。 3.4应用场景和关键技术 3.4.1应用场景 Dremel定位为交互系统大型数据处理的数据库系统，适合数据读取数据量大，但是返回数据量小的场景，对于返回数据量大的场景，采用Dremel就不太合适。 3.4.2关键技术 Dremel采用的嵌套式列存储结构+多层次查询查询树，大型数据处理快速响应的关键，列存储结构可以只对查询关心的列数据读取，多层次查询树结构对于数据查询的拆分和聚合的方式有效的匹配，这是Dremel在该场景速度快于Bigtable的关键技术； Dremel号称可以在秒级进行1PB级的数据运行，没有看到公开的验证数据，该这种1PB级的数据，从个人推断应该是所有列存储数据占用空间的总大小，而不是仅仅该字段占用空间的大小。 Dremel结构解决了传统的多表数据通过外键关联效率缓慢的问题，通过存储列数据的顺序结构解决了多表数据的关联问题，思路非常巧妙。 3.4.3技术展望 Dremel对于标准的SQL语法是不支持的，为了满足高效率查询，设计了与自身结构相匹配的查询语句，因此Dremel对于数据库一些通用SQL查询支持是不够的，更像是一种处理交互式数据查询的分支数据库，与通常意义上面讲的BIGTABLE数据库使用场景有很大的区别，因此应该属于分布式数据库发展的分支技术方向，而不是主流发展方向。后续Dremel是否能够对于嵌套式数据库模型进一步的优化，提供部分SQL标准接口，这些都是Dremel后续可能的发展方向。 4 Spanner 4.1背景在google的BIGTABLE论文中，提到过Bigtable后续计划支持多Master的方向，由于BIGTABLE的架构中，只有一个Master服务器，因此一个Bigtable分布式数据库的扩展能力，始终是由一定的限制，数据量增加后，势必需要就会出现瓶颈，如何提升数据库的数据管理能力，解决数据规模不断增加后带来的问题。同时Bigtable丢失传统RDMS系统的一些特点，比如多数据表之间的事务一致性，这些都是数据库必须也是应该具背的特性。是否能够满足分布式数据库的数据分布、负载和吞吐量的同时，还具备关系数据库特性，这不就是分布式数据库的智高无上的理想吗？但分布式数据库CAP理论告诉我们，分布式数据库一致性，可用性、分区容忍性此特性必然只能取其二，是不可能同时具备，这个魔咒能够被打破吗？阿迪有一句名言“Nothing is impossible”势必需要引入一种新的机制,聪明的Google人找到并解决方案，并在技术上得以实现，Spanner就是在这个场景下面诞生。 4.2Spanner的数据模型 4.2.1带独立时间戳映射结构 Spanner有一种负责专门管理数据的spanserver，spanserver也是基于bigtable的tablet结构，每个spanserver由上百个或者上千个tablet构成，Spanserver类似于Bigtable中tablet服务器，是管理数据的核心组件，spanserver的Tablet存在下面映射(key:string, timestamp:int64) –> string，这种映射与Bigtable采用的Key-Value结构第一眼看去貌似一样，但仔细看确有很大差别，时间字段不在是Key一个组成部分，而是把时间戳单独了出来作为一个独立项，构成了一个多版本的数据库，独立时间戳意味着时间在Spanner中会扮演重要角色。 4.2.2spanserver的软件层次一个tablet由数据和状态部分构成，存放在一种称作Colossus的文件系统中，该文件系统为GFS后继的文件系统，为了支持数据同步复制，在spanserver上部署有一个paxos状态机, paxos状态机用于实现一系列被一致性复制的映射。一个数据有多个数据副本，多个数据副本所在的paxos状态机组织成一个paxos分组，用于控制副本一致性。对于主副本，spanserver会增加锁表来保证并发性控制，对于在一个跨越多个Paxos分组的事务，需要在Paxos更上层的确定出主副本机制，以保证跨Paxos分组的事务性。整个结构如图4-1所示，在图中可以看出，由于涉及同步的复制范围不同，需要参与协商Leader的范围就会发生变化，但不管如何变化，始终是可以根据上升的原则，通过协商机制，实现更大范围的事务控制。图4-1 Spanserver软件层次图 4.2.3Spanner的目录结构 Spanner提供了一种最为基础键值映射集合的逻辑视图，这个逻辑视图实际上是一个桶的作用，用于把提供一系列键值映射集合放在一起存储，只是为了便于理解，在Spanner中，把这种桶叫做目录。由于键值存放的数据可能存在于不同的Paxos分组，各Paxos所对应物理存储可能在不同的Spanserver服务器上，这些数据也可能属于不同zone,因此虽然这些数据都可以被访问，但访问读取时需要通过长距离的网络传输，因此访问效率可能就不太高。 Spanner中提出了目录概念，就是要把目录作为数据放置的最小单位，目录可以在Spanner中进行移动，移动原则是相关数据尽量存放在一起，这样可以提升Spanner的访问效率，可以看出逻辑桶结构对于Spanner这种巨型的分布式数据库效率提升具有十分重要的意义，能够让系统在数据分布的同时，照顾到数据物理位置，尽量以访问效率的原则进行数据物理位置的调整，以解决效率问题。目前这种调整的依据还是只能根据访问频率的方式来进行调整，当一个目录所管理的键值映射集合太大时，会进行分割操作，分裂为多个目录。 4.2.4Spanner的半关系模型 Spanner的模型属于半关系型模型，每个表都必须包含一个或者多个主键的排序集合，这一点类似于Key-Value的结构，这种结构的好处是可以方便的根据这种主键来进行数据存放位置控制，这种位置属性可以解决分布式数据的位置聚集要求，提升系统访问的性能，但是带来的一个问题，系统需要存放一些冗余信息，对于没有主键的行，也必须存储为NULL值。在图4-2对于这种半关系模型进行了说明，这个例子中有2个表，用户和相册，相册是依赖于用户这个表格，在相册定义是就增加了用户的信息，这种结构可以根据客户端分割为一个表或者多个表的层次结构，以用户为主键，可以按照用户来组织目录，这种方式就可以结合上面目录结构做到位置集聚，解决由于数据物理分布引起的效率问题。图4-2 Spanner半关系型数据表定义示例 4.3Spanner的系统架构 Spanner设计为一个全球型，可扩展的巨型分布式数据库，可以把不同的应用放在一个Spanner中，而不像Bigtable需要建立不同的Bigtable集群。Spanner可以支持这些存放数据的同步和复制，在保证效率的基础上，进行数据复制，整个Spanner系统架构如图4-3所示，Universe Master为Spanner的总控制台，一个Spanner只有一个Universe Master，对于zone进行管理，包括创建、删除，同时也显示zone的各钟状态信息；Palacement driver为目录移动控制器，会周期性的与Spanserver进行通讯，确定需要转移目录、满足系统更新后的副本约束条件，系统负载调整所需目录中数据转移，优化数据物理存储，转移速度控制在分钟级别，一个Spanner只有一个Palacement driver；一个Spanner由许多个zone构成，zone类似于Bigtable数据库的角色。zone是管理部署的基本单元，Spanner中的zone中的数据都可以支持复制，可以在Zone之间进行数据复制，这种特性为新加入zone和删除或者替换zone时，提供了良好的扩展性。一个Zone有一个zone Master和许多Spanserver构成，Zone Master把数据分配给Spanserver，由Spanserver提供给客户端数据库服务，客户端通过Zone上面的Location proxy来确定为客户端提供服务的Spanserver。图4-3 Spanner架构图 4.4Spanner查询 4.4.1Spanner只读查询 Spanner收到一个数据读取操作后，根据发起查询请求，计算出整个查询需要涉及到那些键值，涉及到的键值有多少Paxos分组，只涉及一个Paxos分组和涉及多个Paxos分组的处理逻辑有所不同。涉及一个Paxos分组，按照下面步骤来获取数据：步骤一客户端对Paxos组的领导者发起一个只读事务；步骤二 Paxos组的领导者分配为这个读操作分配一个时间戳，这个分配过程Paxos组领导必须要考虑到现在已经申请处理的事务，确保这个时间戳可以让该读取看到最后一次写之后的数据；步骤三按照分配的时间戳进行数据读取。涉及多个Paxos分组时，步骤会有所不同，按照下面步骤获取数据：步骤一客户端发起一个只读事务；步骤二多个Paxos组领导者进行协商后，分配一个时间戳；步骤三按照分配时间戳进行数据读取。 4.4.2Spanner读写操作 Spanner对于读取和写入操作会进行拆分，发生在一个事务中写操作会在客户端进行缓存，先执行读操作，因此这种事务读取操作不会看到这个事务写操作结果。读操作在自己数据相关的Paxos组中先获取到读锁，读锁作用是明确读先执行读操作，避免写操作申请到写锁，申请到读锁后，分配给客户端对应时间戳进行读操作，但所有读取操作完成后，释放掉读锁。读锁释放完成后，客户端开始处理所有已经缓存的写操作，也是通过Paxos协商机制进行协商，获取到写锁，分配对应的预备时间戳后，然后根据预备时间戳中的最大时间，确定一个提交时间戳，在提交时间戳同时进行写操作的事务提交。 4.5应用场景和关键技术 4.5.1应用场景 Spanner的特点使其具备特定关系型数据库的特点，其应用的场景可以部分替换原有关系型数据库的使用场景，原有Bigtable丢失的关系型数据库的特性，在实际应用中也暴露出了存在缺陷，而Spanner着力于找回这些丢失的特性，提供表数据的外部一致性和读取的全局一致性、跨中心数据的一致性复制，从Google的应用实际看，GOOGLE可以使用F1+Spanner的方式来完全满足关系型数据的特性，而Spanner就是这里组合的基础，不满足部分由F1来实现。同时，由于Spanner数据库的管理能力非常巨大，可以设定多个区域，每个区域的管理能力都与Bigtable相当，因此是一个全球性的巨型数据库，理论上所有的应用都可以基于一个Spanner数据库来运行，这种管理能力是非常惊人的，同时采用这种多区域组成Spanner数据库的结构，多个区域网络连接速度一定是有限，Spanner由会通过一些目录调整的技术，来内聚相关数据，做到相关数据的位置聚集，解决了多区域数据库存在的效率问题，因此从部署上看，spanner可以部署多个数据中心，不仅仅是逻辑数据中心，还是包括物理上不同数据中心，组成一个全球分布式数据库。 4.5.2关键技术 4.5.2.1TrueTime TrueTime是Spanner中核心技术，掌握TrueTime也就掌握Spanner技术精髓，TrueTime从物理上GPS和原子钟构成时间发生器，在每个数据中心部署了一组time Master，在每个节点都部署了timeslave daemo,大多数Master都配置为GPS时钟，部分Master配置为原子时钟，这些Master在物理上面相互隔离，逻辑上会彼此通讯，进行时间校对。Timeslave daemo会从一组Master中获取可信时间区间，这种机制会对于Master进行修订，同时timeslave daemo可以获取到一个可信时间区间，具体实现细节这里不做详细描述。而Spanner是利用TrueTime提供API方法，TT.now()、TT.after()和TT.before()方法，TT.now()方法可以给出一个可信时间区间，类似于时间的最早和最晚时间构成的可信时间区间，保证时间必然在这一区域内，TT.after()和TT.before()方法是TT.now()方法的扩展。表示一个事件e的绝对时间，可以利用函数tabs(e)。如果用更加形式化的术语，TrueTime可以保证，对于一个调用tt=TT.now()，有tt.earliest≤tabs(enow)≤tt.latest，其中，是enow是调用事件。这个可信时间区间太重要了，这里强调一下Truetime解决二个重要问题，第一，这个可信时间区间是Spanner全系统一直认同、并一致保证、可靠的时间区间值，第二，TrueTime机制使得这个区间值范围达到毫秒级，时间区间范围值越小越利于分布式事务处理，事务处理成功可能性就会越大。这种时间置信区间后，分布式数据库节点之间最大问题事务一致性控制，如何控制，如果有绝对准确时间，可以通过判断事务发生的时间顺序来进行事务一致性控制，因为从时间点角度看，任务一个事务发生时间点必然是唯一的，只是由于系统时间精度和准确时间获取成本和技术上可行性，导致时间点无法准确区分和排序，TrueTime就退而求其次，给出一个可信时间区间，然后根据各事务提交可信时间区间对事务成功还是失败进行控制，这种思路的确非常巧妙的解决这一难题。 4.5.2.2只读事务和快照读事务无锁管理只读事务时预先申明快照隔离的事务，这种事务提前申明不包含什么写操作，由Spanner系统为这种事务分配一个时间戳，在这个时间戳后面写事务都不会被阻塞，一个只读事务可以去任何足够新的副本上面去执行，实现无锁管理。快照读事务是对历史数据的读取，由客户端在提交事务处理时给出一个时间戳或者给出一个时间范围，让Spanner根据这个时间范围选择一个时间戳给该快照读事务，这二种场景都可以保证快照读在任何足够新的副本上面执行，实现无锁管理。 4.5.2.3Paxos领导者的续约事务始终是与Paxos分组相关，由Paxos中的领导者进行事务控制，对于领导者能够对于事务时间进行控制，可以延长自己的时间，实现更长时间的领导者地位，当然这个时间有一个最大值，不能超出这个值的范围里面续约，续约有一套类似投票协商的机制，此处不做详细介绍，另外为了保证事务的隔离性，退出以时间区间中最晚时间点满足条件为止。 4.5.2.4读写事务的锁管理 Spanner采用读和写采用二阶段锁事务协议。当所有锁都已经获得以后，在任何锁被释放之前，就可以给事务分配时间戳。事务根据分配时间戳，通过Paxos分组控制机制，把读或者写的动作进行时间戳排序拆分，确保该事务能够被正常的执行。 6 结语 GOOGLE从Bigtable数据库开始，提供出来一个解决大型数据管理的新视角，Bigtable侧重于数据分布性、扩展性和处理能力提升，丢弃了关系型数据库特性，是一种NOSQL的技术发展方向，不管是Bigtable在GOOGLE公司内部的成功应用，还是开源社区HBASE大红大紫，都说明这种技术方向确实有应用场景。但是随着Bigtable数据库深入使用，我们发现其丢失的关系型数据库特性，在有些场景下已经不能满足需求，对于巨型数据进行分析时Bigtable的速度也不能满足人们的要求。通过GOOGLE的不断研究，在实时数据分析上，引入了一种新模型Dremel，该模型使用列式嵌套式的存储结构和服务树的方式，提高数据读取的有效性，对于数据进行快速查询分解，对于查询结果进行快速汇集，满足大型数据的实时处理要求。作为Bigtable的后续演进上，GOOGLE推出Spanner来找回部分Bigtable丢失关系型数据库的特性，同时Spanner在管理容量上，比Bigtable有了巨大的提升，如果说Bigtable是一个区域和局部分布式数据库集群，那么Spanner就是一个全球范围的巨型数据库系统，在管理上无理论上限。在Spanner后续技术发展上会进一步的提供更接近与关系数据库的产品，对于数据库的效率继续提升，另外一个比较让人动心的技术是数据按照负载情况进行感知，自动进行位置搬迁，提升处理效率，同时spanner也在提升不同数据中心数据复制的成本，优化数据一致性带来的开销，对于Bigtable、Dremel、Spanner的关系可以如下图6-1所示。图6-1 Bigtable\Dremel\Spanner关系图 GOOGLE对于分布式数据库技术发展方向的共享非常大，可以说引领了整个分布式数据库发展的方向，如果说苹果公司重新定义了手机，那么也可以说GOOGLE重新定义了分布式数据库，差别在于苹果公司提供是手机这样的产品，而GOOGLE提供的是一种可以技术上进行实践的分布式数据库理念，期待不久的将来，GOOGLE能够持续对于分布式数据库进行持续改进，能够使得分布式数据满足必要关系型数据库特性，提供更好的产品理念和技术文档的同时，而且把代码级把产品能够公开出来，满足大型数据的处理要求，推出对外商用的分布式数据库产品。

『码小农第四期』GOOGLE分布式数据库技术演进研究