《Easy Lock-Free Indexing in Non-Volatile Memory》解读

在阅读BzTree的过程中首先感觉比较晦涩的是2.3 Persistent Multi-Word CAS的内容。不过这样感觉挺正常的,毕竟在BzTree在尝试用差不多一页的内容去介绍《Easy Lock-Free Indexing in Non-Volatile Memory》这篇13页Paper,这篇Paper还有对应的工程实现

比较有意思的是这个算法提到自己是cooperative的,通俗地说,就是一个线程t1探测到某个数据正在被另一个线程t2改变,这时候它就会去帮t2把这个事情做完,发现这并不是一个很老的概念

Persistent Multi-Word CAS想要解决的问题是:如何在Persistent Memory上完成多个wordCAS

PMwCAS描述符

PMwCAS描述符是进行PMwCAS操作的基础,一个重要假设是:所有的内存地址,高3位都是没有使用的。

Modern 64-bit x86 processors employ a “canonical address” design, where the microarchitecture only implements 48 address bits, leaving the higher 16 bits unused. These vacant bits can be used to help improve the performance of persistent CAS

PMwCAS中的图 BzTree中的图

从上图中可以看出,一个PMwCAS描述符主要包含两部分内容:

  • 头部
  • Word描述符数组

对于每一个Word描述符,包括5个部分:

  • address,要操作的Word的地址
  • old valueaddress对应的内容的老值
  • new value,需要修改成的新值
  • PMwCAS descriptor address,把PMwCAS描述符的地址也存了一份,这个BzTree中的图是没有的
  • memory policy,针对new/old value的内存策略,需不需要释放

BzTree里面画的图和这个不太一样,所以很难理解。

PMwCAS操作

PMwCAS操作分为两阶段。

Phase 1: Installing Descriptors

将所有需要操作的Word的内容改成这个PMwCAS描述符的指针。

下面的Paper中的伪代码对于理解这一阶段的操作非常有帮助:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# 入参的wdesc是每个word的描述符,paper中说是用了RDCSS的方法
# double compare single swap
# 这里感觉并没有把DCSS描述得特别清楚
def install_mwcas_descriptor(wdesc):
# 这个ptr是把word描述符的指针加上RDCSSFlag
ptr = wdesc | RDCSSFlag
retry:
# 尝试将word.address的指针设置为ptr
val = CAS(wdesc.address, wdesc.old_value, ptr)
# 如果CAS返回的是一个word描述符的指针
if val & RDCSSFlag is not 0:
# Hit a descriptor, help it finished
# 表示已经被某一个PMwCAS操作先“锁”住了,帮忙别人完成描述符的install
complete_install(val & AddressMask, val)
goto retry
# 如果val的值就是word.old_value,那么说明前面一个`CAS`成功了
if val == wdesc.old_value
# Successfully installed the conditional CAS descriptor
complete_install(wdesc, val)
# 这个时候val也有可能是一个PMwCAS描述符的指针,或者是一个新值
return val
# 完成对wdesc的install,即将wdesc。address的内容设置为wdesc所属的mwcas_descriptor
def complete_install(wdesc, val):
mwcas_ptr = wdesc.mwcas_descriptor | MwCASFlag | DirtyFlag
# 这里判断wdesc.mwcas_descriptor.status是否是Udecided的原因
# 可以看下面的说明,也就是使用RDCSS时举的例子
# 感觉这个完全是因为引入了cooperative之后带来的复杂性
u = wdesc.mwcas_descriptor.status == Udecided
CAS(wdesc.address, val, u ? mwcas_ptr : wdesc.old_value)

这里引入了另外一个技术:RDCSS:Restricted Double Compare Single Swap,来源于另外一篇论文:《A Practical Multi-Word Compare-and-Swap Operation》。

Paper中对引入RDCSS的原因的描述还是挺难以理解:

Specifically, we must guard against the installation of a descriptor for a completed PMwCAS (p1) that might inadvertently overwrite the result of another PMwCAS (p2), where p2 should occur after p1. This can happen if a thread t executing p1 is about to install a descriptor in a target address a over an existing value v, but goes to sleep. While t sleeps, another thread may complete p1 (given the cooperative nature of PMwCAS) and subsequently p2 executes to set a back to v. If t were to wake up and try to overwrite v (the value it expects) in address a, it would actually be overwriting the result of p2, violating the linearizable schedule for updates to a. Using RDCSS to install a descriptor ensures not only that the target word contains the expected value but also that the status is Undecided, i.e., that the operation is still in progress.

