lxf's blog
0%

流量存储索引相关文章总结

发表于 分类于

索引相关知识

  • 现有的索引方法主要分为三种:哈希索引，B 树或者 B+树索引，bitmap 索引。
  • 哈希索引
    • 此方法在开始阶段，每个记录的插入只消耗较小的 CPU 时间。但是随着记录数目的增加，由于哈希冲突链长度的不断增加，之后的插入操作将会花费大量的时间去查找哈希表中的对应存储位置。
    • 只支持单域的相等性查找，不支持区间范围查找
    • 为组合字段建立索引的时候，针对部分索引字段的查询是不能支持的
  • B 树或者 B+树索引
    • 许多传统关系型数据库都是采用 B 树或 B+树索引方法，比如 MySQL
    • B 树和 B+树都是多路平衡查找树，他们的特点是可以保证索引键值的有序性并且能够在对数 时间复杂度内进行插入操作和查询操作
    • B+树与 B 树的不同在于 B+树的非叶子节点存储的都是关键字没有数据记录，数据记录都存在叶子节点上。所有的关键字都会出现在叶子节点当中，并且叶子节点会存储指向下一个叶子节点的指针，这样就可以对叶子节点的数据顺序地进行有序访问了。
    • 当一个节点包含的关键字满了的时候需要分裂成为两个节点，这 涉及到大量数据的拷贝工作，所以 B 树或 B+ 树在数据量非常大的时候并不能支持快 速实时的索引插入、查询操作
    • https://www.cnblogs.com/nullzx/p/8729425.html
  • Bitmap 索引
    • Bitmap 索引方法已经在许多数据存储领域广泛使用，此方法被证实非常适用于海量只读数据的索引和查询工作
    • bitmap 索引文件带来的磁盘消耗还是非常大，这不仅影响了实时索引建立的速度，并且增加了索引查询时的时间开销
    • 由于每次查询都需要读取全部相关的 bitmap 索引，索引文件的大小直接决定了从磁盘读入的时间，从而降低了索引查询时的速度
  • Trie 树
    • Trie 树最先被使用在字符串查找以及文本领域当中，又名前缀树或字典树。
    • Trie 树一个比较大的缺点是它的内存消耗可能会比较大，然而由于索引关键字的共享前缀特性和局部性特征使得这种不足表现得并不明显
  • BloomFilter
    • 布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。
  • 一般来说，B-树或决策树都很好地适应了具有唯一操作的数据，它们使用简单的if语句递归地划分空间索引相关知识
    • 现有的索引方法主要分为三种:哈希索引，B 树或者 B+树索引，bitmap 索引。
    • 哈希索引
      • 此方法在开始阶段，每个记录的插入只消耗较小的 CPU 时间。但是随着记录数目的增加，由于哈希冲突链长度的不断增加，之后的插入操作将会花费大量的时间去查找哈希表中的对应存储位置。
      • 只支持单域的相等性查找，不支持区间范围查找
      • 为组合字段建立索引的时候，针对部分索引字段的查询是不能支持的
    • B 树或者 B+树索引
      • 许多传统关系型数据库都是采用 B 树或 B+树索引方法，比如 MySQL
      • B 树和 B+树都是多路平衡查找树，他们的特点是可以保证索引键值的有序性并且能够在对数 时间复杂度内进行插入操作和查询操作
      • B+树与 B 树的不同在于 B+树的非叶子节点存储的都是关键字没有数据记录，数据记录都存在叶子节点上。所有的关键字都会出现在叶子节点当中，并且叶子节点会存储指向下一个叶子节点的指针，这样就可以对叶子节点的数据顺序地进行有序访问了。
      • 当一个节点包含的关键字满了的时候需要分裂成为两个节点，这 涉及到大量数据的拷贝工作，所以 B 树或 B+ 树在数据量非常大的时候并不能支持快 速实时的索引插入、查询操作
      • https://www.cnblogs.com/nullzx/p/8729425.html
    • Bitmap 索引
      • Bitmap 索引方法已经在许多数据存储领域广泛使用，此方法被证实非常适用于海量只读数据的索引和查询工作
      • bitmap 索引文件带来的磁盘消耗还是非常大，这不仅影响了实时索引建立的速度，并且增加了索引查询时的时间开销
      • 由于每次查询都需要读取全部相关的 bitmap 索引，索引文件的大小直接决定了从磁盘读入的时间，从而降低了索引查询时的速度
    • Trie 树
      • Trie 树最先被使用在字符串查找以及文本领域当中，又名前缀树或字典树。
      • Trie 树一个比较大的缺点是它的内存消耗可能会比较大，然而由于索引关键字的共享前缀特性和局部性特征使得这种不足表现得并不明显
    • BloomFilter
      • 布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。
    • 一般来说，B-树或决策树都很好地适应了具有唯一操作的数据，它们使用简单的if语句递归地划分空间

