源码级剖析高性能块存储引擎Buildbarn

背景

作为Bazel Remote Execution生态的一员，Buildbarn在性能上的表现一直很优秀。和其他存储引擎相比，buildbarn的storage组件拥有数量级的优势。尤其在处理大量小文件方面，甚至比BazelRemote快几十倍。

如此夸张的性能差距是怎么做到的呢？本文将从设计和源码的角度，揭秘Buildbarn Storage的内部实现。

实现目标

Google在Remote Execution协议中，规定的存储引擎的能力，协议中称之为可寻址存储(Content Addressable Storage)，简称CAS。

CAS需提供批量查询，批量读写和流式读写三大能力。 每一份存储的内容，都通过唯一的摘要(SHA-256)来索引。

存储引擎需要提供LRU(LeastRecentlyUsed)或类LRU的能力。

考虑到实际的应用场景，该协议对存储引擎有如下的要求：

• 确定的key，返回确定的value
• 快速判断一组key是否存在
• 支持存储大量小文件，也支持存储大文件，并保持高性能
• 存储空间不足时，自动淘汰不常用的key

市面上有不少引擎具备KV()存储能力，例如redis，s3等等，但都很难覆盖Remote Execution的全部要求。接下来，我们简单做一个分析。

现有引擎的缺陷

Buildbarn的设计文档里有一个更全面的汇总。本文只摘录其中一小部分。

• Redis
  • 优点
    • 支持LRU
    • 除了基本的Get，Put方法，协议中的FindMissing方法也可以很好的实现 | - 海量存储空间，基于时间的过期策略
    • 成本低
  • 缺点
    • 单线程设计，valud size过大的时候，可能造成阻塞，影响整体性能
    • 单条记录有512MB的存储上限（致命的）
• 对象存储
  • 优点
    • 海量存储空间，基于时间的过期策略
    • 成本低
  • 缺点
    • 性能差
    • 对FIndMissing的支持较差
    • 不支持LRU

由于现有引擎不能很好满足Remote Execution协议的要求，协议的生态圈均选择了自研存储引擎，例如BazelRemote，Buildfarm，Buildbarn以及我们自研的Coral。

这几种引擎中，Buildbarn性能最为优异，其设计也非常的有趣，接下来让我们进入正题...

设计理念

Buildbarn Storage 在应用层实现了一套，基于“块存储”思想的高速存储引擎。为了更好的理解，本文将按照自顶向下的顺序，对其进行剖析。

块存储

首先我们看一下传统的基于文件系统的存储是怎么做的。

基于文件系统的存储

大部分CAS系统都基于文件系统，将每一个blob，以基于内容的hash值，存储在文件系统上。为了高效寻址，通常采用拆分多级目录的手段来优化，例如：

.
├── aa [dir]
│   ├── aa [dir]
│   │   └── aaaa08f...64da8fd [file]
│   ├── ...
│   └── ff [dir]
├── ...
└── ff [dir]

这样的好处是实现简单，而且用多少空间占多少空间，不会浪费。

块存储的基本模型

块存储则是事先划分好一块独占区域，所有读写均为对这块区域的操作， 需要为此开发一套寻址算法。块存储的示意图如下：

和标准文件系统不同，通过块存储，无法指定往某个path，例如Foo/Bar/1.txt写入文件。只能往Block的某个偏移地址写入若干字节，用接口表示类似这样：

writeAt(offset int64, size int64)

循环存储可行吗

一个很简单的实现方式是循环存储模型。它的实现如下：

首先，用一个指针表示当前写到block的哪个位置。为了便于表述，我们假设某一时刻刚好写到block尾部，把空间用完。再写下一个blob的时候，就循环利用block头部的空间，把位于头部的key自然淘汰掉，如下图所示：

绿色的blob为新加入的，它将直接写到block的头部，同时，A，B两个blob的内容将被破坏，队尾指针也跟着向后移动。

这种方式粗看可以解决问题，但它也存在一个缺陷：当读写动作同时发生的时候，写操作可能会破坏正在读的请求。例如绿色的blob写入时，如果B正在被另一个线程读，数据就可能发生损坏。

另一个值得关注的问题是Tidal Waves，顺序写入的key，可能在某个时间点同时被淘汰，造成大量缓存失效。（这是buildbarn提出来的，tidal waves是否能造成危害，这一点我比较存疑。）

为了更好的管理Block的空间，支持安全快速读写，并避免Tidal Waves，Buildbarn团队设计了一套分代管理模型。

分代管理模型

OldCurrentNew 模型

Buildbarn 提出了OldCurrentNew模型，将Block区域进一步拆分更小的Block，如下图所示：

这些Block是等大小的，每个key必须完整的落在某个Block内，不允许跨越Block。通过抽象出一层子Block，该模型实现了更快速的清理方式，即对整个Block进行删除。

它的淘汰机制是这样实现的：当最后一个New Block写满的时候，把最老的New Block变成Current Block，把最老的Current Block变成Old Block， 把最老的Old Block淘汰掉，而这块空间后续又变成新的New Block，用于新元素写入， 如下图所示：

看起来，很像是集体循环右移。

LRU机制

Buildbarn实现了近似的LRU机制。标准LRU规定，当任何一个blob被访问后，它将成为最后被淘汰的元素，用代码表达通常是移动到队尾。

