Jeff Dean领导谷歌大脑用机器学习颠覆数据索引方法将变革传统数据库设计理念

原题目：Jeff Dean带领谷歌大脑用机械进修倾覆数据索引方式，将变化保守数据库设想理念雷锋网

原题目：Jeff Dean带领谷歌大脑用机械进修倾覆数据索引方式，将变化保守数据库设想理念

雷锋网 AI 科技评论按：伴跟着机械进修理论和手艺的成长、以及机械进修作为一门学科有越来越多的人关心以及参与，机械进修的落地使用场景也越来越多、越来越多样化。这两年的抢手的使用大师都已很是熟悉，深度神经收集+强化进修下围棋的 AlphaGo，还有用深度神经收集做语音生成的 WaveNet，都是在保守方式研究已久但没有什么冲破性进展的范畴引入深度进修，用全新的思绪、全新的东西达到了天神下凡一般令人惊讶的结果，稍加迭代更新当前更是精美绝伦。

近期，谷歌大脑也公开了一篇新的革命性论文，测验考试把机械进修使用在保守上基于确定的法则和算法的数据库系统中，而且还取得了很好的初步功效：对于实在数据的索引使命，神经收集成立的索引能够比保守的缓存优化 B 树索引方式提高 70% 的速度，同时存储空间还能节流一个数量级。包罗 Jeff Dean 在内的作者们也会商并测验考试了若何用神经收集承担数据库系统中更多分歧的使命，他们感觉这是一个全新的、很是有潜力的研究和使用标的目的，很可能会影响将来的数据库系统的设想理念。雷锋网 AI 科技评论把这篇论文《The Case for Learned Index Structures》（聊一聊进修获得的索引架构）的部门内容引见如下。

对于计较机系统来说，只需有高效拜候数据的需求，就能够成立一个索引布局。索引的思惟成长到此刻，也曾经有了各类各样的方式能够处置各类分歧的拜候模式。举例来说，对于范畴拜候（好比读取某个时间段内的所有记实），B 树是最佳选择；对于基于键值的查询使命，哈希表方式的机能很是优良；而若是要查询记实能否具有，Bloom Filter 就是大都时候的选择。因为索引在数据库系统以及其它一些使用中有着很是主要的感化，过去的十多年中各类索引方式就不竭地获得更新改良，各类新方式对内存、缓存以及 CPU 资本的利用也越来越高效。

不外，目前所有的索引方式都仍然是通用型的数据布局，它们都假设数据是以最蹩脚的体例分布的，而没有益用到实在数据中常常表现出的分布特点。好比，若是方针是建立一个高度定制化的系统，用于固定长度的、持续的整型（好比 1 不断到 1 亿如许）键值的存储和查询，这种时候用保守的 B 树对键值成立索引就不是一种好方式，由于键值本人就能够看作偏移量，对于查找肆意键值、或者查找某个范畴键值起始位置的使命，时间复杂度反倒从 O(log n) 提高到了 O(1)；同样，把键值本人看作偏移量的话，索引所用的内存大小也能够从 O(n) 削减到 O(1)。可能有点惊人的是，其它的数据分布模式也都能够找到各自适合的优化体例。换个角度说，若是晓得了数据的切当分布，不管数据库此刻用的是什么样的索引方式，几乎都还能够做进一步的高度优化。

当然了，大都现实使用场景中的数据都不必然完满合适某个已知的数据分布，而且，若是为每一种利用情况都别离建立公用的处理方案的话，需要投入的成本也太高了。不外，这篇文章的作者们（包罗 Jeff Dean 在内的四位谷歌研究员以及一位其时在谷歌拜候的 MIT 学者）认为机械进修此刻带来了一个全新的机遇，它学到的模子能够反映数据的内在联系和分布模式。在此根本之上还能够进一步主动生成公用的索引布局，作者们称之为「进修获得的索引」（learned indexes），同时工程方面的成本也较低。

在这篇论文中，作者们探究了机械进修学到的模子（包罗神经收集），可否用来替代 B 树、Bloom Filter 等如许的保守索引布局。这件事可能有点反直觉，由于保守索引方式往往需要有确定的语义保障，而机械进修凡是供给不了这个；别的，神经收集虽然是最强大的一类机械进修模子，但同时人们也保守上认为评估它们结果所需的成本太高。不外作者们提出，这些较着的坚苦在现实中并没有看起来那么严峻，并且恰好相反，作者们提出的进修模子的方式很有潜力能够带来较着的益处，特别是在为大规模矩阵运算设想的下一代硬件上。

