SLOG

发表于 更新于 分类于 阅读次数：

背景

Geo-replicated DBMS

SLOG假设一个数据库系统是跑在横跨世界各地的数据中心的系统，这种系统我们通常称之为Geo-replicated Database Management System(DBMS)，它将数据复制多份在各地的资料中心中。

下图展示了一个分布在三个地区的数据库系统。通常一个数据中心会持有一份完整的数据，然后每个数据中心中的数据会再切分成多个不相交的partition。在下图之中，一共有三分备份(replica)，然后每个数据中心内有三个partition。数据中心之间会需要时常同步数据来保证数据的一致性。

Geo-replicated DBMS

跨区域备份的架构主要有两个目的：

  • High Available：因为数据有多个备份，当某个备份无法服务的时候就可以由其他备份提供服务。
  • Low Read Latency： 可以优先从地理位置较近的数据中心更快地读取需要的数据。

motivation

分布式数据库系统有三大目标：

  • Strict Serializablity
  • Low Latency
  • High Throughput

到SLOG为止，这时目前尚未有人能够完美同时解决的问题。

例如，要实现strict serializability，通常需要通过协调(coordination)来得到全局的事务顺序，但这会导致write latency较高。如果使用weak consistency（如snapshot isolation)能够同时保证low latency和high throughput，但是又不是strict serializability。

论文发现

SLOG依赖了两个主要发现来达成以上目标：

  1. 使用者通常都会在同一个地区（数据中心）存取自己的数据
  2. 并非所有transaction之间都一定要有global order，不冲突的transaction之间的顺序可以排序。

第1点说的就是数据局部性问题，用户的写入和读取大多都在同一个数据中心。

第2点举例来说，如果有两个事务T1、T2，T1修改数据A，T2修改数据B，那么T1、T2谁先谁后都不影响结果。因此这两个transaction无论如何排序，都不影响serializability。

SLOG概念

Home Region

每一组 records 可能会被跨数据中心复制很多份 replica，但是只有一份 replica 是主要的 (primary)。 存放这个主要的 replica 的区域就叫做 home region。 这个时候，一般马上就会想到 master-slave 架构。 那 SLOG 跟那种架构又有什么不同呢？ 主要差异是，在常见的 master-slave 架构之中，replica 通常是以整个 database 作为单位，其中 primary replica 一定是整组 database 放在同一个区域中。但是 SLOG 提出的架构是以一组 records 作为单位。也就是说，可能有些 records 的 primary replica 在台湾，有些 records 在美国。 如下图所示，每个方块代表一组 records。 黑色代表 primary。 A 组的 home region 是 region 1，B 组则是在 region 2。

Home Region

还需要注意的是在一个partition（一个物理机器）中，并不是所有的records都是primary，如下图所示。

sortledton-2

那么怎么得到一个record的home-region呢?SLOG在每个region设立一个LookupMaster index，它保存的是record id到record metadata的映射，而record meta由两部分组成，第一部分是该record的当前home-region，第二部分是该record的home-region改变次数（后面有用）。

每个Record中也含有这个metadata，并且当record的metadata被更新的时候，更新LookUpMaster Index。

SLOG将事务分成两类：single-home transaction和multi-home transaction

Single-home Transactions

如果一个事务存取的数据的home region都在同一个region，这种transaction被称作single-home transaction。如下图所示，T1、T2、T3、T4都是single-home transaction。

对于single-home transaction，我们只需要在home region内做冲突处理，其他数据中心的replica只要确保有复制到home region的结果就好。因此SLOG在home region完成transaction之后，就会把log复制到slave。一旦有N个数据中心回复（N由使用者设定），就可以回复client该transaction完成。如此以来，就可以省下跨数据中心的coordination带来的多个round-trip time。

image-20221010230820560

举个例子，T1、T2都只访问数据A，而数据A的home region是region 0，因此T1、T2会在Region0上进行冲突处理（client发送transaction到最近的region，即使被发送到了region1，也会被转发到region 0上）。T3，T4被送到region 1上进行冲突处理。对于single-home类型的transaction，它首先写日志到local log，当local log收集到一批事务日志后，通过paxos发给其他region。global log是全局的事务顺序，它既包含本地local log的日志，也包含从其他region接收到的log，因此每个region的global log顺序可能不一致（但是T1一定在T2之前，T3一定在T4之前）。但是因为它们都是single-home transaction，即使顺序不一致也能保证结果的一致性，因为它们的存取的数据不相交（这也就是论文发现的第2点）。

Batch 0-1 0代表的region id，1代表batch id

global log的顺序确定好之后，region只需要从global log取log然后执行就可以了。

multi-home transactions

如果事务都是single-home的，那就皆大欢喜了，可事实却肯定并非如此。如果一个transaction访问的数据home-region不止一个，那么就称为multi-region transaction。如果figure 3的T2不仅要访问A，还要访问B，那么按照figure 3的方式得到的global log是有问题的，会导致region间数据不一致性。比如region0和region1对数据B最后写入的是T4，而region2最后写入的是T2，导致region0和region2，以及region1和region2的状态不一致。

对于multi-home transaction的处理，我们可以分为multi-home transaction跟multi-home transaction之间的冲突处理，以及multi-home transaction跟single-home transaction之间的冲突处理。

multi-home transaction 跟multi-home transaction之间的冲突处理

SLOG采用deterministic database的概念，在一开始先把所有 multi-home transactions 通过一个 total ordering protocol 进行排序，确定了这些 transaction 的 global order 后，再送到 deterministic execution engine 执行，以确保 consistent 的结果。

如下图，Tx G.1 与 Tx G.2 无论送到哪个 region，都会被强制送进 total ordering layer 进行全域的排序之后，再送到下面的系统开始执行。

Multiple Home - Total Oredering