标准LRU通常使用链表实现，当一个元素被访问后，该元素从链表的原始位置脱钩，并移动到尾部，如下图所示：

链表比较适合不连续空间的读写。但是对于块存储来说，所有元素是按顺序写入到某个块设备（或者大文件）中的。元素的移动会造成碎片，而碎片空间的重新利用，会变得非常麻烦，如下图所示：

当A和B被挪动到最后，原空间再分配blob，很难保证大小匹配，且管理困难。

针对这种情况，Buildbarn给出的解法是空间换时间。当元素被访问时，直接在尾部Block中写入，并更新该元素的索引信息，这样旧的位置自然就不可用的。而那部分空间，也会随着Block的移动而自然淘汰掉。

为了避免这种方法造成过多的空间浪费，该模型还规定，只有当Blob位于Old区域的时候，才触发LRU逻辑，如果Blob位于New或Current区域，说明它暂时还比较安全，也就无需挪动Blob的位置。

通过调整参数，可以实现时间与空间的最佳tradeoff模式。

新Blob空间分配

分析完Block的管理之后，让我们看一看元素是如何存入Block的。

当接收到一个新的Write请求时，首先需要找到一个位置进行存储。Buildbarn在处理blob写入时，并没有严格按照Block的顺序写，而是会在所有的New Block中挑选一个写入。这是为了避免Tidal Waves现象。

挑选Block的方式也是不均匀的，简单来说，靠前的Block会写入更多的Blob，如下图所示：

示意图中简单的模拟了4:2:1的写入比例，但实际实现的时候，其比例控制更加复杂，具体的做法我们在源码分析中再做详细介绍。

索引

介绍完写入操作后，接下来我们分析key的索引机制。CAS的索引，简单来说就是通过指定的Hash，返回文件内容。基于文件系统的CAS引擎，可以直接把Hash当作文件路径，而块存储实现起来比较复杂，因为它没有“文件路径”这样的说法。

通常，blob在块存储中的坐标为， offset表示blob的起始位置相对于block的偏移量， size表示blob占据的字节数。而在OldCurrentNew模型下，block又被区分为小块，因此坐标也变成了三元组：

，其中index表示所属的小block在整体的大block中的坐标。这种三元组坐标在代表中被称为Location。

关于Key和Location的映射，Buildbarn并没有选择简单的Hashmap，而是自己实现了类hashmap机制，关于这套机制，在后面的源码分析中，会进行介绍。

以上就是Buildbarn的空间管理模型了，接下来，我们往下再探一层，看看这套块存储机制是如何和文件系统打交道的。

读写操作

前文提到的把blob存储在某个Block的某个偏移地址(offset)，仅仅是逻辑上的概念。真实的数据总是要落盘的，那么buildbarn是如何处理落盘操作的呢。

根据操作系统不同，buildbarn支持两种模式的存储：

读操作运用了mmap技术， 写操作调用的是原生的pwrite。关于mmap，可以参考这篇博客：

简单说，就是操作系统为了提高读写效率，提出一个页缓存的概念，页缓存在内核空间。当用户需要访问磁盘的某一块数据时，需要先把数据拷贝到页缓存，再从页缓存拷贝到用户态的主内存中。 而mmap通过一层额外的映射，绕过了页缓存，这样可以做到一次拷贝就从磁盘把数据读到用户主存。

持久化

接下来咱们聊一下持久化。由于块存储的独特设计，索引信息的持久化非常重要。设想一下，基于文件系统目录的方式，哪怕进程重启了，依然可以通过“路径约定”，找到对应的blob。但块存储模式，一旦丢失了坐标映射，就像无头苍蝇一样，所有的blob都丢失了，这显然是不可接受的。

需要关注的数据主要包含三部分：

blob本体和blob坐标均直接调用pwrite的方式，写入内核缓冲区，可以确保应用程序的重启不会导致数据丢失。但一旦机器断电，这部分数据是不会真正落盘的。

因此，针对blockDevice，还会定期调用Fsync方法，让数据真正落盘，这个调用周期是可配的，和block meta信息共用一个同步周期。

block的meta信息主要记录了block本身的状态信息，这部分数据的更新频率较低（只在block本身发生变化时），因此它的同步是定期进行的。

校验和缓存加速

最后聊一下校验。

Remote Execution协议规定了服务端需要对上传的内容进行校验：

If the client completes the upload but the [Digest][build.bazel.remote.execution.v2.Digest] does not match, an INVALID_ARGUMENT error will be returned. In either case, the client should not attempt to retry the upload.

Buildbarn在此基础上，对Read请求也加上了校验，确保客户端下载的blob是严格正确的。具体的做法就是增加一层缓存，当某个key近期被下载过，我们就认为它在一段时间内都是合法的。缓存的size和缓存失效的时间均是可以配置的。

以上内容基本涵盖了Buildbarn Storage的核心设计。接下来，我们从源码层面欣赏一些具体的实现方式，以便于更加深入的掌握和分析。

源码分析

在正式进入源码分析环节之前，先说几句题外话。

Buildbarn Storage的代码量并不是很大，总计227个go文件，而local storage的核心文件仅有33个。但它却是我看过的代码中，烧脑程度遥遥领先的。

为什么如此烧脑，我认为主要原因是它对细节的把控非常到位。与业务代码不同的是，越靠近底层的代码，性能要求越极致。如果一定要在可读性和性能方面做取舍的话，那么无疑是性能优先！

