华为云数据库创新LAB在论文《ESTELLE: An Efficient and Cost-effective Cloud Log Engine》中提出了自研的云原生低成本日志引擎ESTELLE。SIGMOD会议是由美国计算机协会（ACM）数据管理专业委员会组织的、数据库领域的最顶级国际学术会议。ESTELLE是云数据库创新LAB在可观测性领域取得的关键技术成果之一。

随着业务的快速发展，企业快速扩张，企业服务变的复杂且脆弱，因此为了提升整个系统的可观测性。需要引入相关服务监控。其中日志作为可观测性的重要数据源之一，可用于调试、根因分析、故障排除等场景。

但是构建一个优秀的可观测性的日志服务具有较多的挑战：

• 海量且集中地数据导入压力
• 低频但跨度较大的查询压力
• 多种场景的日志及聚合查询服务
• 低成本的日志引擎服务

为了解决上述问题，本文提出了一个高性价比的云原生日志引擎。关键贡献如下：

1. 本文实现了一个高性价比、读写分离、存算分离的云原生日志引擎，并提供了近无锁的写入流程，以满足海量的日志数据写入；

2. 本文提出了一种低成本的可插拔的日志索引框架，主要包括ESTELLE LOG Bloom Filter和近似倒排索引两个模块。相较于传统的bloom filter，每个模块的设计都是针对云原生存储的I/O友好型方案，并且提供了and查询、近似聚合等查询能力；

3. 本文通过实验在开源数据集上验证了ESTELLE 具有高性能写入能力、低存储开销及稳定高效的查询能力。

作为整个日志引擎的核心，本质上是一个由众多节点组成的集群，其中每个节点存在一个状态（写或读）。当ELB接受到来自上层应用程序的请求，会基于读写请求随机分配到读写节点。

其中查询节点进一步细分为Coordinator及Subquery node，接受请求的读节点称为Coordinator，Coordinator会将分布式任务分发给Subquery node。

每个节点都包含多个worker任务，每个worker任务粒度为一个线程，系统内部处理的粒度为shard。

对象存储服务OBS是华为云提供的海量、安全高可靠、低成本的对象存储服务，与其他存储服务相比，存储成本较低，访问时延相对较高，而日志场景中，大多为高频写入、低频率查询场景，因此通过OBS持久化存储日志数据及相关索引。

弹性文件服务SFS为华为云基于NFS提供的按需可扩展的高性能文件存储，可同时挂载在多台云服务上，提供共享存储服务。SFS相较于OBS而言，速度较快，但成本较高，在ESTELLE 中，用于高频数据flush场景。当写入节点的日志未达到目标数据，但用户下发flush指令，希望数据可见时，将数据临时写入sfs中，这样避免高频OBS写入操作，以减少性能损失。

Meta集群主要负责管理系统的元数据及集群状态。其主要存储了数据库schema、权限、保留策略（RP）等信息，以及监控整个集群中的节点状态，负责分片（shard）的分配及接管。

ESTELLE日志引擎布局如上所示，一个DataRow主要包括时间及数据内容，多个数据行累积构成一个block；一个block为数据压缩和索引的基本单元，在每个shard中，会有n组index及block；每个shard为读写管理的最小单元，每个shard会根据数据的时间分到不同的ShardGroup中，可用于加速查询和数据老化；每个Logstream为多个shardgroup的组合，可以近似理解为一个数据表；每个Repository是logstream的集合，可以近似理解为一个数据库。

如架构图所示，写入过程分为online任务和offline的写入任务。下面介绍在线和离线写入任务的区别。

如下图所示为在线任务的相关写入流程，当收到上层应用的写入后，ELB会随机分配给写集群的一个节点，写节点会创建多个对应PT个数的worker，并将数据打散到不同的PT中，每个pt在每一天会创建对应的shard，并向其写入数据。每个PT对应一个写入队列，encoder对日志数据进行消费、分词生成对应的数据索引，并缓存在memtable中。

当写入数据块达到目标配置大小时，会将数据直接追加写入到OBS上；而当用户发出flush指令或超过30s写入时延，且数据块没有达到配置大小，会将其先写入SFS中，使其数据可见，当累计到目标block大小后，会将数据转储到OBS上。当数据持久化到OBS后，memtable及sfs数据会被清空。

考虑到OBS的随机读取性能较差的问题，索引在memtable及sfs上为行存储，转储到OBS上时会转为列存储，相关内容将在下文进行详细介绍。

