Deterministic in Database

Aria: A Fast and Practical Deterministic OLTP Database

0x00 引言

Aria这篇Paper描述乱一种Deterministic OLTP Database的设计，Deterministic Database的一个特点，没有通信的几个副本各自的执行一系列的事务之后，能得到相同的结果。简单的实现的话，使用单线程顺序执行的话，就能够得到相同的结果。但是这样就会带来比如性能上面的一些缺点。目前的一些Deterministic Database要实现这样的效果，一个问题是要提前制定一个事务要访问那些数据，即在事务执行之前就可以知道write set和read set，然后事务的执行顺序进行一个排序，要求后面事务执行的结果等同于以某个顺序执行的结果。确定这个顺序的方法有比如根据dependency graphs的方法，比如ordered locks的方法，后者是calvin database使用的方法。而Aria则不需要预先知道一个事务需要访问那些数据。Aria的基本思路是先使用一个sequence layer，确定事务的一个顺序，然后批量地执行这些食物，执行一个batch之后对执行结果进行检查。这个batch的执行可以是并发的，这样需要在执行完成之后对结果进行检查，确定其结果和按照之前决定的顺序执行的结果相同，然后commit。

0x01 基本设计

其基本的算法描述如下，其核心是通过事务将会访问的write set和read set来发现不能保证得出确定性结果的冲突。其事务的执行访问Execution Phase和Commit Phase，都是batch方式执行的，每个batch并发执行。事务执行之前会被一个sequence layer赋一个TID，事务执行的时候，每个事务都是从目前数据库的snapshot来读取，执行事务的逻辑，将要写入的数据保存到一个local write set中。在执行完成之后，会计划一个write set中对应的write reservations，这里记录下每个write数据的遇到的最小的事务的TID，不能处理reservation的时候事务就需要abort，在处理reservations操作之后如果有一个reservation操作不成功，则可以提前abort。这个reservation操作以执行T1: x=x+1,T2: y=x−y,and T3: x=x+y为例，T1执行完成之后，table中记录下{x : T1}，执行T2的完添加一个{y : T2}，而后面执行T3的时候则不能完成reservation操作，x以及被T1 reservation了而且T3的TID更大，T3事务会被abort。而如果是T3在前面的话，则T1可以更长reservation的table，后面在commit的时候，通过HasConflicts检查来发现其不能满足commit的条件，而被abort。在HasConflicts中，也会检查读写之间的冲突，其keys为writes set和read的并。这些abort的事务会被调度到下一个batch中被执行。其如何可以满足Determinism 和 Serializability特性在paper中有详细证明。

Function: Execute(T, db)
  Read from the latest snapshot of db
  Execute to compute T’s read/write set # (RS & WS)

Function: ReserveWrite(T, writes) 
  for each key in T.WS:
     writes[key] = min(writes[key], T.TID)

Function: Commit(T, db, writes)
  # T aborts if writes are not installed
  if HasConflicts(T.TID, T.RS ⋃ T.WS, writes) == false:
    Install(T, db)

Function: HasConflicts(TID, keys, reservations) 
  for each key in keys:
    if key in reservations and reservations[key] < TID: 
      return true
  return false
 
Function: Install(T, db)
  for each key in T.WS:
    write(key, db)

deterministic reordering

这前面的基本思路只是，可以通过reservation table和write set，read set检查的方式来发现不能满足Determinism 和 Serializability特性的情况，另外，这里可以通过一些reordering的方式来减少一些abort的情况。比如下面的例子，T1: y=x,T2: z=y,andT3: Print y+z，因为T2，T3读取了T1写入的y，所以这里只能有T1倍提交，而T2和T3得被abort。但是如果能被确定性地重写排序为 T3 → T2 → T1，则都可以commit。这里reorder的算法表述如下。这里引入了一个write一样的ReserveRead，HasConflicts的检查被分为了三个部分，一个是写写冲突的就擦好，另外一个是WAR和RAW的检查。WAR检查的时候使用了ReserveRead给出了reads集合。

Function: ReserveRead(T, reads) 
  for each key in T.RS:
    reads[key] = min(reads[key], T.TID)
    
Function: Commit(T, db, reads, writes)
  # T aborts if writes are not installed 
  if WAW(T, writes):
    return
  if WAR(T, reads) == false or RAW(T, writes) == false:
    Install(T, db)
    
Function: WAW(T, writes) = HasConflicts(T.TID, T.WS, writes) 
Function: WAR(T, reads) = HasConflicts(T.TID, T.WS, reads) 
Function: RAW(T, writes) = HasConflicts(T.TID, T.RS, writes)