只要保证了事务的全局顺序，那么multi-home transaction和multi-home transaction之间的就完成了并发冲突。

multi-home transaction跟single-home transaction之间的冲突处理

上述的方案能够结果multi-home和multi-home之间的冲突，但是解决不了mutli-home和single-home之间的冲突。

mh-mp-2

上图中T1和T3是single-home transaction，而T2和T4是multi-home transaction。从上图可以看出multi-home和multi-home transaction间有序（T2在T4前面），但是和single-home transaction间却导致了乱序，这也会导致region间数据不一致性问题。如何解决？加锁。

image-20221011001507539

figure4所示，T1、T3、T4为single-home，T2为multi-home transaction。T2在total order module排序出来后，会生成T20和T21两个事务（因为T2涉及两个home region，需要为每一个region都生成一个），这两个事务叫做LockOnlyTxn。T20用来锁住数据项A，T21用来锁住数据项B。single-home transaction对数据读取的时候也需要进行加锁，而multi-home transaction（图中没有画出，我把它称作T2，它出现在global log的任何地方都不影响数据一致性，不相信的话可以举个例子）要执行的时候，必须拿到所有的锁（T20和T21执行）才能够执行，否则会阻塞。

home-region的更换

client发送的transaction是发给最近的region，但是此region可能不是home-region，因此这个region会将这个事务发送给home-region。如下图所示。事务T1存取B，它被client发送给了T1，但是T1要访问的数据B的home-region是region1，因此T1被转发给region1.

image-20221011003542954

但是这种转发的次数多了肯定影响性能，因此我们希望设定一个阈值（比如region0连着三次都在转发），那么我们希望把B的home-region变更到region0，充分的利用局部性原理（也就是论文发现的第1点），论文把这种行为称为remaster。

但是简单的remaster也会导致region间数据的不一致性。例如在上图中，事务T1、T2、T3都有存取数据B，T1被转发给region1，而Tremaster事务要将数据B的home-region改为region0。当remaster事务执行后，home region改变了，那么T3的home region就不应该在region 1了，而应该是region0，所以T3 abort，并得到T3new，发送给region0。由此得到的global log如图figure 5所示。

那么这么得到的global log就会导致region间的不一致，region0和region1的事务顺序是T1、T2、T3，而region2的事务顺序是T1、T3、T2。

remaster导致的不一致性解决方案

为了解决remaster导致的region间数据不一致性问题，我们通过record的metadata中的counter（也就是该record的home-region被更改了几次）来解决。我们通过举个例子来理解。

当事务T被发送个第一个region时（比如T1发给region0），region0首先通过LookUpMaster查找该record的metadata，并将此metadata信息插入到事务中。因此T1可以表示为T1(1,0)，1代表它的当前home region为1，0表示home-region改变了0次。类似的，T2(1,0)，T3(1,0)，T3new(0,1)。

当我们要对该事务事务涉及的数据项上锁时，会将事务中的数据项counter和region中数据项的metadata中的counter进行比较。如果前者更大，那么说明本region还没有处理remaster请求，因此需要阻塞该事务等到remaster请求被执行后再换行。如果后者更大，那么说明LookupMaster Index中的映射是stale的，本事务应该abort。

image-20221011140318225

实验结果对比

为什么slog吞吐率低于Calvin？

导致slog吞吐率比calvin低最主要的原因是multi-home事务的存在，在calvin中没有multi-home的概念，因此calvin不受multi-home的影响。

xxxxxxxxxx /client_tcp.c/#include<stdio.h>#include<string.h>#include<stdlib.h>#include<unistd.h>#include<arpa/inet.h>#include<sys/socket.h>​int main(){ //创建套接字 int sock = socket(AF_INET, SOCK_STREAM, 0);​ //服务器的ip为本地，端口号1234 struct sockaddr_in serv_addr; memset(&serv_addr, 0, sizeof(serv_addr)); serv_addr.sin_family = AF_INET; inet_pton(AF_INET, "127.0.0.1", &serv_addr.sin_addr); serv_addr.sin_port = htons(1234); //向服务器发送连接请求 connect(sock, (struct sockaddr*)&serv_addr, sizeof(serv_addr)); //发送并接收数据 char buffer[40]; printf("Please write:"); scanf("%s", buffer); write(sock, buffer, sizeof(buffer));​ memset(buffer, 0, sizeof(buffer)); read(sock, buffer, sizeof(buffer) - 1); printf("Serve send: %s", buffer);​ //断开连接 close(sock);​ return 0;}c

但是当multi-partition（跨分片）事务数量变多的时候，calvin和slog的吞吐率差距会变小，因为calvin对于跨分片的事务也需要进行协调带来额外的开销，而slog在处理multi-home的时候顺带也解决了（部分）multi-partition的冲突。

image-20221011021949992

如下图所示，T1和T2既是multi-home transaction又是multi-partition事务，calvin对于multi-partion事务需要做coordination，而slog需要对multi-home事务做coordination，因此当multi-partition的比例较高时，slog和calvin的差距就不是很明显。

mh-mp

为什么slog延迟比calvin低？

image-20221011024804253

上图曲线越靠近左边代表延迟越低。可以看出slog延迟在multi-home比例很低（也就是single-home transaction比例很高）的时候明显优于calvin。因为对于slog来说，single-home transaction每个record有它的master，只要transaction的日志写入到master（home-region）上该事务就可以返回了，然后异步地使用paxos同步日志给slave region，因此延迟比较低。而multi-home事务越多，对slog的latency影响越大。

参考文献

  1. https://www.slmt.tw/blog/2019/10/20/paper-slog/
  2. Thomson, Alexander, and Daniel J. Abadi. “The case for determinism in database systems.” Proceedings of the VLDB Endowment 3.1-2 (2010): 70-80.