具体来说，在语义保障方面，现代索引方式很大程度上曾经是一些学到的模子，在这种现状下，把现有的模子替代成新的模子其实曾经是一件很是简单间接的工作了，包罗替代成神经收集也是一样。好比，一个 B 树索引能够看作是如许一个模子：它领受一个键值作为输入，然后预测对应的数据记实的位置；Bloom Filter 能够看作一个二值分类器，给定一个键值当前它能够预测这个键值能否具有。当然了，这此中也有一些细微但长短常主要的区别，好比斯刻的 Bloom Filter 可能会呈现误报为真的环境，但不会呈现误报为假。不外，这篇论文稍后将会展现出，借助新的进修技巧和/或简单的辅助数据布局，这些区别都是有可能获得处理的。

在机能方面，作者们察看到现在的 CPU 全都有强大的 SIMD（单指令大都据）计较能力，并且他们也猜测很多笔记本电脑和手机很快城市有 GPU 或者 TPU。他们还猜测，CPU-SIMD/GPU/TPU 城市变得越来越强大，由于比拟通用指令集来说，这些处置器都可以或许更简洁地扩大神经收集需要的很是无限的一部门数学运算的运算规模。那么运转神经收集所需的高计较力耗损将来就可能终究变得何足道哉。举例来说，NVIDIA GPU 和谷歌 TPU 都能够在单个时钟轮回内完成数千、以至数万次神经收集的计较操作。更进一步地，曾经有人指出，到 2025 年时 GPU 的速度还能再提拔一千倍，到那时摩尔定律对于 CPU 曾经根基失效了。只需把分支数量可观的索引布局替代为神经收集，数据库系统就能够从如许的硬件成长趋向中受益。

这里我们重点引见一下论文中神经收集进修获得的索引与 B 树索引之间的对比。

数据库的索引布局其实曾经是一种模子，由于索引的感化就是给定键值之后「预测」这笔记录地点的位置。假设如许一种环境，用 B 树对内存中的阐发型数据库（也就是只读数据库）的有序主键成立索引，如下图 1(a)。在这种环境下，B 树索引供给了从要查询的键值到各笔记录构成的有序数组中的一个位置的映照，同时可以或许包管记实数组中这个位置的键值和查询的键值相等或者大于查询的键值。值得一提的是，数据需如果有序的才能进行范畴拜候请求；而且，这种总体概念同样合用于二级索引，此中最基层是键值，指针对构成的列表，此中的键值就是被索引的属性，指针指向的就是数据记实。

为了让索引比力无效率，凡是的做法中并不会对有序记实数组中的每一个键值都做索引，而是每隔 n 个记实做一个索引，这也就是每个分页中的第一个键值。如许能够显著减小索引中需要存储的数据量，同机会能下降很是轻细。正由于如许，B 树就是一个模子，用机械进修的术语的话能够把它称为回归树（regression tree）：它把一个键值映照到一个位置，它带有最大和最小误差（这里的最小误差为 0，最大误差是分页大小），同时只需这个值具有，就能够确保在这个范畴内找到它。

那么接下来，我们就能够把这个索引机制用其它类型的机械进修模子替代掉，包罗能够用深度进修模子替代，只需它们也同样能够供给雷同的包管，确保数据只需具有就能在最小误差和最大误差构成的范畴之间找到它。

第一眼看上去似乎很难找到有什么类型的机械进修模子能够供给如许的误差包管机制，可是它现实上出奇地容易。B 树其实只能对存储了的数据供给这种包管，而不克不及对所有可能的数据供给如许的包管。对于新添加的数据，B 树需要从头均衡——用机械进修的术语来说就是「从头锻炼」——之后才能供给同样的误差包管。这就能够大幅度简化问题：要供给包管的最小和最大误差就是模子对于锻炼数据（存储的数据）的最大误差。也就是说只需要做一件事，对每一个键值施行机械进修模子，然跋文住位置预测时最蹩脚的向上偏离值和向下偏离值。给定了一个键值当前，模子就会对在哪里找到这条数据做出预测；若是这个键值具有，那它就必然在预测的最小误差和最大误差定义出的范畴内。接下来就能够把 B 树替代为肆意一个具体类型的回归模子，包罗线性回归或者神经收集，如上图 1(b) 所示。