对照着代码里面的注释看会更加清晰一些:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/// T1 mwcas(A1 [1 - 2], A2 [3 - 4])
/// Suppose T1 went to sleep after installed descriptor on A1.
/// T2 comes to help the mwcas operation and finished.
/// Now A1=2, A2=4.
/// 这里举的例子是T1想改两个值A1、A2,然后在A1上install了自己描述符指针后就被换出了(还在Phase1阶段),
/// 这时候T2进来,把T1的Phase1/Phase2帮忙都做完了(居然还可以这样,上面的伪代码里面并没有描述得这么详细)
/// Suppose T3 now conducted an mwcas that reversed the previous mwcas:
/// Now A1=1, A2=3 again.
/// 这个时候T3发起了另外一个mwcas,把值又改回去了。
/// Suppose T1 now resumes execution, it will continue to install
/// descriptor on A2, which will succeed because it has value 3.
/// T1 then continues to CAS in new values, which fails for A1 but the
/// algo will think it's ok (assuming some other thread did it). The
/// installation for A2, however, will succeeded because it contains
/// a descriptor. Now A1=1, A2=4, an inconsistent state.
/// 这个时候被换出了好久好久的T1回来了,这时候它继续自己Phase1的操作,在A2上install自己的描述符指针
/// 这时候因为A2的值被改回了3,所以Phase1是可以执行可以的。进入到Phase2阶段,Phase2阶段去操作A1
/// 将新值设置到A1中时会失败,但是会去忽略它;但是操作A2的时候会成功。这样就是一个不一致的状态。

Phase2: Completing the MwCAS

Phase2的操作相对会简单一些,需要先持久化PMwCAS描述符的状态,然后根据这个状态对每一个word进行设置或者回滚。

这里Paper中的伪代码涵盖了Phas1Phase2的操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
bool PMwCAS(mdesc):
st = Succeeded
for w in mdesc.words
retry:
rval = install_mwcas_descriptor(s)
if rval == w.old_value or rval & AddressMask == mdesc:
# Descriptor successfully installed
continue
elif rval & MwCASFlag is not 0:
# 如果rval是另外一个PWmCAS_desc的指针,先帮它完成,然后再retry
# 如果retry发现word的值已经改变了,那么这次PMwCAS就会失败
if rval & DirtyFlag is not 0:
persist(w.address, rval)
# Clashed another on-going MwCAS, help it finish
persistent_mwcas(rval.Address)
goto retry
else
# 如果是其它情况,也就是w.address指向的内容已经是一个新值了,需要break了
st = Failed
break
# 如果成功,持久化每个word描述符的内容(也就是这个描述符的指针)
if st == Succeeded:
for w in mdesc.words
persist(w.address, mdesc | MwCASFlag | DirtFlag)
# Finalize the MwCAS's status
# 这里不需要判断CAS的返回值,因为有可能别的线程完成了
CAS(mdesc.status, Undecided, st | DirtyFlag)
# 需要先持久化mdesc.status的值,Recovery的时候需要依赖这个值来判断是往前回滚还是往后回滚
if mdesc.status & DirtyFlag:
CLWB(&mdesc.status)
mdesc.status &= ~DirtyFlag
# Install the final values
for w in mdesc.words:
# 判断mdesc.status是成功还是失败,如果成功,就设置为w.new_value;如果失败就回滚
val = mdesc.status == Succeed ? w.new_value : w.old_value
# 只有那些w.address已经设置为这个mdesc的指针的word才需要被修改
# 如果mdesc.status是成功,是不是意味着所有的mdesc.words的address指向的内容都是这个mdesc的指针
expected = mdesc | MwCASFlag | DirtyFlag
rval = CAS(w.address, expected, val | DirtyFlag)
if rval == mdesc | MwCasFlag
CAS(w.address, expected & ~DirtyFlag, val)
# 其实忽略了rval,如果这个时候w.address对应的值跟mdesc没关系也不会去处理
persist(w.address, val)
return mdesc.status = Succeeded

其它

Reading Affected Words

对于PMwCAS中的操作而言,读取一个地址的内容,可以会遇到下面几种不同的情况:

  • 带有RDCSSFlagword描述符
  • 带有MwCASFlagPMwCAS描述符
  • 普通值

那么PMwCAS宣称是一个cooperative的算法,自然不会无脑retry,而是会帮助其它的线程完成它们没有完成的工作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def pwcas_read(address):
retry:
v = *address;
if v & RDCSSFlag:
complete_install(v & AddressMask)
goto retry
if v & DirtyFlag:
persist(address, v)
v &= ~DirtyFlag
if v & MwCASFlag;
persistent_mwcas(v & AddressMask)
goto retry
return v

Recovery

恢复有两点要求:

  • 在进行Phase1之前,整个PMwCAS描述符的内容需要持久化。
  • PMwCAS描述符的状态字段在进行Phase2之前需要是持久化的。

进入Phase2之后,address的内容就可以被其它的线程读取了。状态字段持久化之后,在Recovery阶段就可以决定是向前回滚还是前后回滚了。

这里有个问题是,需要判断address的内容是否是PMwCAS描述符的地址,所以要求重启之后PMwCAS描述符的地址是不变的,所以Paper里面提到了PMwCAS描述符池使用的是一片固定的区域。

memory policy

之前提到了word描述符中有一个字段叫memory recycling policy,直接看Paper里面的表就ok了,写得非常清楚:

最后

感觉BzTree这篇Paper还是挺难的,基础部分的PMwCAS就是这一篇大文章。从作者的主页才知道这篇Paper是中了ICDE 2018