上述的写入流程有以下的几个好处：

1. 从整个写入流程而言，除写入队列外，整个过程保持无锁的写入状态，这样会极大的提升写入速度；

2. 整个写入并发度基于PT进行调整，在Serveless场景下，可以很好的实现扩缩容机制，且可以保证良好的写入线性度；

离线任务为一个可插拔的组件模块，其目的为生成或更新高频词的哈希表，以便于其他的可插拔索引模块使用。其在每一天shard结束后，可以随机采集部分数据，统计更新词频，记录词频大于目标阈值的词于hash表之中，并为每个hash表生成一个版本号。每个shardgroup 创建时，会记录最新的符合条件hash表的版本号，用于后续写入及查询。

整个查询过程主要包括两个阶段：coordinator请求分配及子查询节点实际查询过程。

Coordinator收到查询请求后，会解析、生成及优化plan，并最终创建执行计划，并将子执行计划分配到对应的子查询节点。当子查询节点处理完成后，coordinator会收集、合并查询结果，并将最终的查询结果返回给上层应用。

子查询节点本身是无状态的，为充分利用缓存，coordinator会优先将相同的shard任务分给相同的查询节点，尽可能的增加缓存命中率，减少与OBS的交互，提升查询性能。

Subquery node接收到子计划后，也会对子请求解析和优化，并结合当前资源管理器，创建多个PT级别的并发任务。

每个任务会使用到多种查询缓存。从存储介质的角度来看，整个缓存可以分为内存缓存和本地缓存。查询涉及的小的索引缓存到内存之中，包括元数据信息、高频词hash表等；其他索引缓存到本地，包括bloom filter、近似倒排索引等。从缓存模式角度来看，整个缓存可以分为在线缓存和离线缓存，在线缓存主要缓存当前执行命中的缓存，以用于应对短时间内相同过滤条件的查；离线缓存主要使用时间滑动窗口的方法将最新的数据索引进行缓存，以增加最近时间相关的查询效率。

为了快速、准确的访问日志数，在成本较低可控的情况下支持多样化的日志查询，我们设计了一个如下图所示的日志索引框架。

索引框架存储级别为shard级别。以下为几个模块内容介绍：

Metadata：存储了每个block的基础元信息，包括最大最小时间、数据行数、offset 及size等信息；

Log Data：日志数据压缩后的数据，每一行代表一条日志数据；

Log Indexes：每个block对应一个可插拔、低成本的索引，包括布隆过滤器和近似倒排索引。这两个索引在SFS及内存中都为行存储，在OBS中以列存储形象储存，详细内容将在后文中介绍。索引基础版本仅包括ESTELLE Log Bloom filter（简称EL-BF），为了优化高频词的直方图查询及低频次的and查询，会生成Frequency Division Bloom filter(缩写为 ELFD-BF)；

Mapping Schema：每个shard的索引依赖于Mapping schema模块，以获取对应的hash函数及高频词的hash映射表。基础的hash函数会将词映射为64位无符号整数，用于bf的hash运算；高频词hash表通过区分高低频词分到对应的bf中以减少bf的冲突。高频词的挖掘由上一节中离线任务计算获取，并因为高频词的数量较少，会常驻与内存之中；

据我们所知，ESTELLE Log Bloom Filter（简称EL-BF）是第一个为云原生日志引擎架构设计的布隆过滤器，在本节中，将会介绍EL-BF的设计。

下文将会介绍EL-BF的工作流程、存储格式，与传统布隆过滤器相比，在云原生架构下的优势及理论误判率。

Workflow：整个EL-BF工作流程如下图所示，它包括一个2^x+8大小的数组和一个hash函数，三个映射函数，我们使用了MurmurHash3 算法用于将词映射为64bit的hash值；hash的前x位作为该词在EL-BF上的offset值，然后取该offset往后的8byte位用于映射函数的计算，如果映射函数的四位值都为1，即认为该block包括含目标词。

Columnar-Store Format：为了最大程度使用顺序扫描并减少查询过程中的IO，我们为EL-BF设计了一种列式存储格式。当行存EL-BF在内存中累加到g的数量形成一个group后，会将行存bf转为列存bf，并flush到OBS中。

如下图所示，左图为行存的格式，右图为列存的格式。虚线箭头表示数据的存储顺序。行存EL-BF会按照每8个byte进行切割，每个bf共有h=(2^x+8)/8个piece，第i个block中第j组的piece表示为：

