opencache

Opencache 是一个在单个节点模式下运行的 Rust 缓存服务器，是一个面向对象的存储，提供两个 API：范围 write 和范围 read 以及后台自动淘汰。

缓存集群管理在客户端。不支持回溯，应用程序必须显式将对象写入其中。

协议

• http2 PUT GET
• (可能) aws-s3
• (可能) grpc stream

存储模型

CacheServer 将对象（由唯一的 utf-8 字符串键标识的字节流）存储在块中。属于同一对象的块具有相同的大小。

• 在读取对象时，如果指定的范围与块大小不匹配，则可能返回第一个和最后一个块的部分。

• 在写入对象时，第一个和最后一个未对齐的字节将被丢弃。因为 opencache 以固定大小的块存储对象内容。

  可选地，可以在添加对象时（第一次写入）指定块大小，并且不会更改。

块

Chunk 几乎就是一个字节切片。

块大小可以由应用程序指定（在第一次写入对象时）或由 opencache 服务器决定。默认块大小是

default_chunk_size = max(min(file_size/64, 2M),64K)

块组

不同大小的块存储在不同的块组（ChunkGroup）中，例如。

• (0,4KB]
• (4KB,1MB]
• (1MB,8MB]
• (8MB, +oo]

Opencache 有几个预定义的块组，对象的实际块大小是小于或等于指定大小的最小预定义块大小。

对象

Opencache 中的对象包括对象头和几个块。

头包含 JSON 格式的应用程序元数据和内部元数据。内部元数据包括

• 对象添加的时间，
• 总大小，
• 块大小，
• 存储的块的位图
• 每个存储块的块 ID。

   .------------.
   |   object   |
   '------------'
      |       |
      |       '-------------.
      | header              |
      |                     |
      v                     |
   .-----------------.      |        .----------.
   | json-meta       |      +------->| chunk-1  |
   | size            |      |        '----------'
   | chunk-bitmap    |      |
   | chunk-ids       |      |        .----------.
   '-----------------'      '------->| chunk-2  |
                                     '----------'

Opencache 以 <key, header> 的持久映射存储对象。该映射将在服务器启动时加载到内存中。

数据类型

块组 ID

ChunkGroupId 是文件名中的 2 个 ASCII 字符，或在内存中的 1 个字节。 ChunkGroupId 是其中块大小的编码表示，类似于浮点数的表示。

第一个字符（或 4 个高位）是 power。第二个字符（或 4 个低位）是 significand。

        power          significand
ascii   0              1
bits    4 higher bits  4 lower bits

块大小计算如下：significand * 16^power

例如，48K 块组 ID 为 3c：12 * 16^3 = 48K // c=12;

最大块组 ID 是 ff：15 * 16^15 = 15E

以下列出了一些 ChunkGroupId 的示例

01: 2 * 16^0 = 2        08: 8 * 16^0 = 8
11: 2 * 16^1 = 32       18: 8 * 16^1 = 128
21: 2 * 16^2 = 512      28: 8 * 16^2 = 2K
31: 2 * 16^3 = 8K       38: 8 * 16^3 = 32K
41: 2 * 16^4 = 128K     48: 8 * 16^4 = 512K
51: 2 * 16^5 = 2M       58: 8 * 16^5 = 8M
61: 2 * 16^6 = 32M      68: 8 * 16^6 = 128M
71: 2 * 16^7 = 512M     78: 8 * 16^7 = 2G

块 ID

ChunkId 是一个 u64，其中最高位字节是 ChunkGroupId，其他 7 个字节是 54 位整数中的单增量索引。

       <ChunkGroupId> <index>
byte:  [0]            [1, 7]

键

键是一个任意的 utf-8 字符串。

访问条目

缓存替换算法依赖于访问日志来决定应该淘汰哪个对象/块。

可以是 Key 或 ChunkId，分别用于追踪对象访问或块访问。

存储布局

Opencache 磁盘存储包括

• 描述所有其他磁盘文件的清单文件。
• 键文件用于存储对象键和对象头。
• 块文件用于存储缓存文件数据。