在正式把 B 树改换为进修获得的索引之前，仍是有一些手艺方面的挑战需要处理的。好比，B 树对于插入和查询操作的计较成本是在无限的范畴内的，并且可以或许很是好地操纵缓存；同时，B 树能够把键值映照到并不持续映照在内存或者磁盘中的分页中；进一步地，若是要查询的键值在数据库中不具有，如许的模子前往的位置可能会在最小/最大误差范畴之外，若是这不会枯燥地添加模子大小的话。所有这些特点都是风趣的挑战和研究课题。机械进修，特别是神经收集有如许一种魔力，就是它们能够进修到很多种分歧的数据分布、数据夹杂以及其它一些数据的模式以及奇异的特点。那么，这里还剩下的较着的挑战，就是在模子的复杂度和精确度之间找到均衡，而作者们也提出了一些可能的处理方案。

作者们起首测验考试了一个朴实的方式，用 TensorFlow + Python 实现了一个具有两层全毗连层、每层 32 个神经元的神经收集。用它为 200MB 的 web 办事器日记记实做二级索引，把时间作为输入特征、把位置作为收集预测的标签进行锻炼和测试。如许获得的模子施行一次就需要破费 8 万纳秒；比拟之下 B 树只需要 300 纳秒时间，并且在键值空间中搜刮的速度也要更快。

TensorFlow 平台本身的设想方针是高效运转较大的模子，所以运转开销很大，特别是搭配 Python 利用时；

B 树，或者决策示范型，总体来说逐次切分数据空间时很是高效；其它模子估量数据具有的总体累积概率密度的能力要更好，可是到了最初数据空间不大（统计纪律起头变得不较着）时，速度就会变慢；

典型的机械进修优化方针是优化平均误差。然而对于索引使命，现实上更主要的是具体的最大误差和最小误差值；

B 树的缓存效率很是高，它总会缓存顶端的节点，然后再缓存一些其它需要的分页。比拟之下神经收集就需要从内存中读取所有的权值才能完成一次运算。

为了降服这几个问题，展示出理论上可行的设法的现实可行性，作者们特地开辟了如许几个方式协助实现进修获得的索引。学习数据库

作者们编写了 Learning Index Framework，索引进修框架 LIF，能够把它看作一个索引生成系统：给定一种索引规格，LIF 就会生成分歧的索引设置装备摆设，而且优化它们、主动测试它们。LIF 能够借助 TensorFlow 中实现的更复杂的模子，边运转边进修简单的模子；同时它的推理过程并不依托 TensorFlow，它会从学到的模子建立出高效的 C++编译版本，如许推理时能够大幅削减不需要的计较开销，运转时间缩减到了30纳秒级别。

Recursive model index，递归模子索引 RMI 是为领会决前面提到的数据空间变小当前模子预测能力变差的问题。举例来说，从 100M 笔记录中寻找数据时，最大最小误差若是想要缩小到几百的数量级，只笔据个模子长短常难的；但同时，把误差缩小到 10k 的数量级，用这一个模子替代 B 树的最上两层就要简单得多，用简单的模子就能够做到。同样，下一层的模子只需要把误差从 10k 缩小到几百，因为它只需要关心数据的一个子集，所以也是一个较为简单的问题。

如许，作者们提出了递归模子索引 RMI。如图，作者们设想了层级化的收集布局，此中包含很多个模子，每一层中的模子都领受键值作为输入，然后据此选择下一层的模子，直到最初一层的模子对位置做出预测。在这里，每一个模子都能够看作是对键值空间的某一部门管任，在逐层选择的过程中逐步降低了预测误差。作者们也证了然如许的模子是能够逐层锻炼，最终获得完整的收集的。

但同时值得留意的是，RMI 不是示范型。正如上图所示，分歧的上层模子能够选择统一个基层模子；而且，此中的每个模子笼盖的数据范畴并不是像 B 树那样固定的；最初，因为预测是靠分歧模子间的选择完成的，所以对这个过程的理解不应当看作是“对位置的预测逐步切确”，而是“逐次选择了对这个键值具有更勤学问的模子”。

如许的模子能够高效地把数据空间朋分成了多个小空间，从而用更少的操作提高了最初数据空间很小时的预测精度；