网络相关知识

  • 网络流量需要索引的字段具 有很强的局部性，比如 IP 地址字段和时间戳字段都拥有共享前缀的特征，对于 TCP/UDP 端口，协议号等字段的取值范围很小

The Case for Learned Index Structures

论文从索引的三个方面（Range Index/B-tree, Point Index/hash, Existence Index/bloom filter）论证了机器学习简历索引的可能性

  1. 把这几种索引的数据结构建立索引的过程抽象成机器学习建模的过程，把找寻index的过程看作机器学习进行预测的过程
  2. 利用数据分布以预测每个元素的位置，从而优化索引的存储空间和检索速度
  3. 应用机器学习+传统数据结构的混合模型进行建模，从而保证准确性
    存在的问题：
    1. 适用范围就仅限于只读，无法做到索引的修改
    2. 在最坏情况下有时候用的都是传统的数据结构
    3. 论文的实验部分只在单一的检索场景下进行了建模（例如：时间戳/url），没有针对组合查询的场景进行优化
    4. 似乎没有官方的代码开源

这篇论文将B-树和决策树看作一种类似的结构

  1. BTrees,ordecisiontreesingeneral,arereallygoodinoverfittingthedatawithafewoperationsasthey recursively divide the space using simple if-statements.

  2. For this paper, we focus on 2 types of models, simple neural nets with zero to two fully-connected hidden layers and ReLU activation functions and a layer width of up to 32 neurons and B-Trees (a.k.a. decision trees).

  • B-树是范围请求的最佳选择（例如，检索特定时间范围内的所有记录）

  • 哈希映射在单键查找中的性能很难击败

  • Bloom过滤器通常用于检查记录是否存在

  • 换句话说，知道准确的数据分布可以高度优化几乎所有的索引结构

    • 这里作者举了一个极端的例子来说明，比如我们的数据集就是 1-100 M，那么这时候如果使用 B 树其实不是最合理的，因为 key 值本身就可以作为偏移量使用，如果使用 B 树的话，无疑是把$O\left(1\right)$的时间复杂度变成了 $O\left (logn\right)$，并且由于索引的存在，所以内存空间也会由 $O\left(1\right )$ 变成 $O\left (logn\right)$ 。换句话说，当我们了解数据分布的情况下，其实可以优化数据库的索引。

  • 我们认为机器学习（ML）为学习反映数据模式的模型提供了机会，从而能够以较低的工程成本自动合成专门的索引结构，称为学习索引

  • B-树是一个模型，或者在ML术语中是一个回归树：它将一个键映射到一个具有最小和最大错误（最小错误为0，最大错误为页面大小）的位置，并保证该键可以在该区域中找到（如果存在）

    • 可以用其他类型的ML模型（包括神经网络）代替索引，只要它们也能够提供关于最小和最大误差的类似的有力保证
    • 对于新数据，B-树需要重新平衡，或者在机器学习术语中重新训练，以便仍然能够提供相同的错误保证
    • 我们可以用任何其他类型的回归模型代替B-树，包括线性回归或神经网络
    • 使用其他类型的模型作为索引可以提供巨大的好处: 有可能将B树查找的log(n)开销转换为一个常量操作

  • 在用学习的索引替换B-树之前，我们还需要解决其他技术挑战:

    • B-树在插入和查找方面的开销是有限的，并且特别善于利用缓存
    • B-树可以将键映射到不连续映射到内存或磁盘的页

  • 一个模型，预测一个排序数组中给定键的位置，有效地逼近了累积分布函数（CDF）

  • 实验1:

    • 使用ReLU激活函数训练了一个两层完全连通的神经网络，每层32个神经元
    • 时间戳是输入特征，排序数组中的位置是标签。

  • 实验2:

    • 论文开发了学习索引框架（LIF）、递归模型索引（RMI）和基于标准错误的搜索策略。
    • 递归模型索引的另一个优点是，我们能够构建混合模型
    • 对于整型数据集，相同内存占用时下，RMI经常能较btree有数倍性能提升。或者说性能相同时，内存占用会有数量级的优化
    • 许多（内存中的）索引能够通过使用节点之间的偏移量而不是指针来减少其存储需求
      • 论文从数据分布中学习以获得更紧凑的索引表示或性能增益
      • 更紧密地将现有的具有硬件意识的索引策略与学习模型结合起来，以进一步提高性能
    • B+树消耗大量内存
      • 论文提出了一种完全不同的索引压缩方法，这种方法依赖于数据分布，能够实现数量级的更小索引和更快的查找时间，甚至可能改变存储复杂性级别

  • 试图学习底层数据分布以预测每个元素的位置

  • 通过学习底层的数据分布进行存储压缩并预测key所对应的位置？

  • 适用范围就仅限于只读，无法做到索引的修改

