Faster笔记

Epoch

epoch框架

Faster是基于一个关键的设计原则，旨在实现可伸缩性：避免在线程和公共的访问路径之间的昂贵协调开销。更快的线程在大多数情况下独立执行操作，不需要同步。与此同时，他们需要就共享系统整天同步的通用机制达成一致。为了实现这个目标我们扩展了多线程访问 epoch安全到一个框架中在任意全局操作上启用异步延迟。

Epoch basics是Faster用于协调多线程并发访问的轻量级同步机制。以下是核心组件

线程记作$T$

• 全局当前epoch（E）一个原子计数器，由系统维护，记为当前的epoch。
• 线程本地epoch$E_T$：每个线程维护自己本地版本的E，线程会定期刷新本地的E。
• 安全epoch$E_s$：全局变量，表示所有线程以观察到的最小epoch值。即本地所有线程的epoch大于$E_s$时，$E_s$才会更新为那个新值。

所有线程本地的$E_T$被存储在epoch table中每个线程占用一个缓存行（应该是为了防止缓存行伪共享）。对于任意的epoch $c$如果所有的线程本地的epoch都大于$c$，那么这个c就是安全的。

系统保持对于任意的$T$, $E_s<E_T \leq E$

Trigger action

当把当前的线程从$c$增加到$c+1$,线程可以额外关联一个操作这个操作在将来系统epoch$c$为安全时进行触发。这是通过drain-list实现的，一个<epoch,action>pairs的列表，其中的action是回调代码。这通过使用小的数组来实现的，每当$E_s$更新时，该数组会被扫描以寻找触发的动作。我们在数组上使用原子的比较并交换来确保每个操作只被执行一次。

使用epoch框架

我们使用四个操作来暴露epoch保护框架，它可以被任意线程调用。

• Acquire：为$T$保留一个条目并且设置$E_T$为$E$。
• Refresh：更新$E_T$为$E$, $E_s$更新为当前最大的安全epoch并且触发在drain-list中就绪的操作。
• BumpEpoch(Action)：将计数器E从当前值c增加到c+1，并且添加到drain-list当中。
• Release：从epoch table中删除T。

具有延迟触发动作的epoch可用于简化并行系统中的延迟同步。考虑一个典型案例，当共享变量状态更新为active时，必须调用active-now函数。线程将自动的将状态更新为active，并以active-now作为触发动作来触发epoch。并不是所有线程都会立即观察到状态的变化。然而他们都保证在刷新它们的epoch的时候观察到它，（由于使用内存屏障的顺序内存一致性）因此active-now只有在所有线程看到状态为活动状态后才会被调用，因此是安全的。

我们使用epoch框架在faster中协调系统操作，比如内存安全的垃圾收集，索引改变，循环缓冲维护和页刷新，共享日志页边界维护和检查点。同时在短时间内为用户操作（如读取和更新提供更快的线程不收锁限制地访问共享内存位置）。

Faster线程的生命周期

我们使用faster实现了一个计数器存储（counter store），其中一组faster用户线程会传递与传入请求关联的计数器。线程首先调用Acquire向epoch机制注册自身，随后发起一系列的用户操作，并定期调用Refresh（例如没256次操作调用一次）以将线程移至当前epoch，同时调用completePending（例如没64K操作调用一次）来处理所有先前待处理操作。最后线程调用release来注销Faster的调用。

Faster的哈希索引

Faster的关键构建块是哈希索引，一个并发的无延迟可扩展以及可变的基于哈希的索引。为了便于说明，我们假设一个64位的机器，有64个字节的缓存行。在大的架构中我们期望有更大的原子操作，从而允许我们的设计可扩展。在4,5,6章中，我们把这个索引与不同的分配器配对，以创建功能不断增强的键值对存储。

3.1 索引组织

faster索引是一个缓存对其的$2^k$大小的哈希桶，其中每个桶的大小和缓存行对其（图2）。因此，一个64字节的同由7个8字节的哈希桶项和一个8字节的条目。每个溢出的桶（每个桶包含7个条目+1个溢出指针）也具有缓存行的大小和对其方式，并使用内存分配器按需分配。

选择8字节的条目是关键的，因为它允许我们使用64位原子比较并交换操作对条目进行无锁操作。在64位机器上，物理地址通常占用不到64位，例如因特尔机器通常使用48位指针。因此我们可以偷窃这些额外的比特来进行索引操作（Faster至少需要一个bit）。在本文的其余部分中，我们使用48位指针，但请注意，我们可以支持63位长度的指针。

每个哈希桶（图2）包含了三个部分：tag（15bit），tentative bit和地址。0值的条目代表着空槽位。在一个有$2^k$个哈希桶的索引中，tag用来将索引的有效散列分辨率从k位增加到k+15位。这通过减少哈希碰撞来提升性能。对于哈希值位h的键，其对应的哈希桶先通过h的前k位（成为h的偏移量，offset）来定位。h后面的15位被称为h的标签（tag）。标签只用于增加哈希分辨率，根据地址的大小，标签可能更小，或者完全被删除。试探性钻头是插入所必需的，稍后将介绍

3.2索引操作

Faster的索引是基于不变的每个(offset,tag) 有唯一的索引项，该索引项指向一组记录，这些记录的散列指向相同的偏移量和标签。在支持并发无锁读取、插入和删除索引条目的同时，确保这种不变性是一种挑战。

这里的k取决于哈希表的大小。文中都是在说如何解决一个哈希桶中7个条目遇到冲突的情况。可以简单的理解为，为了缓存行对其，一个链表中存放了7个条目，图中的next Bucket address就是指向下一个的指针。其中每个条目都是一个链表。

