共计 11665 个字符，预计需要花费 30 分钟才能阅读完成。
本篇论文是 Facebook 2019 年发表介绍 Presto 的综述类论文，本篇论文从 Presto 的应用示例、架构、零碎设计等几个方面零碎的介绍了 Presto 的内核和实现原理，对于通识性的理解 Presto 有肯定帮忙。
注：本篇论文中所介绍的 Presto 版本是 0.211 版本，过后 Presto 还没决裂出 PrestoDB 和 PrestoSQL。
一、Presto 介绍
Presto 作为一个分布式查问引擎，于 2013 年开始就曾经在 Facebook 的生产环境中应用。并且现在曾经在 Uber、Netflix、Airbnb、Bloomberg 以及 LinkedIn 这样的大公司中应用。
Presto 具备 自适应、灵便以及可扩大 等个性。Presto 提供了规范的 ANSI SQL 接口来查问存储于各零碎中的数据，如 Hadoop、RDBMS、NoSQL 数据库中的数据，以及 Kafka 这样的流式组件中的数据（Presto 中内置了十分多的 connectors 供用户应用）。Presto 对外提供了开放式的 HTTP API、提供对 JDBC 的反对并且反对商业规范的 BI 的查问工具（如 Tableau）。其内置的 Hive connector 源生反对对 HDFS 或 Amazon S3 上的文件进行读写，并且反对多种风行的开源文件格式，包含 ORC、Parquet 以及 Avro。
二、Presto 在 Facebook 的应用示例
1.Interactive Analytics（交互式剖析）
Facebook 内运行着一个宏大的多租户数据仓库，一些业务部门或个别团队会共享其中一小部分托管的集群。其数据存储在一个分布式文件系统之上，而元数据则存储在独自的服务中，这些零碎别离具备 HDFS 和 Hive Metastore 服务相似的 API。
Facebook 的工程师常常会检索大量的数据 (50GB-3TB 的压缩数据)，用来验证假如，并构建可视化的数据展板。这些用户通常会应用查问工具、BI 工具或 Jupyter notebooks 来进行查问操作。各个群集须要 反对 50-100 的并发查问能力 ，并且 对查问响应工夫十分敏感。而对于某些探索性的查问，用户可能并不需要获取所有的查问后果。通常在返回初始后果后，查问就会被立刻勾销或者用户会通过 LIMIT 来限度零碎返回的后果。
2.Batch ETL（批量 ETL）
下面咱们介绍到的数据仓库会应用 ETL 查问工作定期填充新的数据。查问工作通常是通过一个工作流零碎顺次调度执行的。Presto 反对用户从历史遗留的批处理零碎迁徙 ETL 工作，目前 ETL 查问工作在 Facebook 的 Presto 工作负载中占了很大一部分。这些查问通常是由数据工程师开发并优化的。绝对于 Interactive Analytics 中波及的查问，它们通常会占用更多的硬件资源，并且会波及大量的 CPU 转换和内存（通常是数 TB 的分布式内存）密集型的计算，例如 大表之间的 join 及聚合 。因而绝对于资源利用率以及集群吞吐量来说， 查问提早不是首要关注的。
3.A/B Testing（A/ B 测试）
Facebook 应用 A / B 测试，通过统计假设性的测试来评估产品变更带来的影响。在 Facebook 大量的 A / B 测试的基础架构是基于 Presto 构建的。用户冀望测试后果能够在数小时之内出现（而不是数天），并且后果应该是准确无误的。对于用户来说，可能在 交互式提早的工夫内（5~30s），对后果数据进行任意切分来取得更深刻的见解同样重要。而通过预处理来聚合这些数据往往很难满足这一需要，因而必须得 实时计算。生成这样的后果须要关联多个大型数据集，包含用户、设施、测试以及事件属性等数据。因为查问是通过编程形式实现的，所以查问须要被限度在较小的汇合内。
4.Developer/Advertiser Analytics（开发者 / 广告主剖析）
为内部开发者和广告客户提供的几种自定义报表工具也都是基于 Presto 构建的。Facebook Analytics 就是其中一个理论案例，它为应用 Facebook 平台构建应用程序的开发人员提供了高级的剖析工具。这些工具通常对外开放一个 Web 界面，该界面能够生成一组受限的查问模型。查问须要聚合的数据量是十分大的，然而这些查问是有目的性的，因为用户只能拜访他们的应用程序或广告的数据。大部分的查问包含连贯、聚合以及窗口函数。因为这些工具是交互式的，因而有十分严格的 查问提早限度（约 50ms~5s）。鉴于用户的数量，集群须要达到 99.999% 的高可用，并且 反对数百个并发查问。
三、Presto 架构概览
一个 Presto 集群须要由 一个 Coordinator以及 一个或多个 Worker节点组成。Coordinator 次要负责接管查问申请、解析语句、生成打算、优化查问以及查问调度。Worker 节点次要负责查询处理。如下所示的即为 Presto 架构：
整体的执行流程能够简述如下：
客户端向 Coordinator 发送一个蕴含 sql 的 http 申请。Coordinator 接管到这个申请，会通过评估队列策略，解析和剖析 sql 文本，创立和优化分布式执行打算来解决申请。
Coordinator 将执行打算分发给 Worker 节点，接着 Worker 节点开始启动 tasks 并且开始枚举 splits，而这些 splits 是对外部存储系统中可寻址的数据块的一种费解解决。Splits 会被调配给那些负责读取数据的 tasks。
Worker 节点运行这些 tasks 来解决从内部存储系统获取的 splits，以及来自于其余 Worker 节点解决过得两头数据。Worker 节点之间通过多任务单干机制来并发解决来自不同查问的 tasks。工作尽可能的以流水线的形式来执行，这使得数据能够在 tasks 之间进行流动。对于某些特定的查问，Presto 可能在解决完所有数据之前就返回后果。两头数据以及状态会尽可能地存储在内存中。当在节点之间对数据进行 shuffle 时，Presto 会调整缓冲区来达到最小化的提早。
Presto 被设计成可扩大的，并提供通用的插件接口。插件能够提供自定义的数据类型、函数、访问控制、事件监听策略、排队策略以及属性配置。更重要的是插件还提供了 connector，这使得 Presto 能够通过 Connector API 和内部的存储系统进行通信。Connector API 次要蕴含如下四个局部：Metadata API、Data Location API、Data Source API 以及 Data Sink API。这些 API 能够帮忙在分布式查问引擎中实现高性能的 connectors，开发者曾经为 Presto 社区提供了数十个 connector，而且咱们也留神到了一些专有的 connectors。
四、Presto 零碎设计
1.SQL Dialect（SQL 反对）
Presto 采纳了规范的 ANSI SQL 标准，具备肯定的扩大能力，例如反对 maps and arrays, 反对 anonymous functions (lambda expressions)，反对高阶函数 higher-order functions。
2.Client Interfaces, Parsing, and Planning（接口、语法解析和逻辑打算）
Presto 的 Coordinator 基于 RESTful HTTP 提供命令行接口并反对 JDBC。基于 ANTLR 的解析器把 sql 转为相应的语法树。logical planner 把 AST 形象语法树变为逻辑执行打算，叶子节点是 input。例如上面的 SQL 转化为如图的逻辑执行打算。
SELECT
orders.orderkey, SUM(tax)
FROM orders
LEFT JOIN lineitem
ON orders.orderkey = lineitem.orderkey
WHERE discount = 0
GROUP BY orders.orderkey如上生成查问的逻辑打算如下所示：
3.Query Optimization（查问优化）
打算优化器会将逻辑打算转换成可能示意无效执行策略的物理构造。转换过程是通过 RBO（Rule-Based Optimization：基于规定的优化器） 做 plan nodes 的等价变换，较常见的规定包含 predicate and limit pushdown（查问下推）、column pruning（列剪枝）以及 decorrelation（去相关性）。基于 CBO（Cost-Based Optimization：基于代价的优化器） 也在加强，原理是利用 Cascades framework 在搜寻空间外面找到最优的打算，目前曾经实现的两类 CBO 是 join 办法的抉择（hash index，index join 等）以及 join reorder。
以下是对一些比拟重要的优化伎俩的列举：
3.1 Data Layouts（数据属性）
Connector 提供了 Data Layout API，优化器能够获取待扫描数据的地位信息以及分区、排序、分组和索引等信息。例如做工作散发的 locality aware，partition pruning，sort pushdown，index join 等。
3.2 Predicate Pushdown（查问下推）
范畴和等值查问的下推，能够更好的 filter inputs。举例来说，在 MySQL 分片之上构建了专有的 Connector。Connector 将存储在 Mysql 实例上的数据划分成小的数据分片，并且依据范畴和点查，下推到指定的分片。
另外对于 highly selective filters 的查问非常适合查问下推，能够利用分区裁剪（partition pruning）和 file-format feature（比方 min-max 等粗糙集索引）缩小 IO。
3.3 Inter-node Parallelism（节点间并行计算）
Plan node 中蕴含了输入数据的各类信息（如分区、排序、分片及分组等数据个性），而后 Plan node 会在 worker 间并行执行 Plan nodes 组成的 stages，stage 物理上体现为多个 tasks 的并行执行，task 就是雷同的算子，只是在不同的 input data 上。stage 间通过插入 exchange 算子，利用 buffer 来替换数据，shuffle 是计算和 IO 密集型的，因而怎么在 stages 间做 shuffle 十分重要。下图就是一个执行打算，靠 shuffle 串联起来。
3.4 Intra-node Parallelism（节点内并行执行）
单节点过程内同样能够并行，hash table 和字典能够在线程外面 shards 分区并行，论文里提了两个 use case，用节点内多线程并行能够减速计算，下图是一个例子，扫描数据和 hash build 都能够并行起来，靠 local shuffle 替换数据。
4.Scheduling（调度）
Coordinator 通过散发可执行的 task 的形式，向 Woker 节点调配执行打算的各个 stage，这些可执行的 task 能够被看作单个处理单元。接着，Coordinator 将一个 stage 的 task 与其余 stage 的 task 通过 shuffles 相连接，从而造成一个树形的解决链路。只有各个 stage 都是可用的，数据就会在 stage 之间流转。
这里须要先了解 Presto 外面的 stage、task、pipeline、driver 的概念（能够参阅 Presto 官网文档）。Coordinator 把 plan stages 分发给 worker，stage 只是形象的概念，worker 内理论运行的被称作 task，这是最小的执行单元 。task 有输出和输入，靠 shuffle 把上下游的 task 连接起来。比方在理论调试页面外面有 0.x，1.x，0 示意 stage 0，x 示意 stage 内 task 的并行度。
一个 task 能够蕴含 1 到多个 pipeline，pipeline 蕴含一系列 operators，例如 hash-join 算子包含至多两个 pipeline，build table pipeline，另外一个是流式的 probe pipeline。优化器如果发现一个 pipeline 能够反对并行优化，那么就会把一个 pipeline 拆开，例如 build pipeline 能够拆成 scan data 和 build partitions 两个 pipeline，节点内并行度能够不同。pipeline 间接用 local shuffle 串联起来。driver 在 Query Execution 中来介绍。
调度策略用于决定哪些 stage 该被执行，stage 内多少个 tasks 并行调度起来。
4.1 Stage scheduling
在这一调度阶段，Presto 反对两种调度策略：一次性调度（all-at-once）以及 阶段调度（phased）。前者能够实现将所有的 stage 调度起来，实用于提早敏感的场景，例如上文中的 A / B 测试和广告主服务。后者的典型操作如 hash-join，须要先 build 好，再启动 probe 端，比拟节约内存，实用于批处理场景。
4.2 Task Scheduling
Table scan stage 的调度会思考网络拓扑和数据 locality，比方 share-nothing 的部署模式下，须要有一部分 worker 和 storage node co-located 起来，Intermediate Stages 能够执行在任何 worker 节点类型上。profling 的结果表明 table scan 很多花在解压、decoding、filters、applying transformation，读数据到 connector 上，通过下面提到的节点内并行能够最小化 wall time。在 facebook，presto 用 share-storage 模式部署，这时候网络往往最先成为瓶颈。为了补救计算存储拆散架构下的拜访提早高问题，倒退出了 Raptor connector。
4.3 Split Scheduling
在 table scan stage 读取数据之前，须要先获取存储的 split，比方 file 的门路和 offset，分好 split 后才能够正式启动执行；Intermediate Stages 则不同，随时能够执行。
5.Query Execution（查询处理）
5.1 Local Data Flow（本地数据流）
一旦 data split 调配给线程后，它会在 driver 中循环执行。Presto 的 driver 中的循环比风行的 Volcano 递归迭代器模型更简单，但却提供了重要的性能。它更实用于多任务的合作解决，因为算子（operator）能够在线程生成之前就迅速进入已知的状态，而不是有限地阻塞上来。此外，driver 能够在不须要额定的输出文件的状况下，通过挪动 operator 之间的数据使每个数据量子的执行效率达到最大化（如复原资源密集型的计算或爆炸性转换的计算）。循环的每次迭代都会在 operators 之间挪动数据驱使查问一直的执行。
drive 循环中操作的数据单元称之为 page，而一个 page 为某一列一串行值编码后的数据。Connector 的 Data Source API 在传入一个 data split 之后会返回若干个 page。drive 中的循环会在 operators 之间挪动 page 数据，直到调度实现或 operator 无奈继续执行为止。
5.2 Shuffles
为了尽可能升高查问提早，最大化资源利用率，shuffle 采纳了 In-memory buffer shuffle，同时基于 HTTP 协定，上游 worker 通过 long-polling 向上游 worker 申请数据，实现了一种ACK（音讯确认）的机制，保证数据不丢不重，上游能够依照上游吞吐产出数据和清理数据。
对于 shuffle 的并发度 Presto 设计了一种监控机制，例如一旦 output buffer 过满，执行 stall 并且耗费内存，input buffer 又较为闲暇，便会导致解决效率又有余。因而通过监控 buffer 的使用率，能够实现自行调控 shuffle 并行度，进而防止上述的极其景象，网络资源便能够在多个申请间进行均衡。
5.3 Writes
ETL 是 insert into select 的工作模式，通常会写入其余表，connector data sink writer 的并行度管制是自适应 adaptive 的，以此来实现最大化的写入吞吐。
6.Resource Management（资源管理）
Presto 非常适合多租户应用，而要害的因素就在于它内置了一个细粒度资源管理零碎。这使得一个集群能够同时执行数百个查问，并最大水平地利用 CPU，IO 和内存资源。
6.1 CPU Scheduling（CPU 调度）
上文中已经介绍过 Presto 要反对的特点是 adaptive，最大化集群资源利用率，多个 queries 间要做 偏心调度（fair sharing），这样能够让短查问也有机会执行。
一个 worker 外面有多个 task 须要执行，task 执行分片粒度叫做 quanta（maximum quanta of one second）, 一个 task 执行完 quanta 周期后，会放回 queue 外面期待再次被调度。如果 output buffer 已满，或者 input buffer 闲暇，那么会提前退出，不等一个周期的 quanta。调度计划采纳多级反馈队列（multi-level feedback queue，5 级），执行总工夫越长的 task 会放到更高级别的队列中。Presto 应用一个外部的 yield 指令来做 task 间的切换（集体了解，即便看起来 context switch，然而非 os 级别的，有点协程的轻量级个性，使得集群能够 multi-tenant 的服务，短查问也有工夫高优实现）。cpu 运行工夫越少的 task 会被优先调度，这样能够确保短查问能更快被执行完，而长查问自身对于提早也不是十分敏感。
6.2 Memory Management（内存治理）
Presto 的 Memory pool（内存池）分两类，user or system memory（用户内存）, 以及 reserve memory（预留内存）。
reserve memory个别寄存 shuffle buffers 这些和用户查问无关的数据。这二者的内存都有管制，超过限度的阈值查问就会被 kill 掉。个别依据查问的 pattern 来布局集群规模和内存。对于超过内存限度的查问，Presto 有两种应答办法，spilling：对于大 join 和 agg 计算，spill to disk。不过在 Facebook 生产环境不会应用 spill to disk，因为太过影响性能，集群会被 prevision 成足够的规模，在内存计算和 shuffle。
reserved pools：如果节点内存不足，并且集群没有配置为 Spilling，或没有残余的可撤销内存，reserved pool 机制能够保障集群不被阻塞。每个节点上的查问内存池会进一步被细分为两个池：general pool 和 reserved pool。当 Worker 节点上的 general pool 耗尽时, 那么在 worker 节点上的占用内存最多的那查问会在整个集群中被晋升到 reserved pool 中。在这种状况下，该查问所耗费的是 reserved pool 中的内存，而不在是 general pool 中的内存。为了防止死锁，在整个集群中同时只有一个查问能够在 reserved pool 中执行。如果 Worker 节点上的 general pool 内存已用完，而 reserved pool 也曾经被占用，那么该 Worker 节点上其余 task 的所有内存相干的申请将被阻塞。运行在 reserved pool 中的查问会始终占用该 pool 直到其执行实现，这个时候，群集将进行阻塞之前所有未实现的内存申请。这在某种程度上看起来有点节约，因而必须正当的调整每个 Worker 节点上 reserved pool 的大小，以满足在本地内存限度下运行查问。当某个查问阻塞了大部分的 Worker 节点时，集群也能够配置成 kill 掉这个查问。
7.Fault Tolerance（容错）
Presto 能够通过 low-level（低级别）的retry（重试）从长期的谬误中复原。然而，一旦 Coordinator 或 Worker 节点产生了解体，没有任何内置的容灾措施能够解救。Coordinator 的故障将导致集群的不可用，而 Worker 节点的解体将导致该节点上所有正在执行的查问失败。目前，对于这样的谬误，Presto 须要依附 Client 端从新提交失败的查问来解决。
目前，对于上问题的容错解决在 Facebook 的生产环境中是通过额定的机制保障某些特定场景下的高可用。在 Interactive Analytics 和 Batch ETL 的案例中运行着一个备用的 Coordinator，而在 A /B Testing 以及 Developer/Advertiser Analytics 的案列中，运行着多个集群来保障高可用。内部监控零碎会辨认那些产生异样故障数量的节点并将它们从集群中剔除，而被修复的节点会重新加入集群。以上的措施都是在某种程度上升高服务不可用的工夫，然而无奈齐全屏蔽故障的产生。
罕用的 check pointing 以及局部复原机制通常是十分耗费计算资源的，并且很难在即席查问零碎中实现。基于复制策略的容错机制通常也是相当耗资源的。思考到这样的老本开销，这种技术的预期价值还尚不明确，尤其是在思考到节点均匀故障工夫时，如在 Batch ETL 的案列中，集群的节点数达到了数千个并且大部分的查问都是在数小时之内实现的。在其余的钻研中也得出过相似的论断。
五、查问优化
1.Working with the JVM（应用 JVM）
Presto 是通过 java 实现的，并且运行在 Hotspot Java 虚拟机上，一些性能敏感的计算例如压缩，checksum 能够用非凡的指令和优化。JIT（JVM 即时编译器）能够将字节码 runtime 的优化为 machine code，例如 inlining, loop unrolling, and intrinsics（一些 native 代码的调用），同时也在摸索用 GraalVM 来优化。
Java 的实现须要非常重视GC（垃圾收集），Presto 采纳了 G1 GC，同时为了加重 GC 的累赘，防止创立 humongous 大对象，flat memory arrays to reduce reference and object counts and make the job of the GC easier。同时因为 G1 须要保护对象汇合的构造（remembered sets tructures），所以大型和高度关联的对象图可能会存在一些问题。查问执行门路上的关键步骤的数据结构是通过扁平化的内存数组来实现的，目标就是为了缩小援用以及对象数量，从而使 GC 变得绝对轻松一点。例如，在 HISTOGRAM 聚合中，会在一个扁平的数组或哈希表中存储所有组中的 bucket keys（桶键）以及对象计数，而不是为每一个 histogram 保护独立的对象。
2.Code Generation（代码生成）
引擎的次要性能特色之一，就是生产 JVM 字节码。这有如下两种表现形式：
Expression Evaluation（表达式求值）：Presto 所提供的表达式解释器能够将表达式计算编译成 java 代码，从而减速表达式的求值。
Targeting JIT Optimizer Heuristics（针对 JIT 的优化器）：Presto 会为一些要害算子（operators）和算子组合生成字节码。字节码生成器利用引擎在计算语义方面的劣势来生成更易于 JIT 优化器进行优化的字节码。防止 quanta 做 task 工夫片切换对 JIT 的影响，防止类型推导以及虚函数调用，JIT 也会进一步适配数据的变动。
生成的字节码还得益于内联所带来的二次效应。JVM 可能扩充优化范畴，主动向量化大部分的计算，并且能够利用基于频率的基本块布局来最大水平地缩小分支。这样使得 CPU 分支预测也变得更加无效。字节码生成进步了引擎将两头后果存储在 CPU 寄存器或 CPU 缓存中而不是内存中的能力。
3.File Format Features（文件格式的个性）
扫描算子（Scan operator）应用叶子阶段 split 的信息来调用 Connector API，并以 Pages 的模式接管列数据。一个 page 由一个 block 列表组成，而每个 block 是具备扁平内存示意模式的列。应用扁平内存的数据结构对性能十分重要，尤其是对那些简单的数据类型。在紧凑的循环体内，指针跟踪，拆箱和虚构办法调用都减少了大量的开销。
而这类 connectors 会尽可能的应用特定的文件格式。Presto 配有自定义的 reader，能够通过应用文件页眉 / 页脚中的统计信息（如页眉中保留的最小 - 最大范畴和布隆过滤器），来高效地过滤数据。Reader 能够间接将某些模式的压缩数据间接读成 blocks，从而让引擎能够无效地对其进行解决。
下图显示了一个 page 中列的布局形式，其中每一列都有其对应的编码方式。字典编码的块（DictionaryBlock）在压缩数据的低基数局部十分高效，游程编码的块（run-length encoded block，RLEBlock）对反复的数据进行压缩。多个 page 能够共享一个字典，这能够大大提高内存利用率。ORC 文件中的一列能够为整个“stripe”（最多数百万行），应用单个字典。
4.Lazy Data Loading（数据的懒加载）
Presto 反对数据的惰性物化（lazy materialization）。此性能能够利用 ORC，Parquet 和 RCFile 等文件格式的列压缩个性。Connector 能够生成惰性的 blocks，仅当理论拜访时才读取，解压缩和解码数据。
5.Operating on Compressed Data（对压缩数据的解决）
Presto 所采取的第一种解决办法是 在压缩数据上间接进行计算 。如上图中的构造，当 page 处理器在计算转换或过滤时遇到 dictionary block，它将解决 dictionary 内的所有的值（或 RLE 的块中的单个值）。这容许引擎以疾速的无条件循环解决整个 dictionary。在某些状况下，dictionary 中存在的值多于 block 中的行。在这种场景下，page 处理器揣测未援用的值将在后续的 block 中应用。Page 处理器会继续跟踪产生的理论行数和 dictionary 的大小，这有利于比照解决索引和解决 dictionary 的效率。如果行数大于 dictionary 的大小，则解决 dictionary 的效率可能更高。当 page 处理器在 block 序列中遇到了新的 dictionary 时，它会应用这种启发式的办法确定是否持续揣测。
Presto 所采取的第二种解决办法是在 用字典值代替数据自身进行计算。在构建哈希表（如联接或聚合）时，Presto 还会利用 dictionary block 构造。在解决索引时，operator 会在数组中记录每个 dictionary entry（字典条目）在哈希表中的地位。如果有条目在后续的索引中反复，会简略的重用该条目标的地位而不是从新对其进行计算。当间断的 blocks 共享同一 dictionary 时，page 处理器将保留该数组，来进一步缩小必要的计算。
六、工程相干
在这一部分中，提供了 Presto 在设计上所参考的一些工程哲学，这些对于 Presto 的设计和倒退有着重要意义，也十分具备借鉴意义。
- Adaptiveness over configurability（基于配置的自适应性）
自适应高于配置。例如 cpu 执行的 quanta 分片机制使得短查问能够疾速执行，ETL 写入的并行度，反压等个性。
- Effortless instrumentation（唾手可得的工具）
细粒度的性能统计信息。通过 Presto 的库（libraries）收集统计信息，并且针对每一个查问收集了算子（operator）级别的统计信息，并将这些信息合并到 task 以及 stage 级别的统计信息中。通过这些细粒度的监控伎俩，使得 Presto 在优化时能以数据为驱动。
- Static configuration（动态配置）
如 Presto 这样的简单零碎，诸多操作问题很难疾速地定位本源并予以解决。因而 Presto 抉择不动静调整配置，防止集群不稳固。
- Vertical integration（垂直集成）
Presto 的各组件都应该能够很好的与 Presto 交互，比方发现 gzip 包慢，那么 Presto 就自行革新实现。在多线程下的 debug 和控制能力也十分重要。
最初，咱们简短的进行一个总结。在本篇论文中，咱们介绍了 Presto，这是一个由 Facebook 开发的开源的 MPP SQL 查问引擎，能够疾速的解决大型的数据集，具备自适应、灵便以及可扩大等个性，值得咱们对其的一些实现原理进行深刻的钻研。