行存的piece顺序为

, 转为列存后，即为

ESTELLE Log Bloom Filter VS. Standard Bloom Filter：标准的BF在检查一个词是否存在与BF中，会有两种方法。第一种是依次扫描OBS，将整个BF读取到内存中，这样的IO开销交到；第二种方法是随机读取目标位置的BF，这在磁盘上性能相差不大，但是在现有的低成本的对象存储上，性能会相差一至两个数量级。而EL-BF通过在单个顺序I/O操作下读取多个block的bf数据，以显著提升效率。即使一个词跨了两个piece，也可以顺序读取两组piece进行快速检索。

False Positive Rate：通过计算假阳率公式，可以结合实际业务情况，选取适当大小的EL-BF，估算差距我们目标的性能及成本。

假设hash函数和映射函数f等概率的选择每个词到每个位置上，且任何两个词间是相互独立的，给定长度为bytes长度的ELBF，添加n个不同的hash值后，其假阳率为（详细证明过程，见原文）

近似倒排索引可以在高频词场景优化直方图查询的性能，在低频词场景下优化and查询的性能。

高频次的直方图查询通常需要较多的I/O开销和查询时延，然而在大多场景下，针对海量数据，用户可能更感兴趣的是一个近似聚合结果，而不是一个准确的结果，因此在ESTELLE中，直方图查询为渐进式查询模式。在收到直方图查询请求时，会快速响应一个近似结果，如果用户不需要准确结果，可以提前终止查询，减少查询的成本，如果用户需要准确的结果，在多轮渐进式后，会生成最终准确的结果。为了实现渐进式的直方图查询，快速返回一个准确的近似结果至关重要。

在低频词and查询场景下，如果两个低频词同时出现在一个block的不同行中，会导致大量的误判，影响查询性能。如果通过倒排索引记录所有的行号，存储和查询I/O成本都会很高。

为了解决上述的两个问题，我们设计了如下图所示的固定大小的近似倒排索引。高频词部分，用于快速返回近似聚合结果，低频词部分，用于优化低频词AND查询。接下来讲一次介绍近似倒排索引依赖的ELFD-BF、近似倒排索引的布局、工作流程，以及判断低频词是否存在目标数据的概率理论值。

Frequency Division Bloom Filter：如上图所示Frequency Division Bloom filter (简称为 ELFD-BF) 由两个EL-BF构成，大小为2^xh + 8和2^xl + 8byte。因为高频词的数量通常是明显少于低频词数量的，所以高频词的BF通常较小。

Layout of Approximate Inverted Index：ELFB-BF的高频和低频部分分别对应存在一个近似倒排索引的高频和低频部分。高频部分的BF从头部开始每qh byte会对应一个近似的倒排表，这些列表中的每一个仅存储一个2byte的count值，表示有多少个hash值映射到该近似倒排表。低频部分的bf从头部开始每ql byte对应一个近似倒排表，这些倒排表每一个存储固定长度k的行数，记录映射到该部分的词在block内的第几行出现。

Workflow：近似倒排索引的工作流程如下图所示，如果一个词存在于高频hash表中，则认为是一个高频词，且与ELFD-BF和近似倒排索引的高频部分相关联，反之亦然。我们可基于高频词通过hash运算获取偏移

应于高频bf的偏移，同时，我们定义其对应第

个高频词的倒排索引，同理我们可以定义

个低频词的倒排链表。对高频词的倒排索引每映射一次，将count加一，对低频词而言，为了固定长度，只映射前k个hash的行号。and查询时，如果两个单词对应的倒排索引取与操作，如果找到相交行，即认为存在符合条件的数据。因此K越大，误判率越低，成本越高。

Columnar-Store Format：其设计方法和实现EL-BF是一致的，每一组同一位置的倒排索引被认为属于同一个piece，进行行列转换。

Theoretically Useful Probability：以下为证明在低频词场景下，通过近似倒排索引判断一个数据库是否存在满足条件的数据的可能性 ，该理论公式，作为取k的基本依据。

假设一个数据块包括n行数据，则该数据行包括词a Wa和词b Wb的概率为Pa和Pb，这两个事件是相互独立的，此外假设每个近似倒排索引记录k个行号，使用近似倒排索引过滤调的概率为，详细证明过程见原文。

以下将介绍shard级别的查询流程及及几种查询方法的实现。