清单文件

清单是当前存储的快照。即，它是一个属于此快照的文件列表。

data_ver: 0.1.0
key_meta_ver: 0.2.0
keys:
  key-wal-1, key-wal-2...
  key-compacted-1, key-compacted-2...
access:
  acc-1, acc-2...
chunk-groups:
  CG-1, CG-2...
chunks:
  chunk-id-1, chunk-id-2...

对象存储

对象存储是一组文件，用于持久化对象映射。它包括一个活动 WAL 文件和几个压缩文件。

对象头包括

• 此记录被添加时的时间戳。
• 一个标志，指示它是添加操作还是删除操作。
• 此对象的总大小。
• JSON 格式的用户元数据。
• 此对象分配的块组（CG）。
• 存储的块的 ChunkId 列表。在此列表中不需要存储块组。因为一个对象中的每个块都属于同一个块组。

块存储

对象内容以块的形式存储。相同大小的块属于同一个块组。

每个块组由 一个 活动块文件（可写）和几个只读块文件组成。活动块文件是追加只读。

删除是通过另一个按块文件实现的，即 ChunkIndex（其中逐个追加块索引条目）。

• 对于活动块，ChunkIndex 只包含已删除的块索引：(chunk_id, REMOVE)；因为块文件和 ChunkIndex 文件在更新时没有进行 fsync。

  重启时，当前块 ID 从块文件中加载，而删除的块 ID 从 ChunkIndex 文件中加载。

• 对于关闭的块，ChunkIndex 包含当前块 ID 和删除的块 ID（一个块在关闭（压缩）后被删除）：(chunk_id, ADD) 或 (chunk_id, REMOVE)。

  当服务器重启时，块索引仅从 ChunkIndex 文件中加载。

      .----------.
      | Manifest |
      '----------'


  Access   Access    Keys             ChunkGroup-i      ChunkGroup-j   ..
  Key      Chunk

  .----.   .----.    Active           Active
  |key1|   |cid1|    .---------.      .----.  Chunk     ..
  |key2|   |cid2|    | k1,meta |      | c1 |  Index
  | .. |   | .. |    | k2,meta |    .-|-c2 |  .----.
  |CKSM|   |CKSM|    | ..      |    | | .. |<-|cid5|
  |key3|   |cid3|    | CKSM    |    | | .. |  |cid6|
  | .. |   | .. |    | k3,meta |    | '----'  | .. |
  '----'   '----'    | ..      |    |   ..    '----'
    ..       ..      '---------'    |
  .----.   .----.      ..           |
  |keyi|   |cid1|                   |
  |keyj|   |cid2|    Compacted Keys | Compacted Chunks
  | .. |   | .. |    .---------.    |
  |CKSM|   |CKSM|    | k1,meta |    | .----.  Chunk
  |keyk|   |cid3|    | k2,meta |    | | c1 |  Index
  | .. |   | .. |    | ..      |    +-|-c2 |  .----.
  '----'   '----'    | CKSM    |    | | .. |<-|cid5|
                     | k3,meta |    | | .. |  |cid6|
                     | ..  |   |    | '----'  | .. |
                     '---------'    |         '----'
                           |        '---.
                           v            v
                     KeyMeta          Chunk
                     .----------.     .----.
                     | ts       |     |data|
                     | add|rm   |     |CHSM|
                     | size     |     '----'
                     | userdata |
                     | CG       |
                     | chunkids |
                     '----------'

trait ChunkStorage {
    fn add(&mut self, chunk_id, bytes);
    fn remove(&mut self, chunk_id);
    fn read(&mut self, chunk_id) -> Stream<>
}

trait ObjectStorage {
    fn add(&mut self, key: String, size, meta, prefered_chunck_size);
    fn remove(&mut self, key)
    fn access(&mut self, key)
}

trait Cache {
    /// Write chunks to an object.
    /// Nonexistent object will added implicitly
    fn write(&mut self, key, chunks)

    /// Read specified `range` of bytes in an object
    fn read(&mut self, key, range)
}