加入了reorder优化之后，这个实际上就是检查表述为下的条件是否满足，

Rule 2. A transaction commits if two conditions are met: 
(1) it has no WAW-dependencies on any earlier transaction, and 
(2) it does not have both WAR-dependencies and RAW-dependencies on earlier transactions with smaller TIDs.

Aria的设计应该是假设一个副本的数据都是在一个结点上面的，这个条件可能会带来一些限制。

0x02 评估

这里的具体信息可以参考[1].

KuaFu: Closing the Parallelism Gap in Database Replication

0x10 基本内容

这篇Paper是关于数据库Replication并发replay的一个优化，和Deterministic Database不同。主要是如何实现从节点如何实现并发replay主节点上面的操作，要求达到和主节点中一样的状态。为了保证得出和主节点一样的结果，目前采用的方式非并发的顺序执行主节点以某个顺序执行的操作，这个和前面的Deterministic Database有些类似的地方，如果看作主节点是sequence layer，感觉就更像了，不过这里要求主从之间是有连接的。KuaFu实现这样的思路也是使用图的方式，使用图来刻画有依赖关系的事务之间的前后关系，在从节点上面replay操作的时候以满足这个顺序要求来replay，以得出和主节点一样的结果。

0x11 基本设计

KuaFu实现在MySQL上，其复制逻辑在SQL Layer，这样的好处就是适应MySQL这样的Storage Engine可选择多种的情况。但是也进行了一些变化，比如KuaFu选择row-based logging的方式，会记录下那些行被修改，而不是statement logging的方式。主要是因为statement logging虽然logging的大小会小一些，但是其处理RAND，DATE会比较麻烦，还有就是不能知道会修改那些行，就不能得出其dependencies graph。而row-based logging则处理起来比较简单，

 During replay, two transactions are in conflict if and only if their write sets intersect. Not having to worry about read-write conflict simplifies implementation and increases the degree of parallelism. ... . A backup needs only to update the rows with the values in the log, without worrying about the read set of each transaction or re-executing SQL statements.

KuaFu的基本算法表述如下，其从next_trx_from_parser中解析出log中的事务操作，并获取write set的内容，然后利用write set的数据构建一个事务之间的依赖关系。如果是目前没有执行的事务里面没有一个事务依赖的事务，就可以直接添加到ready_transactions队列里面。在执行的时候，直接从ready_transactions队列里面拉出来一个事务执行，在执行完成之后更新dependencies graph。那些依赖于这个事务的，如果其变得没有其它依赖了，这些就可以满足执行添加，从而可以添加到ready_transactions队列里面，准备执行。

graph = empty_set() 
ready_transactions = empty_queue()
dependency_tracker() {
  while( trx = next_trx_from_parser() ) {
    trx.extract_writeset() 
    vertex v = new_vertex( trx ) 
    for each u in graph {
      if( u.writeset intersects with v.writeset ) {
         u.followers.push(v)
         v.n_incoming_edges++ 
      }
    }
    graph.insert(v)
    if( v.n_incoming_edges == 0 )
      ready_transactions.push(v)
  }
}

executor() {
  // executed in each executor thread 
  while( v = ready_transaction.pop() ) {
    execute_transaction( v.trx ) 
    for each u in v.followers {
      u.n_incoming_edges--
      if( u.n_incoming_edges == 0 )
        ready_transaction.push(u)
    }   
  }
  graph.erase(v) 
}

这种方法可以看作是一种悲观的方法，而SAP HAHA中基于MVCC，执行之后检查一条记录的前后版本来检查是否满足顺序关系的不同，后者更像是一种乐观的方法。KuaFu这里也利用MVCC来处理一些问题，其满足的是prefix consistent ，即从节点上更新的内容是主节点更新操作的一个preifx。这里有一个read inconsistency的问题需要处理。对于2个在主节点上前后执行的事务T1、T2，在从节点上是可以以T2->T1的顺序执行的。这样另外一个读操作的时候，可能看到了T2在从节点上的更新，而没有看到T1的，这样就不能满足prefix consistent的特性。为了处理这个使用了一个consistent reader，从节点replay更新操作的时候，会没n个更新记录一个barrier，这个barrier之前的更新都完成才能去处理后面的操作，然后使用MVCC的方式，在记录一个barrier之前数据库的一个snapshot，对于读请求，读取这个snapshot中的数据。

0x12 评估

这里的具体谢谢可以参考[2].

参考

  1. Aria: A Fast and Practical Deterministic OLTP Database, VLDB ‘20.
  2. KuaFu: Closing the Parallelism Gap in Database Replication, ICDE ‘13.

Recent Posts

Emmmmmmm

Recommended Websites