github上论文 ‘The Case for Learned Index Structures’BTree部分的实现
  • 模型构建流程：
    • 输入：key,value（value就是label）
    • 输出：DNN+Btree 索引数组
    • 根据配置文件（有几层，每层有多少model，误差允许范围）
      • 第一层model根据全部数据（key,value）构建model
        • 对所有的key预测下一层的模型序号，并将数据key，value加入到下一层该模型的数据中
      • 之后的每一层除了最后一层外，重复上述动作，得到一个包含每层模型的数组
      • 判断最后一层得到的预测值与真实label的误差（MSE）
        • 如果误差大于误差允许范围，将数组该位置的DNN模型替换为B-Tree
  • 索引流程：
    • 输入：key
    • 从第一层开始根据key选择下一层的model，（上一层得到的预测值是为了选择下一层的模型序号，下一层的输入还是key），一层层选择直到到达最后一层获得pos
    • 存储时，DNN存储weights，bias，BTree按照Btree结构进行存储
  • 总的来看该方法所占空间的大小和配置时选择的每层模型数相关，每个模型只存储weights，bias相比于Btree减少了存储空间，但是可能会造成较大的误差，通过Btree替换的方式平衡存储内存与误差之间的关系。

Neural Packet Classification

  • 给定一个规则集和一个目标函数(例如，分类时间，内存占用，或两者的组合)，NeuroCuts学习建立一个最小化目标的决策树。
  • 剪切动作将沿选定维度（即SrcIP，DstIP，SrcPort，DstPort和协议之一）的节点划分为多个子范围（即2、4、8、16或32个范围），并且在树中创建了那么多子节点。另一方面，分区动作将节点的规则划分为不相交的子集（例如，基于维度的覆盖率），并为每个子集创建新的子节点。
    • 基于覆盖率就相当于学习数据分布？
    • Partition： 基于维度的覆盖率 -> 基于最大前缀的不同？
    • Cut：沿着选定维度划分为多个子范围
    • 比较：时间/内存方面与 B-树进行比较
  • partition_node根据rule在某一维度上的覆盖范围将rule划分为左右子树
    • 左子树覆盖范围小于threshold，右子树覆盖范围大于threshold
    • 覆盖范围选项 2%, 4%, 8%, 16%, 32%, 64%
  • cut_node将cut_dimension维度的范围分为cut_num份，根据rule所属的不同范围构建cut_num个子树
  • 树构建完成条件：叶子结点的rule个数小于leaf_threshold
  • 输入：rules
  • 输出：决策树

