背景：高性能网络互联技术提高了节点间通信的速度，为DSM实现节点间缓存一致性提供了机会
做了什么：提出了GAM
测试：测试GAM在不同负载下的读写锁性能，对事务引擎和分布式哈希表进行测试
shared-memory和shared-nothing对比
现有DSM提供缓存来缓冲远程内存访问，以减少网络延迟；但是为了维持缓存数据一致性，需要同步原语来更新缓存中的数据，开销过大；而且这需要程序员来完成
现在RDMA技术几乎接近本地访存、甚至比NUMA的吞吐量都大，但是还是需要程序员来完成同步原语
一种方法是不用缓存，直接向数据所在节点进行读写，但是这样延迟太太大了
所以本文提出了GAM，保留了缓存功能，利用RDMA来实现高效的缓存一致性协议
采用PGAS(Partioned Global Address Space)内存模型，逻辑上统一的地址空间+机器间通过RDMA互连+每个节点管理自己的那块内存
API分为访问全局内存空间操作和同步操作两类，前者是malloc/free和read/write，后者是atomic、mfence、rlock/wlock、tryrlock/trywlock、unlock
虽然RDMA很厉害，但是本地访问和远程访问之间的延迟还是差10倍。大多数应用都有数据局部性的特点，利用这点可以利用层次化内存架构，来减少访问较低层次的内存的需求。GAM在全局内存之上，增加了一层DRAM的缓存
这个缓存层不采用窥探协议是因为，RDMA网络不适用，所以采用了基于目录的协议，即维护一个目录，记录数据块的信息，当需要同步缓存时，点对点通信，而非窥探式的广播
GAM有三层缓存层，最高层是由硬件实现的NUMA节点内的基于窥探的协议，第二层是由硬件实现的NUMA节点间的基于目录的协议，最底层是由软件实现的本文提出的协议，接下来说下这层的协议
对于每块数据而言，节点们可以被分为五种类型，home数据的物理内存所在节点，remote非home节点，request请求对数据进行访问的节点，sharing拥有读权限的节点，owner拥有写权限的节点
最初，数据在home上，home既是sharing也是owner，如果有remote变成了request，那么home就会把权限给过去，该remote就会被提升为sharing或者owner。对于一个数据块而言，可以同时有多个sharing，但是只能有一个owner，且sharing和owner不能同时存在。这种缓存效果可以利用数据局部性
缓存的粒度，默认是512bytes，比硬件的要大，这样能减少小数据包传输的开销(因为每次传输有固定开销)，并且这个数字是在平衡了网络带宽和延迟之间做的选择
每个缓存行都有状态，对于home，有unshared、shared、dirty三种状态，对于remote，有invalid、shared、dirty三种状态，状态间的转换不是原子性的，所以又引入了中间的过渡状态
读操作分为local和remote两种，前者指的是home作为request，后者指的是remote作为request。
对于local，如果Cache line是shared/unshared，那么直接读；如果是dirty，需要查Directory entry，然后找到owner，owner要把本地copy发给home，并且把Cache line从dirty改为shared，home收到copy后会更新memory line，并且更新directory entry到shared
对于remote，如果请求的数据在缓存里面且不是invalid，则可以直接读；否则需要从home那拿数据。如果home是dirty，那么需要找到owner，然后owner会把数据给home和request，并把三者改为shared；如果home是non-dirty，那么home会把数据给request，并把两者改为shared
对于local，cache line可以分为dirty/shared和unshared两种，后者可以直接写，前者需要invalidate其他node，然后等得到acknowledge之后，再去写，当cache line为dirty时，owner需要把最新的值给home
对于remote，如果remote是owner，那可以直接写。如果不是，需要找home，home如果是shared，那么home需要先invalidate其他shared节点，然后再把ownership给remote；如果是unshared，则直接把ownership给remote；如果是dirty，则request找home，home找owner，owner把cache line给request，把message给home，home给request发ack，之后request才开始写
如果request里面有俩线程要对同一个数据块进行读写操作，则会发生竞争。故引入in-transition状态，即会把缓存行改为这个状态，如果后续再有对该缓存行的读写操作，则会发生block，直到前面的读写操作完成。
如果一个sharing节点想要变成owner节点，则会向home发送WRITE PERMISSION ONLY，此时位于sharing结点的cache line会进入转换状态；此时home节点也想从sharing变成owner，则会向所有其他sharing节点发送invalidate，并且把自己的cache line变成转换状态。这就陷入了死锁。这个解决策略我还没有看特别明白，但是大致理解的意思是，invalidate特权比较高，遇到这个之后需要回退状态
GAM有多个LRU表，以牺牲准确性来换取性能。每次全局内存访问和缓存行驱逐，都是随机选择一个LRU表。
如果要驱逐的缓存行是invalidate，那么直接eviction；如果是shared，那么需要把eviction请求发送给home，以更新slist，发送之后就可以把该缓存行分配给其他数据了；如果是dirty，eviction请求会附加一个缓存行的副本，home收到之后会发送ack，当ack收到后，才会把该缓存行分配给别人
目前GAM还没法处理out-of-global-memory，后期会用on demand paging来处理，即在需要时动态加载和卸载内存页
协调本地和远程内存访问，实现缓存一致性的是一个coordinator。整个system里面有一个master，用来初始化和状态跟踪，它位于一个node之内。上层应用程序看到的内存是一个统一的模型，可以在不知道数据实际位置的情况下访问集群中的全部内存
RDMA可以绕过CPU和OS来直接访问远程内存，但是具体如何实现，并非易事。在RDMA中传输数据有两组verbs，分别是READ/WRITE和SEND/RECEIVE。前者是one-sided，只有请求方参与；后者是two-sided，还需要接收方做一些操作。通常来讲，前者比较好，因为块。但是one-sided很难确定数据何时传输完成。
把传输分为控制消息通道和数据传输通道，前者是two-sided，后者是one-sided。因为控制消息小且需要立即传输，数据大。这一块感觉应该去看RDMA的论文
设计了带有负载和不带有负载的WRITE_WITH_IMM的通知通道，对于纯通知通信，仅将请求标识符嵌入到头部作为即时值，而不携带任何负载，这样更高效。如果需要携带负载，数据通道和通知通道就会合并在一起。对于所有通信通道，使用RC可靠连接传输类型，因为要求可靠的传输和严格的消息顺序。不用READ是因为它比WRITE差，我觉得真的需要学一下RDMA里面的verb
在GAM中，像request、forward、invalidate这种，是通过control channel传送的(SEND/RECEIVE)。像reply、writeback这种，是通过data和notification channel的结合传送的(WRITE_WITH_IMM with payload)。像ack、transfer这种，是通过notification channel传送的(WRITE_WITH_IMM without payload)。错误回复是用的control channel，因为请求方需要具体的错误描述，超出了notification channel的能力范围
利用RDMA的一些性能，来对GAM做优化
因为RDMA NIC的缓存大小优先，所以保持其所需数据量尽可能小很重要。这些数据包括页表、队列对和接收队列。1.通过将暴漏给远程访问的内存组织为大页，可以减少页表项的数量，进而减少TLB缺失；2.一个结点的线程共享队列对，从n方t方减少到n方，并且这样的减少不会影响吞吐量；3.一个结点只是用一个接收队列，由所有相关的队列对共享。
使用selective signaling，每r个请求才发出一次RDMA动词信号，可以将完成通知和清理例程的数量减少r倍。使用RDMA inline，通过PIO直接发送校服在，消除通过PCIe的额外DMA往返。
将多个小包合并成大包，以此利用请求之间的共享特性，同时保持严格的包顺序。为了避免发送重复的请求，可以将针对同一缓存行的所有请求添加到一个pending list，按照它们发出的顺序逐一处理。
内存一致性模型有强一致性模型的strict、sequential，也有宽松的一致性模型的tso、pso、release。内存访问主要是read和write，所以访问顺序有四种rar、raw、war、waw。
内存一致性模型越强，内存访问就更容易理解，编程复杂性和调试难度就更低。使用强一致性模型，可以最大限度减轻用户在统一内存模型下的编程负担，但是这需要对于读取和写入操作都进行同步操作。对于RDMA，会产生不可接受的远程内存访问延迟。故而，放松了RAW，允许异步写入并将其从程序执行的关键路径中移除。即，写入操作可以异步执行，不阻塞后面的读取操作，写入操作不需要等待前一个写入操作完成，从而减少了关键路径上的延迟。
放松WAW，即不采用TSO，允许写入请求在之前的写入请求完成之前变得可见。如果是TSO，会影响写请求合并的机会，带来更大的网络开销。负载的节点，会阻塞后续的写入请求，影响整个系统的性能。
放松waw和raw，会导致内存一致性的放松。但是这对编程复杂性和程序正确性影响比较小。大多数程序员都熟悉异步写入的编程模型，并且大多数程序的正确性并不依赖于写操作的顺序。但是如果放松其他两个，那就麻烦了。
GAM采用的是PSO，即同步读取和异步写入的编程模式。GAM使用了一个worker thread来处理所有来自线程的请求。application thread发出读请求后会被阻塞，直到worker thread将请求的数据读取到指定的缓冲区；发出写请求后会立即返回，不等待写操作完成。顺序一致性可以通过同步机制实现，在写操作后插入内存屏障，确保操作的顺序性；使用锁原语来实现应用级别的串行化，确保多个操作之间的正确顺序。
GAM提供内存屏障、分布式锁、原子操作，来实现内存访问的顺序性和一致性。
锁操作给程序员提供了一种自然的同步机制来协调在共享内存环境下的数据访问。在GAM中，锁和数据是耦合的，在一个cache line中的数据，共享一个锁。锁操作会预取cache line到本地cache，并且让请求节点变成sharing或者owner，这取决于是WLOCK还是RLOCK，这个操作让后续的读写或者解锁该缓存行的操作不用再进行网络通信。锁操作可以像读写操作一样，被缓存。
没有采用通过RDMA之间的request来实现阻塞锁操作，而是用了队列化的锁机制和合理的失败处理策略。当锁被unlock之后，会从队列头部选一个lock来获取锁。trylock不会进入队列，它获取失败后，会直接返回。为了维持一致性状态，还需要再发生锁失败时，进行回滚操作，因为获取锁的过程可能包括多个节点，有可能因为只有一个节点不同意，而其他节点同一，这时需要回滚。
因为锁和数据的粒度一样，都是cache line，这可能会因为锁的竞争而阻塞；另外，会出现死锁现象，比如node1持有a锁，想要获取b锁，而node2持有b锁，想要获取a锁。所以推荐使用trylock
GAM有DLOG和OLOG两种日志。前者用于记录数据写操作，在请求节点将数据写入内存或缓存之前调用，当请求节点获取独占锁时，也会调用DLOG来记录与锁获取一起预取的缓存行；后者用于记录所有权转移，在主节点每次进行所有权转移前调用。不记录读操作。每个log entry都有一个counter，在每次所有权转移时递增。NVRAM存放日志，日志满时，移到SSD或者hard disk。
在故障恢复方面，假设每次数据写操作都会覆盖整个缓存行，因此每个DLOG条目也记录整个缓存行的内容，下面分单节点故障和多节点故障来讨论。
当检测到节点nf故障时，所有未故障的节点会把nf从共享列表删除，确保nf不再是任何缓存行的共享节点，避免了后续操作中误将nf视为有效节点。数据恢复分为两部分，第一部分，恢复nf作为主节点的数据，第二部分，恢复nf作为所有者的脏缓存行。nf从自身日志中恢复第一部分的数据，每个未故障节点会从自身日志中恢复脏缓存行。在数据恢复过程中，所有未故障节点持有的锁不受恢复过程影响。
在第一个阶段，nf从最近的日志条目开始，逐条向前扫描，直到所有未恢复的缓存行都被处理。对于每个DLOG条目e，直接使用e中的数据恢复缓存行c。对于每个OLOG条目e，请求缓存行c的当前所有者节点验证计数器值，如果匹配，则提升该结点为c的所有者，并更新缓存目录，否则记录一个UNDO，使e无效。每个缓存行最多进行两次恢复尝试。
在第二个阶段，对于每个由nf拥有的脏缓存行，未故障节点会请求nf验证其最近一次对该缓存行的写操作是否与当前的计数器值一致。如果匹配，则未故障节点将nf重新提升为该缓存行的所有者；否则未故障节点使用其记录的倒数第二个未完成的日志条目来恢复该缓存行
数据恢复之后，原本共享的缓存行可能变为脏或未共享状态，未故障节点通知nf它们之前共享的缓存行，nf从当前所有者节点读取内容，更改状态为共享，并更新共享列表。
等待所有故障节点重新上线后再并行地进行恢复。每个故障节点恢复其作为主节点的缓存行，从自身和未故障结点的日志中恢复，每个故障节点恢复其作为所有者节点的脏缓存行，从其他节点的日志中恢复。如果第一个阶段有问题，则defer到第二个阶段执行。
使用GAM开发应用程序，事务引擎和分布式哈希表
共享内存模型隐藏了复杂的网络通信细节，每个事务处理节点通过全局索引访问所有表，使用tryrlock和trywlock实现并发控制和数据一致性，在事务准备提交时，数据已被请求节点获取，避免了2PC的开销。
DHT实现为跨多个节点的分布式数组，每个节点负责一部分64位键空间。每个桶包含多个12字节的条目和一个溢出指针，用于处理哈希冲突，键值对存储在全局地址中，索引条目仅包含指向这些键值对的指针，局部重新分配键值对，减少更新操作的成本，通过全局地址指针，自动平衡个节点的负载
实验再20台服务器组成的集群上进行，每台服务器配备了一个四核Intel xeon处理器，操作系统是ubuntu14.04，内核是3.13.0
在8个节点上部署GAM，每个节点贡献空闲内存到全局空间，并使用LRU缓存，每个节点产生三种不同类型的工作负载，设计write/read和rlock/wlock。通过读取比例，远程比例，数据局部性和共享比例四个参数控制访问模式，默认情况下，访问对象随机分布且不重叠
基线系统是Argo和gam-tso，后者是gam的一个变体，通过在每个写操作后附加一个mfence操作来禁用写重排序，从而强制执行tso模型。对于每个系统，每个工作负载参数配置运行四次，第一次用于预热缓存，后三次运行结果取平均值，用于报告。
拿GAM和L-Store、FaRM、Tell做对比
拿GAM和Grappa和Argo比较
通常采用释放一致性模型来摊销网络延迟，通过在同步点使用较大的消息大小来减少网络通信成本，但是其更适合没有数据竞争的应用，因为他们的同步成本太高。
ThreadMarks、Cashmere-2L、Munin使用释放缓存一致性。要求脏数据仅在下一个释放点才变得可见，适合无数据竞争的应用；一些分布式内存组织成本地磁盘的缓存层，以减少慢速磁盘访问；有研究在语言级别提供了全局内存抽象，但增加了语言学习的负担。
基于RDMA也有不少分布式内存管理的研究。DSPM使用RDMA和NVM提供数据持久性；Argo设计了一组基于RDMA和MPI的宽松缓存一致性协议lSinfonia和FaRM使用两阶段提交协议为全局内存操作提供事务支持；GAM不提供事务支持，提供同步原语，使用户可以构建事务应用程序；Grappa设计用于延迟容忍的任务框架和不规则数据密集型应用的共享内存抽象，没有采用缓存机制；Tell和NAM提出了RDMA的共享内存架构，将查询处理和数据存储解耦。
GAM提供统一内存模型、PSO一致性模型、RDMA技术、故障恢复机制
问题
为啥sharing-nothing比sharing-memory容错性好，后者如果单个节点故障，会发生什么？
为啥RDMA的吞吐量可以，延迟缺不怎么行？
啥是基于窥探的协议，snoop-based cache coherence protocol