好了，废话说完了，让我们一起欣赏buildbarn的一些精巧设计吧。

数据结构

在介绍细节之前，先通过一些基本数据结构，来了解代码大致的框架。和介绍设计理念不同的是，这里采用自底向上的方式，以便于更好的理解数据结构是如何组织的。

核心数据结构分为三大类，分别是Device族，Block族和Location族。如果从Blob写入的视角来看，这三类数据结构所处的位置Location > Block > Device。

Blob读写的操作，大致是如下的流程：

• 读

  • 通过hashkey得到上次存储的坐标(Location)
  • 根据坐标，调用Block的读方法，返回一个getter对象
  • 由上层控制调用getter方法，访问真实Device拿到数据。

• 写

  • 调用Block的写方法，写入数据，返回一个writter对象
  • 调用writter方法，访问真实Device写入数据，返回一个坐标（Locatoin）
  • 记录hashkey和Location的映射，以便下一次查询。

先看类结构大图：

接下来，让我们查看这几类数据结构的核心成员。

Device族

Device族主要用于和底层设备或文件打交道，逻辑相对比较简单。

• BlockDevice

type BlockDevice interface {
   io.ReaderAt
   io.WriterAt
   Sync() error
}

块设备，对块存储底层的抽象，提供ReadAt，WriteAt和Sync三个接口。它的实现类只有一个memoryMappedBlockDevice，它实现了和文件系统或块设备底层的交互。

Block族

Block是存储引擎最核心的概念，该族的接口用于定义基于Block的增删改查以及Block本身的数量和位置控制。

• Block

type Block interface {
   Get(digest digest.Digest, offsetBytes, sizeBytes int64, dataIntegrityCallback buffer.DataIntegrityCallback) buffer.Buffer
   
   Put(offsetBytes int64, b buffer.Buffer) error
   Release()
}

Block是存储模型的核心概念，它的接口也比较简单，只有Get， Put和 Release， 其中Get请求可以带上一个Callback函数，用于处理获取的blob不正确的善后工作。

Block的实现类包括inMemoryBlock 和blockDeviceBackedBlock，后者是我们主要关心的。它包含了BlockDevice对象，用于和底层交互。

• BlockList

