Linearizability 与 Serializability

我们这里讨论 linearizable 和 serializable 这两个概念。

linearizability 和前面谈到的 atomicity 是等价的概念,这里稍微提一下它另外一种阐述的形式以便与 serializability 比较(参考 wiki)。我们首先定义 history 的概念,这个上下文是我们使用 OOP 描述世界,对象之间的交互通过 invocation 和 response 来进行(每一个 invocation 一定会导致对应的 response),简单的说一个 atomic object 就是对应的行为(invocation/response)表现出来不会因为 concurrency 而中断或者产生 variance,但这样的描述不能更精确的表述这个概念,为此我们引入 history 这个概念,它是一个 invocation、response 的序列,可以由一组线程产生。比如一个 lock 对象,两个线程 AB 分别试图上锁,对应的 history 可能是 A lock、B lock、A 获得失败响应、B 获得成功响应。一个 history 称为 sequential history 当且仅当所有的 invocation 立即跟着对应的 response,那么前面的例子显然不是。当然 sequential history 很容易 reason。一个 history 称为 linearizable 当且仅当

  • 如果其 invocation、response 通过重新排序可以成为 sequential history
  • 重排获得的 sequential history 存在一个满足对象本身的 sequential definition(如果对象本身的状态会对行为产生影响,虽然没有必然关系,这里是说如果有关系必然满足)
  • 若在原 history 里面某个 response 出现在某个 invocation 之前,它在重排获得 sequential history 时仍然应该保持这个顺序

以上例子满足这三点,因为我们可以重排成为 B lock、B 获得成功响应、A lock、A 获得失败响应,最后一点很重要它允许 response 之前的 invocation 颠倒顺序但不允许之后的 invocation 到其之前。

与 linearizability 类似的是 serializability,它只要求以上三点中的前两点:从这个意义上来说 serializability 是相对更弱的 consistency model,可能获得更强的 concurrency。一个常见的例子是数据库使用 transaction 方式将操作弄成 ACID,类似的也有考虑将 memory 弄成类似的 STM,它们往往选择 serializability 作为自己的 consistency model。

数据库的 transaction 实现通常有两个技巧,write-ahead loggingshadow paging

  • WAL (参看 sqlite 相关文献)常常是与 rollback journal 相比较的,区别在于 rollback journal 是将原始 page 写入到 journal 中然后将新内容覆盖原先的 page,这样在 rollback 的时候将 journal 中的 page 恢复即可;WAL 恰好相反,原始内容仍然放在原先的 page 里,新的内容首先写入到单独的 WAL 文件里,这里的想法其实和硬件上做 store buffer 类似,WAL 就是一个 store buffer,为了 transaction 的 ACID 性质,类似 snooping 的技术也被用来保证一个 transaction 只读到需要的位置:store buffer 在读的时候相当于是从 cache 和 store buffer 两者里面取值,类似的一个 transaction 产生写操作就会在 WAL 里面留下新的值以及对应的“end mark”,另外的 transaction 在读取的时候也会使用对应的 end mark 来做 filtering,也就是说看看 WAL 中小于该 end mark 的最后一个对应的值是否存在,否则就从原始数据库里面读取(从这点看软件实现的结构比起硬件还是复杂了很多,为了高效的实现这个部分通常会使用 WAL index 这类特殊的数据结构);WAL 里面的数据达到某些 checkpoint 时就会写入到数据库里面,但是为了避免 active transaction 中某个读取产生错误,我们只能将 active transaction 所有 end mark 中最小之后的 WAL 记录写入到数据库,这在存在 long read transaction 的时候就可能出现问题
  • shadow paging 这个策略其实跟 pure functional programming 里面常用的“immutable data structure”类似,使用的技巧是 copy-on-write,先建立新的 page 写入数据,之后将引用原始 page 的部分递归的改变成指向新的 page(由于这个过程可能导致好几轮的 recursion,性能上往往会被人诟病),这个地方如果需要考虑 isolation 的要求感觉更加 tricky

我们可以看到为了最大化 concurrency,特别是让写操作不会 block 读操作,数据库这两个技术都是尽量将写孤立到一个不影响读的区域(新 page)直到最后将其 flip on。在并发的 transaction 下,数据库为什么需要 serializability 呢?其实很多时候一个系统都面临两难的要求:correctness 和 performance,如前面所讨论,绝对的正确可以用 sequential history 获得,但这个基本上也就扼杀了 concurrency 的可能性;如果对 transaction 的执行不加约束,我们就会造成数据错误。而研究的比较多的 serializability 有几个重要的性质,

  • serializability 提供了一定 reasoning 的可能
  • 判定一个 history 是否是 serializable 的是 NPC(我们无法有效的对 general 的 history 判定是否能获得 correctness)
  • 因此我们需要在某一些 history 子类上来进行判定才可能获得有效的算法
  • 同时一旦发现 non-serializable 的 transaction 出现,transaction 必须得 rollback(atomicity)
  • concurrency control 体现在 transaction 上很重要的就是 isolation:什么 dirty read 呀之类的

也有人尝试使用 linearizability(见这里),有机会也来看看。常见 concurrency control 分为

  • optimistic:延迟对 isolation、serializability、recoverability 的检查,这样就不会 block 对应的读写,如果之后发现问题违背了这些条件就 abort(导致 rollback)
  • pessimistic:一旦有可能出现违背以上性质的可能就首先 block,这样获得了唯一的权限后就可以避免违背,很显然这会降低并发性
  • semi-pessimistic:前两者的混合,对某些情况使用锁,某些情况使用延迟检查

具体的一些方法包括

  • 2PL(2 phase locking),常见的是 SS2PL
  • serialization graph checking,在某个子类里面可以通过对应的 serialization graph 是否有环来判定 serializability
  • timestamp ordering,每个 transaction 包括一个时间戳,执行时根据时间顺序来检查,似乎 google 的 F1 使用了高精度时钟就是为了这个?
  • commitment ordering,根据 precedence ordering 来顺序来检查

似乎后两者都是 optimistic 的。看来这边水还有点深… 谬这方面的经验一时半会弄不懂。

——————
Thus have I been twenty years in thy house; I served thee fourteen years for thy two daughters, and six years for thy cattle: and thou hast changed my wages ten times.

Advertisements
Linearizability 与 Serializability

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s