Post

IndexDB

Posted
By Jebearssica 18 min read

IndexDB 简介

indexDB 是一种索引数据库的概念, 它保存了键值 (key) 至元数据 (metadata) 映射的存储结构. 其中元数据可以理解为是原始数据的一些属性, 例如名称/位置等等. 因此可以通过元数据快速定位至文件的具体数据块 (二进制文件的读写加速通常涉及分块处理), 从而避免了对于整个大型二进制文件的扫描, 进一步来说优点有如下几个:

  • 核心诉求: 尽可能降低每次计算对于整个文件的扫描规模
  • 查询多样性: 由于不同计算流程所需涉及的对象规模不同, 为了降低遍历规模, 通过构造不同键值对从而能够访问到所需的对象集合, 避免了在全集合中进行遍历后滤出的过程
  • 常数项时间复杂度: 同样的, 在每次计算中, 由于缩小了规模, 因此可以显著降低常数项的时间复杂度, 在大规模计算中理论时间复杂度与实际的运行时间开销仍存在很大差异
  • 内存限制: 内存无法直接加载所有结构, 因此需要不同索引快速定位至某一小块的局部数据后进行加载
    • 这事实上是持久化索引的原因, 当你能持久化索引也就意味着相同的搜索遍历不再需要大规模加载(不需要加载原始数据且不需要购机按索引映射)
  • 并发与恢复: 并发访问, 增量读写与崩溃恢复要求分离的索引机制(不同的索引有不同的更新/重建成本)

常见的索引类型有以下几种:

  • 偏移索引(offset index): 键值对映射至当前块的偏移量, 在分块处理大型二进制文件中是一个简单常用的方式
  • B树: 由于通常数据规模巨大, 因此使用B树, 相较于传统平衡二叉树而言, B树能够人工限制树深度, 从而大幅减少每次搜索的硬盘 IO 开销
    • 实际原理可以理解为, 在普通的二叉树基础上, 对于一个结点而言可以存储多个有序键值. 因此在访问一个结点时按序比较当前结点的所有键值, 可以找到最终要搜索的目标究竟在哪个区间内, 接着递归访问区间内的子树集合
    • 人工限制树深度指的是调整存储结点中的键值信息, 而非人为控制树结构
    • B树是二叉树的变种, 因此支持区间查询
  • 哈希索引: 顾名思义, 快速单点查询
  • LSM树: 写性能好, 适合批量写或写多读少
  • 布隆过滤器: 快速判断肯定不存在, 从而大幅度减少硬盘查询次数

在 GDSII 读写中的应用

GDSII 格式的特点:

  • 格式结构: 二进制流格式, 由头部(类型+长度)与数据构成；DB 解析时需要按序按规逐条读取
  • 层级与引用: 涉及 cell/instance 概念, 同一 cell 可能在多处被引用；DB 解析时应注意不要重复存储副本, 要记录引用关系
  • 大规模: 超百G的文件常见；DB 解析时应注意不能全部存储至内存, 要支持流式构建或部分构建

根据其特点, 在 DB 中的读写设计可以有以下几点:

  • cell 名称索引: 根据 cell name -> offset + length, 这样能够通过名称直接找到对应二进制文件的头部直接开始读取, 这一部分可以使用哈希从而能够快速定位到一个 cell 的定义
    • 进一步而言, 考虑 hierarchy 结构, 可以使用 B 树存储 cell name 的哈希值, 应该确保这个哈希值能够满足子 cell 的 index 一定在父节点的 index 区间内
  • 空间索引: 事实上 GDSII 是一个存储二维平面物理信息的格式, 通过 R 树或者 quad 树能够实现空间范围内的快速搜索, 键值配对应当是 bbox -> metadata(？metadata 具体有待研究)
  • 基本属性的索引: 实践中经常有按 layer 进行的操作, 因此一个合理的键值配对也应当由 layer -> {一堆 index}, 从而能够实现根据基本属性进行对象的分组
  • 涉及具体 instance 修改的索引: 上述能够对 per cell 的操作进行快速索引, 如果要修改具体某个 instance 而言, 可在此基础上建立一个基于 cellname + relative transform(或 bbox) -> instance 的索引
  • 布隆过滤器: 快速判断键值是否存在

其中, 具体的设计细节应该注意以下几点:

  • 索引与数据分离: 数据太大存硬盘里, 索引可以存内存中
  • 构建索引的策略: 依旧由于数据量太大, 可以通过流式处理(单/多线程)
  • 并发问题: 读多写少就只读内存映射, 写多就分块加锁
  • 内存映射: ？
  • 空间索引持久化: 业务中大量涉及图形间运算, 因此持久化空间索引可以避免每次运算都进行一次索引建立
    • 避免冷启动开销: 持久化索引避免每次计算都需要完全解析巨大的二进制文件
    • 减少磁盘 IO: 避免全文件顺序读或随机查询
    • 并发共享: 多线程共享持久化的索引, 避免每个线程额外进行冷启动
    • 故障恢复: 持久化的索引额外加上校验信息能够在崩溃后快速恢复一致性
    • 增量更新: 持久化数据方便直接在内存上进行增量更新
  • 去重与引用: ？
  • 压缩: 应该考虑大量叶子结点上未被复用的 cell 实例, 这种大量小块的存储如何压缩？
  • 一致性与恢复: optional WAL？
  • 原子更新: ？

持久化注意事项

