从面部识别签到到“猜你喜欢”的各种应用，机器学习（尤其是深度学习技术）已经广泛应用于我们生活的方方面面日常生活。深度学习框架（如TensorFlow、PyTorch等）和AI专用芯片（如：TPU、NPU等）等软硬件系统的设计极大地提升了机器学习的性能，拓展了其应用领域场景。同时，机器学习方法本身能否用于优化计算机系统设计，甚至取代传统设计模式？谷歌技术大神JeffDean带领的研究团队在2018SIGMOD学术会议上发表了一篇有趣的作品：TheCaseforLearnedIndexStructures[1]。本文简要介绍了LearnedIndexStructures的实现、优缺点，希望能给大家带来一些系统设计的灵感和思路。1.什么是学习索引结构？索引（index）是数据库、文件系统等领域中常见的一种数据结构。最经典的是B-Tree。B-Tree是一种范围索引（RangeIndex）数据结构。查询时给定一个key（或一些具有一定范围的key），B-Tree会索引到包含该key的对应范围的叶子节点，在叶子节点中查找key。如果key在索引中存在，则获取其对应的位置。通常，逻辑页中的记录将使用键进行索引。如图1(a)所示，输入为key，输出为待查询记录对应的位置区间。除了范围索引，还有HashMap等点索引和布隆过滤器等ExistenceIndex，也是常用的索引数据结构。LearnedIndexStructures的主要思想是用机器学习模型代替B-Tree或BloomFilters等数据结构——搜索操作变成了根据key预测索引数据的位置，如图1所示(二).下面以范围索引为例，详细介绍LearnedIndexStructures的设计和实现思路。图1B-Tree和LearnedIndex示意图图1是传统B-tree和LearnedIndex的对比。可以看出，LearnedIndex的输入是Key，输出是这个key对应的检索结果的位置（可能有错误）。结尾）。那么如何设计用于范围索引的机器学习模型呢？这里只考虑一维聚簇索引的情况（即数据按照用于查找的key进行排序，非聚簇索引可以通过聚簇索引添加指向真实数据排列的指针来实现).LearnedIndexStructures非常聪明，如图2所示，索引位置实际上是一个单调递增的函数，随着键的增长而增长。虽然具体的索引可能是离散的，但仍然可以用一个函数作为一个整体来描述：p=F(Key)*N其中p是估计的位置，N是索引键的个数，F(key)是索引数据的累积分布函数(CDF)。F(key)的含义是小于等于key的索引数据项之和（即key的位置估计）。它本质上反映了数据集的分布特征。与B-Tree的一般设计相比，LearnedIndexStructures考虑了数据集固有的分布特性，并利用它来优化索引的结构。LearnedIndex误差上限可控，在误差范围内根据预测位置向左或向右二分查找即可准确找到搜索目标。图2索引位置的累积概率分布（CDF）那么如何学习得到F(Key)呢？LearnIndexStructures的作者首先尝试使用TensorFlow构建了一个每层32个神经元和两层全连接神经网络的神经网络。用web服务器日志的数据集训练后发现，效果远不如B-Tree。问题是：1）TensorFlow用于大规模神经网络的训练，小规模场景的调用开销变得不可忽略。2）欠拟合问题，如图2所示，机器学习模型可以很好地估计CDF的整体趋势，但很难在单个数据项上得到准确的表示。但是B-Tree可以使用if语句简单高效的精确划分范围。为了优化“最后一英里”的机器学习模型，需要大量的存储空间和计算资源消耗。3）B-Tree的CPU和缓存行为经过高度优化设计，每次搜索只使用少量索引。机器学习模型需要使用所有参数权重来完成预测。最终的LearnIndexStructures模型是使用图3中所示的阶段模型实现的。每个模型可以是任何机器学习模型，从最简单的线性回归（LR）到深度神经网络（DNN）。实际上，模型越简单越好（避免在查找模型时花费太多时间在模型上）。在查找时，最顶层模型（只有一个模型）会选择一个二级模型来处理这个键。然后第二层的模型再选择下一层的一个模型来处理key，直到最底层模型才会给出key对应的预测位置。但实际上，上层的每个模型都输出了预测位置，而这个预测是用来选择下层模型的（模型id=（预测位置/总记录数）*本层模型数）。整个StagedModel是分层训练的，先训练顶层，再分发数据。数据分布是指上层模型对哪个下层模型进行预测的关键，而该模型有这个训练数据作为它的训练集。因此，随着层数的加深，每层模型数量的增加，每个下层模型的训练数据变少。这样做的好处是底层模型可以很容易地拟合这部分数据的分布（缺点是数据量小对模型的选择带来限制，复杂的模型无法收敛）。[1]中采用的结构是：只在顶层使用神经网络模型，其余层使用线性回归模型。图3学习索引结构的阶段模型点索引和存在索引的学习索引结构。我不会在这里详细介绍。有兴趣的可以阅读论文[1]和基于论文的RMI（RecursiveModelIndexes）代码[2]。].2.LearnedIndexStructures如何评价？总的来说，LearnedIndexStructures向我们展示了机器学习在系统领域的巨大潜力，但是还有很多问题需要解决（比如：过拟合，索引增删改查等）。对于过拟合，如果新索引的key仍然满足CDF，则不需要重新训练，直接插入到预测的位置即可。如果数据分布会发生变化，则需要尝试在线学习（Onlinelearning）的方法。对于数据更新频繁的系统，可以使用delta-index技术增量更新学习到的索引。事实上，以LearnedIndexStructures为代表的机器学习优化方法并不是系统设计优化的终结者。例如，splineB-tree[6]在B-tree的每个叶子节点中只使用一个样条（即key和它的位置），两个样条之间的数据由两点之间的直线预测。这样一个简单的数据结构往往相当于一个复杂的LearnIndex，甚至更好。在PointIndex领域，通过减少冲突来优化LearnedIndex可以很容易地被bucketizedcuckoohashing[7]击败，它只是将每个键同时散列到两个桶中。但这并不否定机器学习在系统设计中的价值。机器学习可以激发系统设计的优化和思考，探索以前未被发现的系统设计思路。在优化原则明确、场景固定的情况下，很明显人工解释和重新实现在效率和稳定性上优于机器学习方法。在数据分布等特性动态变化的场景下，机器学习方法可以优化适应数据特性，理论上可以优于通用算法和数据结构。3.机器学习+系统设计=？或许LearnedIndexStructures还有很多不足，但不可忽视的是，机器学习应用于计算机系统设计的趋势已经到来。如果说LearnIndexStructures是机器学习进入计算机系统设计领域的声音，那么2019年发布的机器学习系统白皮书[5]正式确立了机器学习与计算机系统设计交叉学科研究方向的诞生。正如JeffDean在SysML18大会的主题演讲中所说：“任何使用启发式技术的系统领域都是机器学习可能应用的好地方——编译器、网络、操作系统、芯片设计等。”要想成功，有两个关键点：1）找到一个可以用数字准确表示的优化指标；2）有清晰的集成机器学习的接口（定义模型的输入和输出，训练和测试数据集的获取等）。对于计算机系统领域的优化来说，这两个要求似乎比较容易实现。