这里的tag可以将哈希分辨率提升到k+15位，15就是tag的固定大小。比如在查找时如果一个桶中有许多元素，可以先比较tag，来排除一部分，而不需要直接比较俩个key本身（如string的比较代价是高昂的）。

查找和删除一个条目。定位一个条目对应的key是直接的：我们使用k哈希bit，扫描存储桶以找到标记的条目。从索引条目中删除条目也很容易：我们使用比较交换将匹配项（如果有的话）替换为0。

插入一个条目：考虑一个例子，当一个tag没有存在于bucket中，并且必须插入一个新条目。一个简单的方法是查找空条目并使用比较并交换插入标记。但是俩个线程可以并发地在bucket中的俩个不同的空槽中插入相同的标记，从而破坏我们的不变量。作为一种变通，考虑一个解决方案，每个线程从左到右扫描bucket，并确定地选择一个空条目作为目标。他们将使用比较并交换来竞争插入，并且只有一个会成功。

这里给的例子意思是一个哈希桶中出现了一模一样的重复的key

即使是这种方法在存在删除操作时也会违反不变性条件，如图3a所示。一个线程$T_1$从左到右扫描桶，并且选择槽5来插入tag$g_5$。另一个线程$T_2$从相同桶中的slot3中删除$g_3$，然后尝试插入具有相同tag的$g_5$.从左到右扫描将会导致线程$T_2$为这个tag选择第一个空的条目3。可以证明，对于任何独立选择槽并直接插入的算法都存在这个问题：要了解原因，请注意，就在线程$T_1$执行比较并交换之前，它可能会被交换出去，数据库状态可能会任意更改，包括具有相同tag的另一个槽。

简单来说就是插入之后重新跑一遍检查看看有没有值被修改过，如果被修改过了。说明发生竞争了，需要重新执行。但是一个桶内发生竞争的概率很小。

因此，锁定桶是一个必要（但是沉重）的解决方案。Faster使用latch-free俩阶段插入算法这使用了tentative bit条目。一个线程找到一个空槽并插入了含有tentative bit 记录。然后我们重新扫描桶（注意，它已经存在于我们的缓存中）来检查是否另一个tentative条目在同一个tag中。如果是回退进行重试。否则我们重置暂定位以完成插入。因为每个线程都遵循这个俩阶段提交方法，因此每个线程都保证稳定的不变性。图3b展示了俩个线程的操作顺序：不存在任何并发交错（interleaving）会导致重复的非暂定（non-tentative）tag。

3.3 扩容和索引检查点

对于键数可能随时变化很大的应用程序，我们支持动态调整索引大小。我们利用epoch保护盒阶段状态机降低开销执行大小。有趣的是，即使存在并发操作，使用无锁存操作也总是将索引保持在一致状态。这允许我们在不获得读锁的情况下执行索引的异步模糊检查点，从而大大简化了恢复。

内存键值对存储

我们现在构建了完整的内存键值对存储使用上述的hash index，搭配在内存中的入jemalloc分配器。具有相同(offset,tag)的记录被组织为反向单链表。哈希桶入口指向链表尾部（最近的一条记录）尾部指向前一条记录，以此类推。每个记录可以是固定大小或可变大小，由64位记录头、键和值组成。记录头如图2所示。除了前面的指针之外，我们还使用一些位（invalid和tombstone）来跟踪日志结构分配器所需的信息（参见第5节和第6节）。这些位作为地址字的一部分存储，但如果需要，也可以单独存储。

内存分配中的操作

fetch-and-add是什么？

fetch-and-add 是一种原子操作（atomic operation），用于在多线程环境下安全地修改共享变量的值。它的核心特点是原子性（不可分割），即在执行过程中不会被其他线程中断，从而避免竞态条件（race condition）。

在faster中，用户在epoch保护的安全下线程读取和修改记录值，使用用户的读取或更新逻辑处理记录级并发。例如可以对计数器级别使用fetch-and-add，采用记录级别的锁，或者利用用户级别的分区只是来进行无锁更新。下面描述对于存储的操作。

读取，我们从3.2节中描述的索引中找到匹配的标记条目，然后遍历该条目的链表以找到具有匹配键的记录。

更新和插入。盲更新（upsert）和rmw更新都是从查找键的哈希桶条目开始的。如果条目不存在，我们使用3.2中描述的俩阶段算法来插入标记和新纪录的地址到散列桶的空槽之中。如果条目已存在，我们扫描链表来找到一个匹配键的记录。如果存在这样的记录，我们就地执行操作。线程保证访问记录的内存位置，只要它不刷新它的epoch。此属性允许线程在不担心线程安全的情况下就地更新值。如果这样的记录不存在，我们使用比较-交换将新记录拼接到列表的尾部。在我们的计数存储示例中，我们增加现有键的计数器值，使用fetch-and-increment或普通的in-place increment（如果key是分割的）。插入新键的初始值设置为0

删除操作。我们通过原子性地将记录从链表中移除来实现删除，具体方式是对记录头或哈希桶条目（针对首条记录）执行比较并交换操作。当从单例链表中删除记录时，该条目会被置为0，从而允许后续插入操作重新使用该位置。由于同一内存地址可能存在并发更新，被删除的记录无法立即归还给内存分配器。为此我们采用基于epoch的保护机制：每个线程维护一个线程本地（避免并发瓶颈）的(epoch, 地址)配对空闲列表。当相关epoch进入安全状态后，即可将这些内存安全地归还给分配器。