10x查询性能提升，全新UniqueKey的设计与实现1。2

　　作者：张晨SelectDB资深研发工程师
　　在实时数据仓库的业务场景中，能够友好支持数据的实时更新是一个非常重要的能力。例如在数据库同步（CDC）、电商交易订单、广告效果投放、营销业务报表等业务场景中，面对上游数据的变化，通常需要快速获取到变更记录并针对单行或多行数据进行及时变更，保证业务分析师及相关分析平台能快速捕捉到最新进展，提升业务决策的及时性。
　　而对于一贯不擅长数据更新的OLAP数据库而言，如何更好实现实时更新的能力，在数据时效性要求愈发强烈以及实时数仓业务应用范围愈加广阔的今天，成为了赢得激烈竞争的关键。
　　在过去ApacheDoris主要通过UniqueKey数据模型来实现数据实时Upsert，因底层采取了类似LSMTree结构，对于大数据量的高频写入具有足够强劲的支撑，但由于采取了MergeonRead的更新模式，因此读取效率成了制约ApacheDoris发挥实时更新能力的瓶颈，在应对实时数据的并行读写时可能引发查询抖动问题。
　　基于此，在ApacheDoris1。2。0版本中，我们在UniqueKey模型上引入了全新的数据更新方式MergeOnWrite，力求在实时更新和高效查询间得到统一。本文将详细介绍全新主键模型的设计实现以及效果。原UniqueKey模型的实现
　　了解ApacheDoris历史的用户可能知道，Doris最初的设计是受GoogleMesa启发，最初只有DuplicateKey模型和AggregateKey模型，而UniqueKey模型是在Doris发展过程中根据用户的需求而增加的。但那时实时更新的需求并没有这么强，UniqueKey的实现也相对比较简单只是将AggregateKey模型做了一层包装，并没有针对实时更新的需求进行深度优化。
　　具体而言，UniqueKey模型的实现仅是AggregateKey模型的一个特例，如果使用AggregateKey模型，并将所有非Key列的聚合类型都设置为REPLACE，则可以实现完全相同的效果。如下图所示，对一个UniqueKey模型的表exampletbl进行desc，最后一列的聚合类型显示它等价于所有列都是REPLACE聚合类型的AggregateKey表。
　　UniqueKey数据模型和AggregateKey数据模型都是MergeOnRead的实现方式，也就是说数据在导入时先写入一个新的Rowset，写入后并不会执行去重，只有在发起查询时才会做多路并发排序，在进行多路归并排序时，会将重复的Key排在一起，并进行聚合操作，其中高版本Key的会覆盖低版本的Key，最终只返回给用户版本最高的那一条记录。
　　下图是一个简化后的UnqueKey模型执行过程表示：
　　虽然其实现方式较为一致，但是UniqueKey和AggregateKey数据模型的使用场景有明显的差异：用户在创建AggregateKey模型的表时，对于聚合查询的条件是非常明确的按照AggregateKey指定的列进行聚合，Value列上的聚合函数就是用户主要使用的聚合方法（COUNTSUMMAXMIN等），例如将userid作为AggregateKey，将访问次数和时长进行SUM聚合来计算uv和用户使用时长。但UniqueKey数据模型的Key的主要作用其实是保证唯一性，而不是作为聚合的Key。例如在订单场景中，通过FlinkCDC从TP数据库同步过来的数据，是以订单ID作为UniqueKey来进行去重的，但查询的时候通常是对某些Value列（例如订单状态，订单金额，订单耗时，下单时间等）进行过滤、聚合和分析。不足之处
　　以上可知，用户使用UniqueKey模型进行查询的时候，实际上是进行了两次聚合操作，第一次是按照UniqueKey进行全部数据的逐Key聚合，去除掉重复的Key；第二次是按照查询真正需要的聚合条件进行聚合。而这两次聚合的操作就带来了比较严重的效率问题，导致查询性能低下：数据去重需要执行代价很高的多路归并排序，全量Key的比较非常消耗CPU的计算资源。无法进行有效的数据裁剪，引入大量额外的数据IO。例如某个数据分区有1千万条数据，但是符合筛选条件的数据只有1000条，OLAP系统丰富的索引就是用来高效地筛选出这1000条数据的。但由于无法确定具体文件里某条数据的值是否有效，使得这些索引派不上用场，必须先全部进行一次归并排序并对数据进行去重之后，才能对这些最终确认有效的数据进行过滤。这就带来了约1万倍的IO放大（这一数字仅为粗略的估计，实际的放大效应计算起来更为复杂）。方案调研与选型
　　为了解决原UniqueKey模型存在的问题，以更好的满足业务场景的需求，我们决定对UniqueKey模型进行优化，针对读写效率问题的优化方案展开了详细的调研。
　　关于以上问题的解决方案，业内已经有了较多的探索。代表性的有三类：DeleteInsert。即在数据写入时通过一个主键索引查找到被覆盖的key，将其标记为删除。比较有代表性的系统是微软的SQLServer。DeltaStore。将数据分为basedata和deltadata，basedata中的每一个主键都保证唯一，所有更新都记录在DeltaStore中，查询时将basedata和deltadata进行merge同，时有后台的merge线程定期将deltadata和basedata进行合并。比较有代表性的系统是ApacheKudu。CopyonWrite。在更新数据时直接将原来的数据整行拷贝、更新后写入新文件。数据湖采用这类方式的比较多，比较有代表性的系统是ApacheHudi与DeltaLake。
　　具体三类方案的实现机制及对比如下：DeleteInsert（即MergeonWrite）
　　比较有代表性的是SQLServer在2015年VLDB上发表的论文《RealTimeAnalyticalProcessingwithSQLServer》中提出的方案。简单来说，这篇论文提出了数据写入时将旧的数据标记删除（使用一个DeleteBitmap的数据结构），并将新数据记录在DeltaStore中，查询时将Base数据、DeleteBitmap、DeltaStore中的数据Merge起来以得到最新的数据。整体方案如下图所示，由于篇幅限制就不展开进行介绍了。
　　这个方案的优势在于，任何一个有效的主键只存在于一个地方（要么在BaseData中，要么在DeltaStore中），这样就避免了查询过程中的大量归并排序的消耗，同时Base数据中的各种丰富的列存索引也仍然有效。DeltaStore
　　DeltaStore的方式比较有代表性的系统就是ApacheKudu。在Kudu中，数据分为BaseData和DeltaData，BaseData中的主键都是唯一的，任何对于Base数据的修改会先写入DeltaStore中（通过行号标记与BaseData中的对应关系，这样可以避免Merge时的排序）。与前面SQLServer的BaseDelta不同的是，Kudu没有标记删除，所以同一个主键的数据会存在于两个地方，所以查询时必须将Base和Delta的数据合并才能得到最新的结果。Kudu的方案如下图所示：
　　https：www。slideshare。netclouderaapachekudutechnicaldeeppe
　　Kudu这套方案也能避免读取数据时的归并排序所带来的高昂代价，但是由于一个主键的数据会存在于多个地方，它就难以保证索引的准确性，也无法做一些高效的谓词下推。而索引和谓词下推都是分析型数据库进行性能优化的一个重要手段，这个缺点对于性能影响还是挺大的。CopyOnWrite
　　由于ApaceDoris定位是一个实时分析型数据库，CopyOnWrite方案对于实时更新来说成本太高，并不适合Doris。方案比较
　　下面的表格对比了各个方案，其中MergeOnRead是UniqueKey模型的默认实现，即1。2版本之前的实现方式，MergeOnWrite（写时合并）即前面提到的DeleteInsert方案。
　　如上可知，MergeOnWrite付出中等的写入代价，换取了较低的读取成本，对谓词下推、非key列索引过滤均能友好支持，并对查询性能优化有较好的效果。综合对比后，我们选择了MergeOnWrite作为最终的优化方案。新版方案的设计与实现
　　简单来讲，MergeOnWrite的处理流程是：对于每一条Key，查找它在Base数据中的位置（rowsetidsegmentid行号）如果Key存在，则将该行数据标记删除。标记删除的信息记录在DeleteBitmap中，其中每个Segment都有一个对应的DeleteBitmap将更新的数据写入新的Rowset中，完成事务，让新数据可见（能够被查询到）查询时，读取DeleteBitmap，将被标记删除的行过滤掉，只返回有效的数据关键问题
　　设计适合Doris的MergeOnWrite方案，需要重点解决以下几个问题：导入时如何高效定位到是否存在需要被标记删除的旧数据？标记删除的信息如何进行高效的存储？查询阶段如何高效的使用标记删除的信息来过滤数据？能否实现多版本支持？如何避免并发导入的事务冲突，导入与Compaction的写冲突？方案引入的额外内存消耗是否合理？写入代价导致的写入性能下降是否在可接受范围内？
　　根据以上关键问题，我们进行了一系列优化措施，使得以上问题得到较好的解决。下文中我们将进行详细介绍：
　　主键索引
　　由于Doris是面向大规模分析设计的列存系统，并没有主键索引的能力，因此为了能够快速定位到有没有要覆盖的主键，以及要覆盖的主键的行号，就需要给Doris增加一个主键索引。
　　我们采取了如下的优化措施：为每个Segment维护一个主键索引。主键索引的实现采用了似于RocksDBPartitionedIndex的方案。该方案能够实现非常高的查询QPS，同时基于文件的索引方案也能够节省内存占用。为每个Segment维护一个主键索引对应的BloomFilter。当BloomFilter命中时才会查询主键索引。为每个Segment记录一个主键的区间范围〔minkey，maxkey〕维护一个纯内存的区间树，使用所有Segment的主键区间构造。在查询一个主键时，无需遍历所有的Segment，可以通过区间树定位到可能包含该主键的Segment，大幅减少需要查询的索引量。对于命中的所有Segment，按照版本从高到低进行查询。在Doris中高版本意味着更新的数据，因此如果一个主键在高版本的Segment索引中命中，就无需继续查询更低版本的Segment。
　　查询单个主键的流程如下图所示：
　　DeleteBitmap
　　DeleteBitmap采取多版本的方式进行记录，具体如下图所示：
　　图中的Segment文件是由版本5的导入产生的，包含了该Tablet中版本5的导入数据版本6的导入中包含了对主键B的更新，因此会在Bitmap中将第二行标记删除，并在DeleteBitmap中记录版本6的导入对该Segment的修改版本7的导入包含了对主键A的更新，也会产生一个对应版本的Bitmap；同理版本8的导入也会产生一个对应的Bitmap
　　所有的DeleteBitmap存储在一个大的Map中，每次导入都会将最新的DeleteBitmap序列化到RocksDB中。其中关键定义如下：usingSegmentIduint32t；usingVersionuint64t；usingBitmapKeystd：：tupleRowsetId，SegmentId，Version；std：：mapBitmapKey，roaring：：Roaringdeletebitmap；
　　每个Rowset中的每个Segment，都会记录多个版本的Bitmap。Version为x的Bitmap意味着版本为x的导入对当前Segment的修改。
　　多版本DeleteBitmap的优点：能很好的支持多版本的查询，例如版本7的导入完成后，一个该表的查询开始执行，会使用Version7来执行，即使这个查询执行时间较长，在查询执行期间版本8的导入已经完成，也无需担心读到版本8的数据（或者漏掉被版本8删除的数据）能够很好的支持复杂的SchemaChange。在Doris中，复杂的SchemaChange（例如类型转换）需要先进行双写，同时将某个版本之前的历史数据进行转换后再删除掉旧版的数据。多版本的DeleteBitmap可以很好的支持当前的SchemaChange实现可以支持数据拷贝和副本修复时的多版本需求
　　不过多版本DeleteBitmap也有对应的代价，在刚才的例子中，访问版本8的数据，需要将v6、v7、v8的三个BitmapMerge在一起才能得出完整的Bitmap，再用该Bitmap对Segment数据进行过滤。在实时高频导入场景中，很容易产生大量的Bitmap，而Roaringbitmap的并集操作的CPUCost很高，为了尽可能减少大量并集操作的影响，我们为DeleteBitmap增加了LRUCache来记录最新合并过的Bitmap。写入流程
　　写入数据时会先创建每个Segment的主键索引，再更新DeleteBitmap。主键索引的建立比较简单，篇幅有限不再详细描述，重点介绍一些比较复杂的DeleteBitmap更新流程：
　　DeltaWriter会先将数据Flush到磁盘在Publish阶段去批量的点查所有的Key，并且更新被覆盖的Key对应的Bitmap。在下图中，新写入的Rowset版本是8，它修改了3个Rowset中的数据，因此会产生3个Bitmap的修改记录在Publish阶段去更新Bitmap，保证了批量点查Key和更新Bitmap期间不会有新增可见的Rowset，保证了Bitmap更新的正确性。如果某个Segment没有被修改，则不会有对应版本的Bitmap记录，比如Rowset1的Segment1就没有Version8对应的Bitmap读取流程
　　Bitmap的读取流程如下图所示，从图片中我们可知：
　　一个请求了版本7的Query，只会看到版本7对应的数据读取Rowset5的数据时，会将v6和v7对它的修改产生的Bitmap合并在一起，得到Version7对应的完整DeleteBitmap，用来过滤数据在下图的示例中，版本8的导入覆盖了Rowset1的Segment2一条数据，但请求版本7的Query仍然能读到该条数据
　　在高频导入场景下，可能会存在大量版本的Bitmap，合并这些Bitmap本身可能也有较大的CPU计算消耗。因此我们引入了一个LRUCache，每个版本的Bitmap只需要做一次合并操作。
　　Compaction与写冲突的处理
　　Compaction正常流程Compaction在读取数据时，获取当前处理的Rowset的版本Vx，会自动通过DeleteBitmap过滤掉被标记删除的行（见前面的查询层适配部分）Compaction结束后即可清理源Rowset上所有小于等于版本Vx的DeleteBitmap
　　Compaction与写冲突的处理在Compaction的执行过程中，可能会有新的导入任务提交，假设对应版本为Vy。如果Vy对应的写入有对Compaction源Rowset中的修改，则会更新到该Rowset的DeleteBitmap的Vy中在Compaction结束后，检查该Rowset上所有大于Vx的DeleteBitmap，将它们中的行号更新为新生成的Rowset中的Segment行号
　　如下图所示，Compaction选择了〔05〕，〔66〕，〔77〕三个Rowset，在Compaction过程中，Version8的导入执行成功，在CompactionCommit阶段，需要处理由Version8的数据导入所生成的新Bitmap
　　写入性能优化
　　在最初设计时，DeltaWriter不在写入数据阶段进行点查和DeleteBitmap更新，而是在Publish阶段做，这样能保证DeleteBitmap更新时可以看到该版本之前所有的数据，保证DeleteBitmap的正确性。但是在实际的高频导入测试中发现，Publish阶段串行对每个Rowset的数据进行全量点查和更新时，所引入的额外消耗会使得导入吞吐出现较大幅度下降。
　　因此在最终设计中，我们将DeleteBitmap的更新改成两阶段的形式：第一阶段可以并行执行，只查找和标记删除当时能看到的Version；第二阶段必须串行执行，将此前第一阶段可能漏查的新导入的Rowset中的数据再更新一遍。第二阶段增量更新数据量很少，因此对整体的吞吐影响非常有限。优化效果
　　新的MergeOnWrite实现通过在写入的时候将旧的数据标记删除的方式，能够始终保证有效的主键只会出现在一个文件中（即在写入的时候保证了主键的唯一性），不需要在读取的时候通过归并排序来对主键进行去重，这对于高频写入的场景来说，大大减少了查询执行时的额外消耗。
　　此外，新版实现还能够支持谓词下推，并能够很好利用Doris丰富的索引，在数据IO层面就能够进行充分的数据裁剪，大大减少数据的读取量和计算量，因此在很多场景的查询中都有比较明显的性能提升。
　　需要注意的是，如果用户使用UniqueKey的场景都是低频的批量更新，则MergeOnWrite实现对于用户查询效果的提升不一定明显，因为对于低频的批量更新，Doris的Compaction机制通常就能够较快的将数据给Compact到比较好的状态（也就是说Compaction完成了主键的去重），避免了查询时的去重计算代价。对于聚合分析的优化效果
　　我们使用TPCH100中数据量最大的Lineitem表进行了测试，为了模拟出多个持续写入的场景，将数据切分了100份，并进行了3次的重复导入。之后进行了count（）的查询，效果对比如下：
　　分别对比了无Cache和有Cache的情形，在无Cache的情况下由于从磁盘加载数据的耗时较多，整体上有大约4倍的性能提升；而排除掉磁盘读取数据的开销影响，在有Cache的情况下新版实现的计算效率能够有20多倍的性能提升。
　　Sum的效果类似，篇幅有限就不再列举。SSBFlat
　　除了简单的Count和Sum，我们还对SSBFlat数据集进行了测试，在100G数据集（切分成10份，多次导入来模拟有数据更新的场景）上的优化效果如下图所示：
　　关于测试结果的说明：在32C64GB的典型配置下，所有查询跑完的总耗时，在新版实现上是4。5秒，旧版实现为126。4秒，速度相差近30倍。进一步分析，我们发现在旧版实现的表上的查询执行时，32核CPU全部打满。因此更换了配置更高的机型来测试计算资源充足时旧版实现的表上的查询耗时在64C128GB的配置下，旧版实现总耗时49。9s，最高约跑满了48个核。在计算资源充足的情况下，旧版实现仍然与新版实现有12倍的性能差距
　　由此可见，新版实现不仅大大提升了查询速度，而且能够显著减少CPU的消耗。对数据导入的影响
　　新版的MergeOnWrite实现主要是为了优化数据的查询性能，如前所述也取得了不错的效果。不过这些优化效果是通过在写入时做了一些额外工作换取的，因此，新版MergeOnWrite实现会使得数据导入效率有小程度的变慢，但由于存在并发并且多个批次之间的导入可以形成Pipeline的效应，整体的吞吐没有明显的下降使用方式
　　在1。2版本中，作为一个新的Feature，写时合并默认关闭，用户可以通过在建表时添加下面的Property来开启：enableuniquekeymergeonwritetrue
　　另外新版本MergeonWrite数据更新模式与旧版本MergeonRead实现方式存在差异，因此已经创建的UniqueKey表无法直接通过AlterTable添加Property来支持，只能在新建表的时候指定。如果用户需要将旧表转换到新表，可以使用insertintonewtableselectfromoldtable的方式来实现。未来的规划
　　新版的MergeOnWrite实现能够兼容之前UniqueKey的所有功能，包括条件更新（使用Sequence列在乱序写入中保证数据更新的正确性）、通过DeleteSign进行批量删除、SchemaChange、UPDATE语句等。
　　从用户的反馈来看，UniqueKey模型目前对如下几个需求的支持水平还需要进一步提升，这也是我们下一步工作的重点：部分列更新。目前UniqueKey主要支持的是Upsert操作（也就是整行更新），暂时不支持Update操作（也就是每次只更新一部分列的数据）。但在订单、画像等场景中，存在大量的需求，需要频繁且实时的更新一部分状态列，当前只能通过AggregateKey模型的REPLACEIFNOTNULL功能来实现部分列更新。未来在Doris1。3版本中，我们计划支持完整的UniqueKey模型的部分列更新。提高点查性能。Doris采用的是列式存储，数据按列组织，列存系统天然在大规模数据分析中具有优势，在按行点查上存在劣势（因为一次读取一行需要进行N次磁盘文件的访问，相比行存系统来说存在非常大的IO放大问题）。随着Doris在订单、画像等对实时数据更新有强需求的领域的广泛使用，越来越多的用户提出了希望Doris支持高性能点查，以替代HBase等系统，来简化运维。这方面我们已经有了初步方案，正在开发中，预计在2023年上半年的新版本中可以发布。
　　目前ApacheDoris1。2版本已经发布，欢迎大家下载使用！也欢迎有兴趣的开发者可以一起参与到社区的开发中。