传统索引方法和Neural Packet Classification构建的不同

  • Trie/Hash-Trie/Bitmap-Trie 构建的索引有很多节点，且由于ip的特性，最多有四层，每层最多可能有256个节点
    • Hash-Trie利用最短不相交前缀，使得搜索路径的长度<4
  • DRL优化决策树的时候有partition/cut这两个action，按照范围或者覆盖维度进行切分，将rule进行划分
    • 而索引的时候是要固定到某一位置的
    • 如果是对构建好的树进行优化，只能采用剪枝的方案？
      • 先构建一个完全树，然后在从底层往上走，action选择是否取消该节点？
    • 如果是在构建的时候进行优化action选择在这个位置是否构建节点？
      • 但是对于第一层来说，每个src（xxx.xxx.xxx.xxx）的第一个都应该构建节点
      • 下一层的时候，才有可能（由于最短不相交前缀的特性）不再继续往后构建节点（xxx.xxx）和（xxx.xxx.xxx.xxx）是一样的

Accelerating B+tree Search by Using Simple Machine Learning Techniques

​ 主要思路：对构建好的B+树的每个节点构建一个用于搜索的线性回归模型，在准确率偏差到一定程度时利用新的数据重新训练以适应新插入的key和node。

存在的问题：

  1. 构建好B+树后再根据B+树构建模型，在内存上相当于多出了一部分空间进行存储
  2. 仅是针对搜索查询进行了优化

​ 索引性能对于内存OLTP系统来说非常重要。本文提出用简单的机器学习模型来加速B+树搜索。我们针对每个索引节点训练一个线性回归模型，并使用这些模型在连续的层级上预测索引节点。在预测出叶节点后，我们只需跳到预测出的叶节点，并进行局部搜索以找到记录。提出了一种将学习模型集成到B+树搜索操作中的算法，并在存在插入的情况下自适应地训练学习模型。
​ 实验结果表明，该方法对叶片节点的预测准确率为80%～96%，搜索时间缩短了33%～57%。此外，该方法对插入具有鲁棒性，能够快速更新机器学习模型，以适应新插入的key和node。

  • Kraska 假设的是只读工作负载和聚集索引组织，其中数据存储在连续的内存位置。
    • 本文支持插入，并将数据作为数据页存储在非连续的内存位置
      • 带来的挑战：
        • 插入学习模型：需要一个再培训阶段来更新学习的模型
        • 在非连续存储器位置存储数据禁止将关键位置直接用作学习模型的标签：需要一种标记机制来将搜索键映射到叶节点
      • 将简单的线性回归模型整合到现有的B+树索引中
  • 本文只加速了搜索查询阶段
  • 使用两个辅助数据结构将线性回归模型集成到B+树搜索算法中:
    • model table
      • 节点号映射到指向特定节点所在内存位置的指针上
    • mapping table
      • 预测节点号
      • 节点号是人为创建的标签，用于训练线性回归模型
    • 为了满足再训练过程中的插入查询，在每个叶子节点上保留一个溢出缓冲区
      • 当节点满了的时候，将记录插入到这个缓冲区中，从而防止节点被拆分
      • 搜索查询如果在节点本身找不到记录，则检查溢出缓冲区
  • 对每个树节点的再训练包括三个主要任务：
    • 更新用作标签的节点编号
      • 节点编号方式：
        • 在每一级，对节点进行连续编号，从1到N，其中N是该级的最后一个节点
        • 对于均匀分布，直接使用节点号作为标签
        • 对于倾斜分布，使用节点号的自然对数作为标签，将非线性关系转化为线性关系
    • 收集训练数据并训练新的回归模型
    • 更新映射和模型表项
    • retrain过程
      • 广度优先搜索遍历树
        • 在每个节点的访问中，节点号会被更新
        • 在每个叶级节点统一随机收集一次trainning key
        • 对trainning key执行搜索查询并保存搜索遍历的节点的键和节点号生成训练数据
          • 这里的搜索查询采用的是对B+树的遍历？
        • 再训练过程使用生成的训练数据为每个节点创建一个新的线性回归模型