|
|
文章转自：腾讯大数据 ， 作者 Tbase
腾讯TBase是一款腾讯自研高性能HTAP数据库，供给高性能的OLTP和OLAP才能，同时保证可扩大全局分歧性散布式事务（ACID），为用户供给高分歧性的散布式数据库办事和高性能的数据仓库办事。一方面处理了传统数据库扩大不敷、数据sharding以后数据库事务的严酷分歧性困难、数据平安、跨地域容灾等题目，同时具有了高性能事务处置、数据治理、夹杂负载支持等才能。
在OLTP方面，TBase采用MVCC+全局时钟+2PC+SSI的方式来实现全局分歧性散布式事务，同时引入大量性能优化的设想来削减全局事务带来的开销。在小范围集群上，TBase可以供给跨越300万TPMTotal的事务处置吞吐量（产业界标准TPCC测试集）。
买卖毫秒内完成
TBase已经覆盖多个行业的标杆用户，其中对内支持了微信广告、微信付出、腾讯舆图等海量数据营业，一笔买卖毫秒内即可完成，支持了微信付出50倍的买卖增加。
本文先先容TBase的架构系统和数据库事务的根基道理，然后先容学术界最早辈的散布式事务设想计划，最初论述我们的设想道理。
全文12000字，估计阅读时候：30分钟。
TBase腾讯自研高性能HTAP数据库先容
—— TBase整系统统架构图 ——
TBase是一款腾讯自研高性能HTAP散布式数据库，同时供给高性能的OLTP和OLAP才能，整系统统架构如上图所示。具体的，TBase由多个调和理点（Coordinator），多个数据节点（Data Node）和单个时钟办事器（GTS）组成。用户表数据采用shard机制 [9,12]在多个Data Node停止散布。Coordinator节点负载接管用户的SQL请求，剖析SQL天生散布式履行计划，然后在Data Node上分派资本履行该散布式履行计划。每个Data Node运转着完整的数据库实例，包括存储层，日志层，事务处置层，查询优化器，履行器等。GTS负责天生严酷递增的时候戳，用于保证全局分歧性散布式事务。
数据库事务机制
数据库事务ACID是关系型数据库最根基和最焦点的一个特征。数据库事务供给给用户一个强大的笼统概念，可以简化上层利用存储和拜候数据的逻辑。比如数据库事务的最严酷的Serailizable隔离级别可以保证并发的事务的履行结果和串行履行这些事务的结果是一样的，从而使得上层利用不需要斟酌复杂的并发致使的分歧性题目。数据库事务的原子性（A），分歧性（C）和持久性（D）根基都是经过WAL（Write-ahead Log）日志来实现，在散布式场景下还需要引入额外的两阶段提交（2PC）来保证，这里就不具体论述。本文重点先容事务里面最复杂的隔离性（I）。
我们首先先容一下 数据库隔离语义： read committed，repeatable read 和serializable。
一切的隔离级别语义都需要满足：事务T1可以看到T2的点窜，当前仅当T1.start > T2.commit。T1.start为T1事务起头的绝对时候，T2.commit为T2提交的时候。对于read committed，即T1.start为每条语句起头时候。
Read committed：满足上述的语义的同时，对于写写抵触，采纳答应并行点窜的战略，从而削减abort。具体的，对于一个tuple， T1(x, w)写入x值，T2(y, w)写入y值，假如T1先提交，则该值变成x，T2再提交时，将改成y。假如update语句中有where判定条件，T2会重新计较更新的最新值x能否满足条件，再停止更新。
Repeatable read: 对于写写抵触，采用First-commit-win机制，并行点窜事务第一个提交的将成功，前面提交的将被abort。Repeatable read和read committed城市存在write skew的题目 [1,2]。斟酌以下并发履行，T1履行读取x，然后将x值写入y，T2履行读取 y，然后将y值写入x。在Repeatable read隔离下，T1和T2都可以提交成功，可是履行成果不满足串行化履行T1和T2后的成果，即先履行T1再履行T2，或反过来。
Serializable：在Repeatble read隔离根本上，假如两个事务T1和T2存在读写依靠(rw-dependency），也会abort后提交的事务。Serializable隔离级别履行成果满足并行事务肆意串行化履行的成果。即例如T1和T2并行履行，最初的成果满足肆意串行化履行（T1->T2大概T2->T1）的成果。这类隔离级别履行成果最轻易被用户了解，对利用数据库的利用法式来说，可以极大的简化上层营业逻辑（不用去斟酌并行），可是会致使比力频仍的abort（在抵触比力大的时辰）。
数据库实现上述隔离级别首要有三种支流的方式: 2PL,OCC和MVCC。
2.1 2PL （Two-phase Locking）
两阶段锁，是一种最简单又最低效的实现事务隔离的方式。2PL经过在事务起头阶段对一切拜候数据工具停止加锁，在事务竣事的时辰停止解锁，来串行化并行事务的履行，从而实现Serializable隔离级别。该方式会致使极低的履行并发度。
2.2 OCC (Optimistic Concurrency Control）
OCC采用两阶段履行（execution phase和 commit phase）来供给事务隔离。
履行阶段：每个事务将writes缓存在当地write-set（对别的事务不偏见），同时记录读操纵到read-set（读的位置和序列号）。拜候一个记录的时辰，假如该记录被锁住（别的事务提交阶段锁），则挑选abort。
提交阶段：该阶段将对write-set中的记录停止加锁，并检查读的记录（read-set一定包括write-set，由于点窜一个记录需要先读一个记录，即read before write）在事务履行进程中能否被别的并发事务所点窜（检查序列号），假如被点窜，则abort本事务。假如没有被点窜，则将write-set中的数据写入数据库存储，更新序列号，最初解锁。OCC可以供给Serializable隔离保证，可是读写抵触情况下，读并发低（很多负载是read-dominated的负载，改良读性能很重要）。
2.3 MVCC （Multi-Vesion Concurrency Control）
MVCC经过量版原本供给更高的读并发，同时经过snapshot isolation机制保证read-committed和read-repeatable隔离级别（相比serializable隔离级别弱）。MVCC的根基道理是经过量版本链来在并发写的情况下支持non-blocking读。MVCC可以保证并发更新的同时，并发读可以读到事务起头前（大概语句起头前）的分歧性的数据库快照。
MVCC具体的实现方式是每个tuple（表的每个逻辑行对应的物理存储单元）都有一个xmin和xmax，xmin暗示插入该tuple的事务xid，xmax暗示删除该tuple的事务xid。Update操纵由一个删除和插入组成。每个表的逻辑行由一串多版本的tuple链组成。每个事务起头前获得一个系统范围内正在运转的事务的xid调集（数据库快照），在拜候某个逻辑行时，对它的版本tuple链停止遍历，从而找到对该事务可见的最新版本（即会拿xmin和xmax在快照中停止查找判定，读取事务起头之前已经提交的最新的tuple版本）。
快照判定的道理是，假如一个xid在快照中，说明插入这个tuple的事务在当前事务起头时正在运转中，则这个事务xid的点窜对当前事务不偏见。否则，当前事务进一步判定xid能否已经提交，假如已经提交（而且不在快照中），则该xid的点窜对当前事务可见。
在一定的时辰，空间接管进程对老的版本停止空间接管（热接管和冷接管），来开释空间，更重要的是削减版本链的长度（削减读搜索可见版本的开销）。热接管是在扫描的时辰开启，用来将每个扫描的页面上的多版本停止compact从而削减搜索长度，来加速前面的扫描。冷接管是专门的进程运转，对表停止空间接管，行将页面上有用的tuple版本拷贝到新的页面上去，从而完全接管空间。
空间接管有一个应战是要判定哪些版本可以接管，从而避免接管掉正在（行将）被拜候的记录。一个根基的算法（PostgreSQL里的算法）是计较全部系统范围内一切事务可见的最老的xid，然后接管xid < oldestxmin的事务插入后来被删除（大概更新）的记录。
Oldestxmin算法：在天生快照的时辰，以系统范围内完成的最大的xid + 1为oldestxmin，然后更新oldestxmin小于或即是每个正在运转事务的xid，而且小于或即是每个事务天生快照时它计较出的oldestxmin。这样对于每个逻辑行，接管xmax < oldestxmin的tuple版本可以保证正在运转的事务一定可以看到对它可见的一个版本，即接管的版本不会被别的事务拜候（不偏见）。
—— MVCC多版本链和空间接管机制 ——
上图展现了MVCC的根基道理。表的某个逻辑行有三个版本，和，tuple的data部分被省略。Invalid暗示是最初一个版本，每个删除大概更新会将invalid字段点窜成该事务的xid，再插入一个新的版本（更新）。该逻辑行由xid1事务插入，并依次被事务xid2和xid3更新。假定有一个和xid3并交运转的读事务T1，则xid3在事务T1的快照中，T1停止扫描的时辰，发现xid1和xid2均已经提交而且不在快照中，对T1不偏见，继续遍历下一个版本时，发现xid3在快照中，xid2不在而且已经提交，是以T1会读取该逻辑行的第二个版本，从而在更新（xid3）的同时支持无阻塞的读（T1）。T1读取的是它起头时数据库的快照。
同时，我们斟酌空间接管机制，假定计较出来的oldesetxmin满足xid2 < oldestxmin < xid3，则空间接管进程会将该逻辑行的第一个版本停止接管，从而接管空间（冷接管）大概削减页面中版本链的长度（热接管）。
我们用反证法证实oldestxmin接管算法是正确的。
证实：
接管事务为T1（xid2 < T1.oldestxmin = T2.oldestxmin，从而T1.oldestxmin > xid2 >= T2.oldestxmin（不等式1）。由T1.oldestxmin > T2.oldestxmin可以导出T1天生oldestxmin发生在T2以后。由oldestxmin天生算法可知，T1一定会读取到T2的oldestxmin，而且将T1的oldestxmin更新为小于或即是T2的oldestxmin，即T1.oldestxmin T2.commit_timestamp，则T2的点窜对T1可见。这样Percolator可以经过全局时钟来保证snapshot isolation。Percolator在底层的KV存储中为每个tuple存储多个timestamped版本，从而支持基于时钟的可见性判定。但这类全局时钟的方式仍然存在一个应战，即并发事务申请的时候戳到达每个节点的顺序纷歧定一样，能够会存在一个事务在分歧节点看到纷歧致的视图。
Percolator采用锁的机制来处理这个题目，具体的，Percolator的事务会在预提交阶段，在申请提交时候戳之前将它点窜的工具加锁。假如在这个工具在被锁后，别的一个并发读事务在拜候这个工具时，发现被加锁，则会期待锁竣事再停止tuple可见性判定，即比力时候戳。这样可以保证，若T1.start > T2.commit，则T1可以在一切节点都看到T2.commit，从而分歧性的看到T2的点窜。
正确性证实：
物理天下事务发生的依靠关系是(TrueTime暗示物理天下实在发生的切确时候):TrueTime(T1.lock)
LogicalTime(T1.commit)，则T1申请commit发生在T2收到start之前，即 TrueTime(T2.start)>TrueTime(T1.commit)。
TrueTime(T2.start) >TrueTime(T1.lock) （传递性），则T2一定可以在一切节点都看到T1写入的锁记录，从而期待T1.commit到来。证毕。
Spanner [9] 采用物理实在时候（原子时钟和GPS时钟）来供给全球大都据中心的内部分歧性（即散布式系统中很重要的特征Linearizability[11]）。Spanner给一切事务都供给实在的commit timestamp，而且返回给客户端。内部分歧性的界说：假如T2.start > T1.commit，则T2.commit > T1.commit。即对内部客户端来说，假如T2起头请求发生在T1的提交以后，Spanner保证T2的提交时候戳s2一定晚于T1的提交时候戳s1。
Spanner经过TrueTime API来供给带有误差bound的时钟，即[time-delta1, time+delta2]。为了避免时钟误差带来的毛病，Spanner的事务在提交阶段会加入Wait来期待实在时候已经过了分派给它的时钟，从而容忍机械之间的时钟误差（ms级此外skew）。
具体的时钟算法以下:
调和理点e1.commit（T1提交返回成果）和e2.start（起头T2事务）两个事务，而且TrueTime(e1.commit) < TrueTime(e2.start)。
则调和理点给T1分派提交时候戳为s1，同期间待跨越它的时钟误差再倡议e1.commit，这样保证s1 < TrueTime(e1.commit)
同时TrueTime(e2.start) |
本帖子中包含更多资源
您需要 登录 才可以下载或查看，没有帐号？立即注册
x
|
[复制链接]
发表于 2019-10-20 10:08:20
发表于 2019-10-20 10:08:41
楼主