根据版图数据使用的频繁程度做优先级排序:

  • cell name -> file offset: 通过 cell name 定位具体 cell 的数据块
  • per cell metadata: cell_bbox/cell_layer/cell_reference(instance) 作为键值: 常用属性方便快速过滤
  • per cell bloom filer: 快速检查 cell 是否存在
  • 空间索引: 用于范围查询或相交检查, 可以考虑按所需子树进行持久化(无需全局整树持久化), 即在只需要两颗子树之间进行频繁相交检验时, 考虑检索至其最近公共祖先并以此为根结点持久化当前子树
  • per instance metadata: ？考虑 cell -> instance 的索引建立
  • 校验信息: 用于崩溃恢复以及何时内存实际写入硬盘(原子替换) 通常而言, 在 drc 检查中可以视作版图是只读的, 且众多命令都有大量查询/搜索

布隆过滤器

用于优化查询效率节省存储空间, 与一般的 hash set 不同, 它根本不需要存储 key, 只需要 k 个比特位判断元素是否在集合中. 因此在 GDSII 中例如查询一个 cell, 可以先通过占用较小内存的 m 位位数组查询是否存在, 判断可能存在后再通过更大的哈希映射查询至实际的 cell 对象.

核心思想是位数组+多个哈希函数 通过一个长度为 m 的位数组表示元素的存在情况(初始化各位都为 0) 设置 k 个独立的哈希函数, 每个哈希函数都会将输入元素转换为一个 [0, m - 1] 的索引值, 因此可以将一个元素映射至位数组的某位上, 通过多个哈希函数将一个元素映射至多个位置(减少哈希冲突) 添加元素: k 个哈希函数会生成 k 个(不同的？)索引值, 因此有 k 个位置的值被设为 1 查询元素: 同样的哈希函数生成 k 个索引值, 判断这些索引位上的值是否为1, 如果存在0则一定不存在, 反之可能存在 误报漏报: 由于位数组有限, 因此一定存在哈希冲突使得不在集合内的元素由于其他元素的 key 值错误判断为该元素在集合内(误报), 但一定不会漏报(判断为不在集合内的元素一定成功) 复杂度: 插入与查询为 O(K), 空间为 O(m)

进一步讲一下误报率: 位数组长度为 m, 现有 n 个元素插入, 有 k 个哈希函数 某特定位仍然为 0 的概率 $P=(1-\frac{1}{m})^{kn}$ , 由此可以给定元素数量n与期望误报率来计算出最优哈希数量 k 与最小位数组长度 m

LSM 树

核心优化目标: 通过牺牲小部分读性能来提高写性能 主要模块有以下几个:

  • memtable: 可以理解为缓存, 是内存中的数据结构, 保存最近更新的值. 是一个有序排列的存储结构.
  • immutable memtable: 随着 memtable 扩大, 当扩大至一定程度(或周期性的)时, 将有序的 memtable 给持久化为 SSTable(sorted string table)的中间状态. 通过 memtable 写入, 转换过程中不阻塞数据更新
  • SSTable(sorted string table): 有序键值对, 存储至硬盘；同时考虑 SStable 读写问题, 在此基础上再套一层 key->offset 的键值映射, 且前方读写可以再加一层布隆过滤器

有一些缺陷可以被解决:

  • memtable 持久化至 sstable 这个过程中, 不同 sstable 可能存在相同 key, 除开最新的 key 对应的实际对象而言, 其他的键值映射是冗余无用的(即使包含故障恢复的情况, 这部分占用空间如果不处理也会很大), 因此在 sstable 上需要执行压缩操作
  • 读取时需要按时间倒序查询, 最差情况可能遍历所有 sstable. 这一点可以通过建立额外索引键值对+布隆过滤器优化 有一些缺陷较难解决:
  • compact 时磁盘 IO 占用大 同时也有一些优势:
  • 由于是大量有序写, 因此写时吞吐量高延迟较低, 在结构设计上容易实现压缩控制. 适合密集写入或批写入
    • 对于 gds 文件读写上, 常常涉及 cell 替换, 因此这个场景很适合使用

sstable compact

为了避免 sstale 的不断膨胀, 势必进行压缩, 策略有多种, 但无论如何最终都是在三个指标上做再平衡:

  • 读放大: 读取的数据量大于实际的数据量. 举例, 先试图在缓存中命中对象, 没有命中再去 sstable 找
  • 写放大: 写入的数据量大于实际的数据量. 举例, compact sstable 导致实际写大于对应键值的实际存储量
  • 空间放大: 显而易见, 例如上述的冗余键值映射

策略有以下两种:

  • size tired: 确保每个 sstable 的大小近似且限制每层 sstable 的数量. 当 sstable 的数量达到限制值时触发 compact, 将合并后的 sstable 放入下一层或直接构成一个更大的 sstale(接下来的 sstable 也会同步扩大)
    • 最底层的 sstable 大小会很大, 且同层 sstable 必定存储大量冗余信息(只有同层满了才触发一次 compact)
  • leveled: 限制每层的总大小, 并试图将每一层划分为多个大小相同的 sstable. 要求每层 sstable 是全局有序的. 当L层大小超出限制时, 至少选择一个对象将与L+1层相交的部分进行合并并写入L+1层.
    • 单层全局有序意味着每层不会有冗余映射
    • 写放大问题很严重, 可能触发递归导致逐层合并. 即使多线程下不相交的部分可以同时进行合并, 对于磁盘 IO 的占用是不可避免的.

GDSII 中的实际应用

键值设计: key: {cell_index(或者 cell_id), spatial_key(空间索引键值), object_seq(对象有序序列, 确保)} value: 序列化后的属性(bbox, ref, metadata等等)

This post is licensed under CC BY 4.0 by the author.