type BlockList interface {
   BlockReferenceResolver
   // 删除最老的Block
   PopFront()
   // 尾部追加一个Block
   PushBack() error
   // 从指定坐标的Block获取数据
   Get(blockIndex int, digest digest.Digest, offsetBytes, sizeBytes int64, dataIntegrityCallback buffer.DataIntegrityCallback) buffer.Buffer
   // 查询指定坐标的Block是否有空间
   HasSpace(blockIndex int, sizeBytes int64) bool
   // 向指定坐标的Block写入数据
   Put(blockIndex int, sizeBytes int64) BlockListPutWriter

BlockList用于管理一组Block，通过该接口，可以读，写，查询指定坐标Block上的blob。同时，它也提供了Pop和Push的接口，用于淘汰和创建新的Block。

BlockList的实现类包括volatileBlockList和PersistentBlockList，同样的，后者是我们重点关心的。具体的实现我们后面再分析。

• BlockAllocator

type BlockAllocator interface {
   // 创建新的Block，返回Block本身和BlockLocation坐标
   NewBlock() (Block, *pb.BlockLocation, error)

   // 在指定的Location创建Block对象
   NewBlockAtLocation(location *pb.BlockLocation) (Block, bool)
}

Block分配器，通常作为BlockList的成员，用于为BlockList创建新的Block。实现类为inMemoryBlockAllocator和blockDeviceBackedBlockAllocator

• BlockReferenceResolver

type BlockReferenceResolver interface {
   BlockReferenceToBlockIndex(blockReference BlockReference) (int, uint64, bool)

   BlockIndexToBlockReference(blockIndex int) (BlockReference, uint64)
}

这个数据结构主要用于处理Block坐标漂移的问题，写入某个blob的时候，会记录所属block的坐标，但这个坐标可能是会改变的。 为了防止坐标改变造成索引失败，这里引入了一个新的概念BlockReference。这里不展开具体实现，我们后面再说。

• LocationBlobMap

type LocationBlobMap interface {

   Get(location Location) (LocationBlobGetter, bool)

   Put(sizeBytes int64) (LocationBlobPutWriter, error)
}

这是Block族的入口层接口，提供了Put和Get的抽象。它的实现类是OldCurrentNewLocationBlobMap，实现类需要管理好每一个元素的Put和Get动作，并及时对BlockList的状态进行调整。

Location族

Location族是Storage的另一个核心。它主要用于Key和Location的转换，而Location是Block读写的唯一位置标识。

• Location

type Location struct {
   BlockIndex  int
   OffsetBytes int64
   SizeBytes   int64
}

用于表示一个blob的精确坐标，包括Block的下标，blob在Block中的offset，以及blob的size

• LocationRecord

type LocationRecord struct {
   RecordKey LocationRecordKey
   Location  Location
}

type LocationRecordKey struct {
   Key     Key
   Attempt uint32
}

type Key [sha256.Size]byte

一对的组合对象。

• LocationRecordArray

type LocationRecordArray interface {
   Get(index int) (LocationRecord, error)
   Put(index int, locationRecord LocationRecord) error
}

一个抽象的容器，提供了标准的Get和Put方法，可以快速检索某个blob的LocationRecord记录。实现类为blockDeviceBackedLocationRecordArray，也就是说LocationRecord将会被写入到blockDevice中。

顶层结构

• locationBasedKeyBlobMap

type locationBasedKeyBlobMap struct {
   keyLocationMap  KeyLocationMap
   locationBlobMap LocationBlobMap
}

该结构包含两个重要接口：KeyLocationMap和LocationBlobMap, 从字面意思也能看出，Stoage的核心设计就是处理好Key 到 Location 到 Blob存储之间的映射。

实现逻辑&算法

底层存储

BlockDevice接口抽象了对底层存储的读写操作，具体逻辑在实现类memoryMappedBlockDevice 中。Buildbarn支持两种方式创建BlockDevice, 分别是基于块设备和基于文件。如果部署在Darwin或Windows操作系统，只支持文件的方式。

switch source := configuration.Source.(type) {
case *pb.Configuration_DevicePath:
   return NewBlockDeviceFromDevice(source.DevicePath)
case *pb.Configuration_File:
   return NewBlockDeviceFromFile(source.File.Path, int(source.File.SizeBytes), mayZeroInitialize)

如果选择文件方式，需要提供文件size，当文件不存在的时候，会按照size创建一个大文件，用于存储数据。下面我们以大文件为例，介绍BlockDevice的相关设计。

• 4K对齐

由于Remote Execution的协议要求，存储引擎需要支持大量小文件。在文件系统层面，有一个单文件的最小占用空间，即BlockSize。

这里稍微展开一下扇区和块的区别：

扇区是磁盘物理层面的概念，操作系统不直接和扇区打交道，一个扇区的size通常为512bytes

IO Block是文件系统读写数据的最小单位，也叫磁盘簇。操作系统将相邻的扇区组合在一起，形成一个块，对块进行管理，通常的块大小是4K bytes。块大小是可以在系统层面重新设定的。

创建BlockDevice的时候，设定的最小存储单元也是读取的操作系统的BlkSize，值得注意的是，虽然代码里的命名是sector(扇区)，但并非表示真正的扇区，而代表的是操作系统层面的Block， 这个命名我理解是为了和逻辑层面的Block核心概念区分，代码节选如下：

fd, err := unix.Open(path, flags, 0o666)
unix.Fstat(fd, &stat)
sectorSizeBytes := int(stat.Blksize) 
sectorCount := int64((uint64(minimumSizeBytes) + uint64(stat.Blksize) - 1) / uint64(stat.Blksize))
sizeBytes := int64(sectorSizeBytes) * sectorCount

• mmap的读写实现

上文提到，BlockDevice底层通过mmap技术将进程主内存空间映射到磁盘空间。 mmap的实现比较简单， memoryMappedBlockDevice结构持有一个fd以及data数组：

type memoryMappedBlockDevice struct {
   fd   int
   data []byte
}

data, err := unix.Mmap(fd, 0, sizeBytes, syscall.PROT_READ, syscall.MAP_SHARED)

• 读 & 写

这里读操作，直接用了mmap映射的data数组。但是写操作，依然走的文件系统接口Pwrite。根据注释说明，如果写操作也走mmap，可能会出现PAGE FAULT

func (bd *memoryMappedBlockDevice) ReadAt(p []byte, off int64) {
    copy(p, bd.data[off:])
}

func (bd *memoryMappedBlockDevice) WriteAt(p []byte, off int64) (int, error) {
   return unix.Pwrite(bd.fd, p, off)
}

Block空间分配

了解了底层的Device实现后，我们接着看Buildbarn是如何管理Block的空间分配的。为了避免歧义，我们把存储空间的整体表述为大Block，把大Block中切分出了一堆Block，说成小Block。 如果没有特殊指明，Block默认指小Block。

Block的空间分配管理器，是由blockDeviceBackedBlockAllocator结构实现的。

type blockDeviceBackedBlockAllocator struct {
   blockDevice       blockdevice.BlockDevice
   readBufferFactory blobstore.ReadBufferFactory
   sectorSizeBytes   int        // 存储最小单元的size
   blockSizeBytes    int64      // 单个block的size
   freeOffsets []int64          // 空闲offset数组，记录待分配block的闲置空间的起始地址
}

给freeOffsets设定初始值的逻辑如下：

for i := 0; i < blockCount; i++ {
   pa.freeOffsets = append(pa.freeOffsets, int64(i)*blockSectorCount)
}

当一个Block被分配出去时，就从freeOffsets中删掉这个Block的起始地址：

func (pa *blockDeviceBackedBlockAllocator) NewBlock() (Block, *pb.BlockLocation, error) {
   if len(pa.freeOffsets) == 0 {
      return nil, nil, status.Error(codes.Unavailable, "No unused blocks available")
   }
   offset := pa.freeOffsets[0]
   pa.freeOffsets = pa.freeOffsets[1:]  //Block分配出去后，从freeOffsets中移除
   return pa.newBlockObject(offset), &pb.BlockLocation{
      OffsetBytes: offset * int64(pa.sectorSizeBytes),
      SizeBytes:   pa.blockSizeBytes,
   }, nil
}

相应的，当Block的生命周期结束时，将触发Release动作，此时Block的起始地址会追加进Allocator的freeOffsets列表，表示这块空间可以创建新的Block了。

func (pb *blockDeviceBackedBlock) Release() {
   if c := pb.usecount.Add(-1); c < 0 {
      panic(fmt.Sprintf("Release(): Block has invalid reference count %d", c))
   } else if c == 0 {
      pa := pb.blockAllocator
      pa.lock.Lock()
      pa.freeOffsets = append(pa.freeOffsets, pb.offset)  //Block归还后，该空间可重新分配
      pa.lock.Unlock()
      blockDeviceBackedBlockAllocatorReleases.Inc()
   }
}

以下是图解：

这种做法保证了归还的空间最后被消费。这里起始引出了另一个概念，即SpareBlocks

代码中计算Block数量的时候，出了Old，Current，New，还有一个叫SpareBlocks，但实际创建Block的时候，是按照Old+Current+New来创建的。

这里SpareBlocks并不是真正的Block，它仅仅是为了在freeOffset中占一块空间。 好处就是当空间分配满的时候，如果归还了一个OldBlock，它不会理解被分配为新的NewBlock， 新Block的空间会从SpareBlock预设的空间里取。

Block内部管理

了解了Block的创建和归还后，我们进一步查看Block内部是如何管理blob的读写的。每个Block都对应一个persistentBlockInfo结构，该结构记录了当前已分配的sector。

type persistentBlockInfo struct {
   block         *sharedBlock
   blockLocation *pb.BlockLocation

   allocationOffsetSectors  int64
   writtenOffsetBytes       int64
   synchronizingOffsetBytes int64
   synchronizedOffsetBytes  int64

   epochCount int
}

当一个新的blob被写入时，allocationOffsetSectors被相应的调整，这一段逻辑在PersistentBlockList的Put方法里：

func (bl *PersistentBlockList) Put(index int, sizeBytes int64) BlockListPutWriter {
   // Allocate space from the requested block.
   blockInfo := &bl.blocks[index]
offsetBytes := blockInfo.allocationOffsetSectors * int64(bl.sectorSizeBytes) 
blockInfo.allocationOffsetSectors += bl.toSectors(sizeBytes) 

   block := blockInfo.block
   absoluteBlockIndex := bl.totalBlocksReleased + index
   block.acquire()
   return func(b buffer.Buffer) BlockListPutFinalizer {
      err := block.block.Put(offsetBytes, b) 
        
      // some code ... 
   }
}

判断Block是否写满，也是基于allocationOffsetSectors的：

func (bl *PersistentBlockList) HasSpace(index int, sizeBytes int64) bool {
   blockInfo := &bl.blocks[index]
   return bl.blockSectorCount-blockInfo.allocationOffsetSectors >= bl.toSectors(sizeBytes)
}

Block列表

接下来，我们进一步了解Block列表的管理方式，以及Old，Current，New这些不同类型的Block究竟是如何组织的。

比较常见的想法是维护3个列表，分别为OldBlockList, CurrentBlockList 和NewBlockList。这种做法可读性比较强，但是由于Block经常需要移动分组，按照这种模式，就需要对3个列表频繁加锁，性能上可能产生损耗。

Buildbarn采用了单列表的方式，利用下标计算的小技巧，从逻辑上把BlockList隔成了3段。我们找一个具体的例子看下：

OldCurrentNewLocationBlobMap结构的findBlockWithSpace方法， 用于在block列表中找到可用Block的下标。按照OldCurrentNew模型的设定，应该从New类型的Block中挑选。以下这段代码揭示了寻找可用index的过程。

for {
   if lbm.allocationAttemptsRemaining > 0 {
      index := len(lbm.oldBlocks) + lbm.currentBlocks + lbm.allocationBlockIndex
      if lbm.blockList.HasSpace(index, sizeBytes) {
         lbm.allocationAttemptsRemaining--
         return index, nil
      }
   }
   lbm.startAllocatingFromBlock((lbm.allocationBlockIndex + 1) % lbm.newBlocks)
}

这里在计算index的时候，通过把oldBlock和currentBlock的数量相加，就自动定位到了newBlock的起始地址。之所以用一个简单的表达式就可以找到NewBlock的起始地址，是因为我们的列表始终满足规则：

Block严格按照Old，Current，New的顺序，排列在BlockList中

当我们想把最老的NewBlock变成CurrentBlock，不需要做任何的Block移动， 仅仅把currentNum自增1，把newNum自减1即可。下面这段代码表达的很清楚：

for lbm.totalBlocksReleased  0 {
      lbm.removeOldestOldBlock()
   } else if lbm.currentBlocks > 0 {
      lbm.currentBlocks-- // 减少一个current
   } else {
      lbm.newBlocks-- // 把最老的new变成current
      lbm.startAllocatingFromBlock(0)
   }
}

以下是关于淘汰最老的Old Block和追加新的Block的图解：

左边虚线框里的Old Block，会从blocks列表中删除，并把它在大Block中的起始offset，归还给BlockAllocator, 这样这块空间就可以被分配出来，变成一个新的Block，追加到列表最后了。

中间渐变色的两个Block，表示从箭头起点的名称，变成箭头终点的名称。

值得注意的是，经过这一番操作后，Block的index全部往前挪动了一格。如果我们把index存储为blob的坐标，会出问题。 这里Buildbarn设计了一个BlockReference机制来处理这种偏移。代码实现比较烧脑，我们先往后放一下。

NewBlock选择

按照OldCurrentNew的设计，新元素应该写入New Block，为了避免tidal wive，新元素会挑选其中一个New Block，而不是严格顺序写入。这一段的实现是通过startAllocatingFromBlock方法实现的。

for {
   if lbm.allocationAttemptsRemaining > 0 {
      index := len(lbm.oldBlocks) + lbm.currentBlocks + lbm.allocationBlockIndex
      if lbm.blockList.HasSpace(index, sizeBytes) {
         lbm.allocationAttemptsRemaining--
         return index, nil
      }
   }
   lbm.startAllocatingFromBlock((lbm.allocationBlockIndex + 1) % lbm.newBlocks)
}

从上面的代码也可以看出，index的表达式包含一个lbm.allocationBlockIndex，它的值表示第几个NewBlock。具体逻辑，我们进一步查看startAllocatingFromBlock

func (lbm *OldCurrentNewLocationBlobMap) startAllocatingFromBlock(i int) {
   lbm.allocationBlockIndex = i
   if i >= lbm.newBlocks-lbm.desiredNewBlocksCount {
      // One of the actual "new" blocks.
      lbm.allocationAttemptsRemaining = 1  lastBlockIndex {
      return 0, 0, false
   }
   return lastBlockIndex - blocksFromLast, bl.epochHashSeeds[epochIndex], true
}

坐标映射

上文在介绍BlockReference时提到了EpochID的概念，这个概念其实是为坐标映射服务的。

坐标映射，即每个Digest唯一对应一个BlockReference，虽然可以用hashmap快速的实现，但这种做法在块存储中是不合适的。块存储模式中，这一层映射关系非常重要，一旦丢失，所有数据都不可用了！但hashmap的持久化非常的麻烦，如果每写入一条数据就做一次反序列化成本太高了， 定时存储又可能导致数据丢失的风险。

需要一个数据结构，保证映射关系能实时落盘。于是Buildbarn设计了一个近似的Hash表结构，该算法比较接近Robin Hooking Hashing算法，让我们看看它的具体实现：

考虑到BlockSize定长的特性，存储的key的个数是有上限的，上限等于总size/最小文件的size， 最小文件受操作系统限制，通常为4K。 因此，可以用一个定长的数组来存储所有可能的BlockRef。接下来，只需要一个算法，将key映射到数组的下标中即可。

"Key —> 数组下标" 的映射，通过hash+取模的方式实现，这种方式必然存在hash碰撞，作者采用了一个小技巧，即把重试次数作为hash函数的参数，如果碰撞，就重新计算一次hash，找到下一个合法的坐标，如图所示：

这种做法的查询和写入时间复杂度近似为O(1)，但在数据空间比较满的时候，发生hash碰撞的几率还是挺大的，严重的甚至可能导致死锁。为了规避这种情况，作者引入了最大重试次数的概念，超过重试次数的请求将被丢弃。听起来，这可能造成错误的请求丢弃，但实测下来效果很好，丢掉的请求基本上都是些过期的记录，见下面这段注释：

Because the hash table has a limited size (and does not resize), there is a risk of the hash collision rate becoming too high. In the case of a full hash table, it would even deadlock. To prevent this from happening, there is a fixed upper bound on the number of iterations Get() and Put() are willing to run. Records will be discarded once the upper bound is reached. Though this may sound harmful, there is a very high probability that the entry being discarded is one of the older ones.

为了验证取到的value的合法性，作者还引入了校验机制，先看value的数据格式：

const (
   // BlockDeviceBackedLocationRecordSize is the size of a single
   // serialized LocationRecord in bytes. In serialized form, a
   // LocationRecord contains the following fields:
   //
   // - Epoch ID                     4 bytes
   // - Blocks from last             2 bytes
   // - Key:                        32 bytes
   // - Hash table probing attempt   4 bytes
   // - Blob offset                  8 bytes
   // - Blob length                  8 bytes
   // - Record checksum              8 bytes
   //                        Total: 66 bytes
   BlockDeviceBackedLocationRecordSize = 4 + 2 + sha256.Size + 4 + 8 + 8 + 8
)

这里EpochID和Blocks from last对应的刚好是BlockReference的结构， 而checksum表示校验码。前文提到EpochID但没有解释其用法，我们在这里解释一下：

每一个blob插入，都会生成一个随机种子，用于结果校验。 通过一个函数，计算LocationRecord和hashSeed的值，生成校验码。 下次查询LocationRecord的时候，只要用相同的随机数种子重新计算校验码，就可以验证LocationRecord的合法性， 代码如下：

if computeChecksumForRecord(&record, hashSeed) != binary.LittleEndian.Uint64(record[4+2+sha256.Size+4+8+8:] ) {
   return LocationRecord{}, ErrLocationRecordInvalid
}
 // 红色部分对应的就是checksum校验码

hashSeed存储在blockList的epochHashSeeds字段里，而EpochID只是为了索引epochHashSeeds内部的坐标而存在的。具体做法是：每插入一个新blob，将EpochID写入BlockReference里，需要获取hashSeed的时候，用EpochID减去当前最老的Block的第一个元素的EpochID，就得到了epochHashSeeds的下标了。举个例子：

假设当前最老的Block存储的第一个元素的EpochID为100，待查询的EpochID为125，我们就从105-100=5的坐标位置找到存入Blob的时候生成的hashSeed。

为了防止epochHashSeed的长度无限扩大， 每当最老的Block被淘汰时， OldestEpochID会加上那个Block的epoch数量，同时，epochHashSeeds数组也会淘汰掉相同数量的元素。

关于锁/并发安全

锁往往穿插在诸多细节中，看代码的时候容易忽略。正确运用锁，可以用最低代价换取并发安全，否则轻则影响性能，重则会导致程序崩溃或数据丢失。

下面我们一起来看Buildbarn的锁设计：

第一把锁 外层锁

Buildbarn整体的设计模型是CPU和IO分离的，收到读写请求后，并不是立刻准备IO数据，而是通过Block管理模型，返回一个getter或者setter对象，这个动作由于设计空间分配，是需要整体加锁的。而触发IO操作时，则不需要加锁。

加锁逻辑在flatBlobAccess中，它位于前文提到的locationBasedKeyBlobMap的更外一层。它的职责如下：

处理Get，Put请求，通过调用下层的KeyBlobMap，拿到getter和putter，并进行调用，触发真正的读写操作

读的时候，会收到needRefresh的标识，如果为true，需要再次触发写请求，将该内容写入待存储的位置。

这里，flatBlobAccess采用了读写锁的设计。获取getter的时候加读锁，获取putter的时候加写锁。

值得一提的是，当出现refresh的时候，为了保证数据安全，代码里调用了第二次Get请求，并加上了写锁，如下所示：

{
    ba.lock.RLock() 
    getter, _, needsRefresh, err := ba.keyBlobMap.Get(key)
    if err != nil {
       ba.lock.RUnlock()
       return buffer.NewBufferFromError(err)
    }
    if !needsRefresh {
       b := getter(blobDigest)    // 这里不会阻塞其他线程的读
       ba.lock.RUnlock() 
       return b
    }
    ba.lock.RUnlock() 
    
     // 开始处理Refresh
    ba.lock.Lock()   // 这里换成了写锁，因为其他线程也可能在处理相同的key的refresh
    getter, sizeBytes, needsRefresh, err := ba.keyBlobMap.Get(key)
    if err != nil {
       ba.lock.Unlock()
       return buffer.NewBufferFromError(err)
    }
    b := getter(blobDigest) 
    if !needsRefresh {
        // 在我们取得写锁之前，其他线程已经处理过了
       ba.lock.Unlock() 
       return b
    }
    
    putWriter, err := ba.keyBlobMap.Put(sizeBytes)
    ba.lock.Unlock()   // 释放写锁
}

第二把锁 Block分配锁

空Block的产生和满Block的回收，均通过BlockAllocator来完成。BlockAllocator内部维护了一个列表，记录了每个可分配Block的起始地址，假设每个Block的Size为1024(实际比它大得多)，可分配下标一般会写成这样的形式：

// 可分配地址， 例：
freeOffset = [0, 1024, 2048, 3072, 4096]

当收到创建Block的请求时，第一个offset被分配出去， 数组变为[1024,2048,3072,4096]。当该数组被回收时，下标又追加到数组尾部，例如[1024,2048,3072,4096,0]

这里必须限制BlockAllocator对数组的并发修改，否则可能分配出两个具有相同offset的Block，数据就写乱了。加锁的方式比较常规，就是普通的排他锁：

func (pa *blockDeviceBackedBlockAllocator) NewBlock()  (Block, *pb.BlockLocation, error) {
   pa.lock.Lock() 
   defer pa.lock.Unlock() 

   if len(pa.freeOffsets) == 0 {
      return nil, nil, status.Error(codes.Unavailable, "No unused blocks available")
   }
   offset := pa.freeOffsets[0]
   pa.freeOffsets = pa.freeOffsets[1:]   // 这里修改了freeOffsets
   return pa.newBlockObject(offset), &pb.BlockLocation{
      OffsetBytes: offset * int64(pa.sectorSizeBytes),
      SizeBytes:   pa.blockSizeBytes,
   }, nil
}

func (pb *blockDeviceBackedBlock) Release()  {
   if c := pb.usecount.Add(-1); c < 0 {
      panic(fmt.Sprintf("Release(): Block has invalid reference count %d", c))
   } else if c == 0 {
      pa := pb.blockAllocator
      pa.lock.Lock() 
      pa.freeOffsets = append(pa.freeOffsets, pb.offset)  // 这里修改了freeOffsets
      pa.lock.Unlock() 
      blockDeviceBackedBlockAllocatorReleases.Inc()
   }
}

第三把锁 Block回收锁

当一个Block写满时，它的生命周期也即将结束，在它生命的最后时刻，有几件事情是需要善后的。

第一点主要是防止还有请求未处理完的时候，Block空间就被分配出去了。 第二点主要是防止意外重启，导致重新加载时，BlockState不正确。

让我们看看代码里是如何实现的：

首先看到Block接口的实现类blockDeviceBackedBlock，实际的Get，Put请求最终会作用到这个类上。

type blockDeviceBackedBlock struct {
   usecount       atomic.Int64
   blockAllocator *blockDeviceBackedBlockAllocator
   offset         int64
}

注意，这里有一个引用计数器，计数器初始值为1。 当调用Get请求时，计数器加1，Release则减1：

type Block interface {
    // 计数器加1
   Get(digest digest.Digest, offsetBytes, sizeBytes int64, dataIntegrityCallback buffer.DataIntegrityCallback) buffer.Buffer
   Put(offsetBytes int64, b buffer.Buffer) error
    // 计数器减1
   Release()
}

当计数器减到0的时候，Block占用的空间会真正被回收，这也就意味着，这块空间可以重新分配给新的Block用于读写了。

func (pb *blockDeviceBackedBlock) Release() {
   if c := pb.usecount.Add(-1); c < 0 {
      panic(fmt.Sprintf("Release(): Block has invalid reference count %d", c))
   } else if c == 0 {
      // Block has no remaining consumers. Allow the region in
      // storage to be reused for new data.
      pa := pb.blockAllocator
      pa.lock.Lock()
      pa.freeOffsets = append(pa.freeOffsets, pb.offset) 
      pa.lock.Unlock()
      blockDeviceBackedBlockAllocatorReleases.Inc()
   }
}

那么什么时候计数器会减到0呢？代码里有两处：

一是当读请求结束时，即Reader的Close方法被调用时：

func (r *blockDeviceBackedBlockReader) Close() error {
   r.block.Release() 
   r.block = nil
   blockDeviceBackedBlockAllocatorGetsCompleted.Inc()
   return nil
}

这样设计，每个读请求从生命周期开始到结束，对引用计数器的影响刚好是抵消的。但计数器的初始值为1，所以需要在Block生命周期即将结束时，触发Release来真正释放掉空间。

这里需要引入一个新的概念，叫sharedBlock， 它是blockDeviceBackedBlock的封装类，多了一个refcount对象，作为引用计数器：

type sharedBlock struct {
   block    Block
   refcount uint64
}

sharedBlock提供了acquire和release两个方法，当引用计数器为0时，再去调用真实Block的Release， 整个过程是无锁的。当引用计数为0时，触发真实Block的Release:

func (sb *sharedBlock) release() {
   if sb.refcount == 0 {
      panic("Invalid reference count")
   }
   sb.refcount--
   if sb.refcount == 0 {
      sb.block.Release() 
   }
}

初始状态下，sharedBlock的引用计数为1， 随后每一个Blob的写请求， 都会在返回putWritter前给引用计数加1， 完成IO操作后，再减去1。那么什么时候才减到0，触发释放呢？在Block的持久化信息同步完毕之后，相关的代码如下：

func (bl *PersistentBlockList) NotifyPersistentStateWritten() {
   for i := 0; i < bl.blocksReleasing; i++ {
      bl.blocksToRelease[i].release() 
      bl.blocksToRelease[i] = nil
   }
   bl.blocksToRelease = bl.blocksToRelease[bl.blocksReleasing:]
   bl.blocksReleasing = 0
   if len(bl.blocksToRelease) == 0 {
      bl.blockReleaseWakeup.block()
   }
}

因此，整个Block的释放分为两层。 外层是sharedBlock，内层是blockDeviceBackedBlock，两层都有引用数器，外层针对写请求，内层针对读请求。整体模型如下所示：

- sharedBlock
  - refCount
  - blockDeviceBackedBlock
    - refCount

既然都是引用计数器，为什么不能合并成一个数据结构呢， 读写请求开始的时候加1，完成的时候减1，似乎也能实现功能。

这个问题也困扰了我很久，后来看注释和代码实现才意识到，这可能和是否加锁相关。

回顾一下外层锁的设计， 当时采用的是读写锁， 也就是说读可能并发，但写一定是独占的。既然上层保证了“写独占”，引用计数器就可以完全无锁了，而读操作允许并发，所以refCount一定要设置为atomic类型 ， 这里不得不赞叹一波，Buildbarn的设计者确实非常注重细节！

第四把锁 Block持久化锁

在介绍第三把锁的时候，我们知道一个Block真正被释放掉，取决于BlockList的持久化信息被同步完成。这里就引入了第四把锁——Block持久化的锁机制。

首先，查看NotifyPersistentStateWritten的被调用链路，看到下面一段代码：

func (ps *PeriodicSyncer) writePersistentState() error {
   ps.storeLock.Lock()
   defer ps.storeLock.Unlock()

   ps.sourceLock.RLock()
   oldestEpochID, blocks := ps.source.GetPersistentState()  // 获取persistentState
   ps.sourceLock.RUnlock()

   if err := ps.store.WritePersistentState(&pb.PersistentState{  // 写persistentState
      OldestEpochId:                    oldestEpochID,
      Blocks:                           blocks,
      KeyLocationMapHashInitialization: ps.keyLocationMapHashInitialization,
   }); err != nil {
      return err
   }

   ps.sourceLock.Lock()
   ps.source.NotifyPersistentStateWritten() 
   ps.sourceLock.Unlock()
   return nil
}

当PersistentState被同步完，会调用NotifyPersistentStateWritten将Block释放掉。再往上的调用链比较多，我们从头说起。

首先，有一个常驻routine负责巡检，专门处理BlockRelease的情况：

go func() {
   for {
      periodicSyncer.ProcessBlockRelease()
   }
}()

这个巡检函数，利用channel机制，设计了一套阻塞和唤醒机制， 代码中把它叫做block和unblock：

func (ps *PeriodicSyncer) ProcessBlockRelease() {

   ps.sourceLock.RLock()

   ch := ps.source.GetBlockReleaseWakeup()

   ps.sourceLock.RUnlock()