Shard外首先已经通过shardgroup进行了大颗粒度的时间裁剪，在shard内部会通过数据库的元信息的mintime/maxtime 进行细颗粒度的查询裁剪，然后通过索引（EL-BF）进行数据裁剪，最后通过实际下发请求从SFS/OBS获取目标数据，并解压、遍历及过滤数据获取最终结果。

首先使用FD-BF过滤掉肯定不包含目标词的数据快，然后通过近似倒排索引进行二次过滤流程如下：

1. 如果有一个词被映射到高频词上，即终止二级索引过滤，直接开启数据扫描

2. 如果两个词都映射在低频部分，即获取两个词的倒排表，进行优化：

• 如果交集为空，且倒排链表都没有满，则丢弃数据块，认为没有命中
• 如果交集为空，倒排链表满了，取两个链表的最大行号中的较小值，进行数据遍历
• 如果交集不为空，即遍历目标数据块

渐进式近似聚合运算分为两步，近似查询和样本矫正。在近似查询阶段，每个worker首先通过索引过滤掉不包括目标词的数据块，然后通过近似倒排索引进行计算：

1. 如果该词为高频词，则技术直接返回记录在近似倒排索引中的值，coordinator将所有的值累加计算返回；

2. 如果该词为低频，则首先评估命中的block成本。

（1）如果剩余的block较少，则可以直接过滤计算，返回目标结果

（2）如果剩余的block较多，则进如采样校准部分

样本校正需要经历多次迭代，在每一个迭代中，会采样分布的数据块进行计算预估，返回结果给客户，当经历多轮迭代后，最终会得到准确的目标数据。

Benchmark选用了 Hadoop-14TB logs 的数据中的847gb的数据， 选取ES、CK、Doris作为我们对比对象，CK使用tokenbf_v1 作为索引，ES及CK使用倒排索引作为索引；且需要compaction操作的引擎，在写入时是没有开启的，在写入完成后，查询开始前，单独完成；上述引擎均使用超高I/O云硬盘，用于缓存和数据存储；

EST-B为我们的基础仅包括EL-BF模型的日志引擎，EST为我们完整的包括近似倒排索引的日志引擎，采用1GB超高I/O云硬盘和 16GB SFS 及OBS作为底层存储。所有的压缩引擎均采用LZ4压缩算法。所有引擎开启除结果缓存以外的其他缓存。

如下图所示，左图为单核每秒的写入性能，右图为最终（其他引擎compaction）后的数据存储成本。可以看出EST的单核写入性能极强，为CK的4-5倍，ES/Doris的20倍，且存储成本较低，与CK持平，远低于倒排索引的ES及Doris。

下述表格，为不同引擎在低频词（Low）、高频词（High）、None（不存在的词）场景下不同的CPU及时延表现。可以看出，大家在高频词场景下表现较优，在低频词及不存在的词场景下，使用倒排索引的两个引擎性能更好；而EST因为OBS成本原因，在低频词场景下，优于CK，但因为网络I/O成本问题，弱于倒排索引的两个引擎。

Table1：Performance of Full-Text Query

如下表所示，在前缀查询场景下，没有找到除正则以外的前缀模糊查询命令，所以没有测试，仅比较了其他四个引擎，可以看出倒排索引在前缀查询场景表现优异，CK及EST-b在查询不存在的词时，因为需要全表扫描而超时，EST通过前缀索引可以较快的查询到目标结果。

Table2：Performance of Prefix Fuzzy Query

如下表所示为and查询的能力对比，倒排索引的查询性能明显优于其他三个引擎，CK和EST-B的能力相近，EST因为使用了近似倒排索引，提供了较好的用户体验，甚至可以获得和ES接近的查询时延，但并发能力相对较弱。

如下表所示，为各引擎在直方图场景下的聚合能力，其中EST的apx为近似计算、acrt为全量计算。由于CK的BF较重且误判率较高，整体资源及时间消耗都较大，除ES外，其他引擎都采用了向量化执行引擎，聚合计算能力都较强，Doris的聚合计算能力最强；EST因为采用了近似倒排索引，在近似场景下相较于基础的渐进式计算，降了一个数量级的响应时延。

本文我们提出了一种高性价比的云原生日志引擎，并介绍了一种低成本可插拔的适合于云原生的日志索引框架，介绍了一个近似无锁的高性能写入架构。总体而言，ESTELLE日志引擎在海量数据写入、低频查询及分析的服务场景下，可以在构建较高性价比的云原生日志服务。