收集中分歧的层之间不需要任何搜刮操作。好比，模子 1。1 的输出间接就选择出了下一层的模子 1。2。这不只削减了办理整个布局所需的指令的数目，并且还能够把整个索引表告竣能够在 TPU/GPU 上完成的矩阵相乘操作；

如许的布局能够答应混用分歧的模子。好比最上层的模子能够是利用 ReLU 激活函数的神经收集，由于它们凡是能够学到良多种分歧的复杂数据分布；底层的模子就能够是数千个简单的线性回归模子，由于它们需要的空间和施行时间都很少。

这篇论文中作者们就编写算法锻炼了一个分歧模子构成的 RMI 收集。具体来说，此中的单个模子能够是带有 0 到 2 层全毗连层和 ReLU 激活函数的简单神经收集，每层最大宽度为 32 个神经元；也能够是 B 树，也就是决策树。想要其它类型的模子也能够，这里作者们先用了这两类。

按照作者们的设想，每个模子的尺度最小/最大误差会存储在最下面一层的模子中，这种做法带来的益处是能够按照利用的模子为每个键值零丁设定搜刮空间的大小。作者们也为混用模子收集中设想了一个替代功能，一起头收集中所有模子都是神经收集，而若是某处神经收集模子的绝对最小/最大误差高于某个阈值的话，锻炼算法就会把这个神经收集模子替代成 B 树。如许现实上也就是设定了这个混用模子收集的表示的下限：对于最蹩脚的、无法进修的数据分布，混用模子收集就根基上是一个 B 示范型；而在除此之外的环境下，模子都理应有更好的表示。

作者们在几个数据集上把学到的索引模子和 B 示范型进行了对比。B 示范型选用了分歧的分页大小；而学到的索引模子选用了一个 2 层的 RMI 模子，测试中也给出了分歧的第二阶段模子搜刮数量大小的表示。对于模子布局，第二阶段的模子现实上在布局最简单（0 个全毗连层），根基就是线性模子的时候有最好的表示；这也并不奇异，由于搜刮空间曾经减小之后，运转更复杂的模子反倒不划算。整个学到的索引模子用 LIF 编译之后，运转在不带有 GPU/TPU 的英特尔 E5 CPU 上。

Weblogs 数据集包含近几年中某个大学网站的 200M 条拜候记实，每笔记录都有分歧的时间戳。这个数据集几乎能够算是最蹩脚的环境了，由于它的数据模式会遭到课程规划、周末、节假日、午餐、学院勾当、放假时间等等要素的影响，很是难以进修。

而现实测试成果显示出，与 B 树比拟，学到的索引模子不只老是更快，耗损的空间也最多能够节流 99%，也就是两个数量级。

地图数据集包含了大约 200M 条用户添加的全世界的地标消息。这个数据集的数据就更线性、不纪律性更小。所以进修获得的索引比拟 Weblogs 数据集中更好的表示，不只能够提速跨越 60%、大小减小最多 99%，最大预测误差也减小了良多。

如许的成果不只无力地验证了论文开首作者们提出的「当数据有纪律时，机械进修的方式能够优化索引效率」的猜想，并且初步尝试的结果就出人预料地好。

值得申明的是，作者们并没有筹算用学到的索引完全代替保守的索引架构。现实上，他们是想要指出一种新的成立索引体例，它该当是现有研究的弥补，并且为曾经有几十年汗青的数据库索引范畴开启了一个全新的研究标的目的（当然这也还有待更多后续研究和会商）。

这篇论文中作者们的研究重点在于纯读取负载（键值查找、数据定位、具有性搜刮），同时也大要会商了若何把这种思绪拓展到重写入负载的系统的加快上。作者们也进一步简要描述了若何用同样的思惟把数据库系统的其它组件和操作也做个替代，包罗排序和归并。若是这些研究的进展成功的话，这可能会成长成离开现无数据库系统模式的新做法，高维度索引、进修数据库操作算法、GPU/TPU 加快数据库操作城市是成心思并且有深远实意图义的研究方针。

总的来说，作者们表了然机械进修学到的模子有潜力在现有的顶级数据库索引方式根本上继续带来显著的提高，这不只是数据库相关手艺研究的新标的目的，更是机械进修在又一个新范畴拓土开疆。