海量数据优化查询的套路之——ordinals

Using Ordinal in Search

Posted by S.L on May 27, 2020

对于海量数据查询的场景,往往对耗时要求有一定的追求,除了默认的索引之外还有什么方式可以提高检索速度?

本文主要对工作中用到的两种海量数据存储和查询工具:clickhouseelastic search在查询中遇到的一类提高检索速度的方式进行总结 发现,二者均使用了ordinal方式对查询进行了优化。

Ordinals

对于编程语言来说,枚举类型一般都会对应一个ordinal()方法,它返回对应枚举类型在枚举列表中的顺序,比如Java。即不管具体的 枚举名是一个什么样的字符串,在底层会根据它声明的顺序给它从0到N匹配一个唯一的数字,这个数字在一个枚举类型中是唯一的。

我们知道存储数字在数据量比较小的情况下比存储字符串本身要高效的多,无论从检索速度还是查询匹配。

ES聚合的优化

线上的消息搜索场景有一个根据消息内容查询全部用户会话中匹配的会话维度的前N条符合条件的消息,使用到了聚合搜索。

在项目初期查询速度很快,但是随着业务的上线时间半年后,发现这个查询搜索速度已经上升到秒级别,并且和符合条件的文档数没有关系, 即使符合条件的文档很少,还是需要等待很久才能返回数据。

经过初步分析觉得应该是索引数据太大导致的:由于建立索引时需要对消息内容进行分词(还包括拼音的分词),所以最终索引的数据量很大, 几个月的时间就已经达到了6G个文档,1T的磁盘空间。

Global Ordinals

ES为了减少内存使用,会将字符串排序后进行编号,形成一张映射表,然后在每条数据中使用相应字符串的序号来表示。通过这样的设计, 可以显著降低在检索时对内存的占用。这里的映射表,或者说映射表中的序号,就是Ordinals。

当我们对某个keyword字段做Terms聚合查询时,请求会透过Coordinate Node分散到Shard所在的Node中执行,而针对每个Shard的查询又会分散到多个Segment中去执行。 上述的Ordinals是per-segment ordinals,是针对每个Segment里面的数据而言, 意味着同一个字符串在不同的per-segment ordinals中可能对应的序号是不同的。

所以又有一个Global Ordinals概念,即ES会在Shard层面统一维护一个全局的Shard维度的Ordinals映射表,在底层查询到具体的ordinals 后会在返回客户端结果之前对数据进行转换回字符串。

构建时机

构建Global Ordinals的目的是为了减少内存使用、加快聚合统计,在大多数情况下其表现出来的性能都非常好。之所以会影响到查询性能,与其构建时机有关:

  • 由于Global Ordinals是Shard级别的,因此当一个Shard的Segment发生变动时就需要重新构建Global Ordinals,比如有新数据写入导致产生新的Segment、Segment Merge等情况。当然,如果Segment没有变动,那么构建一次后就可以一直利用缓存了(适用于历史数据)。
  • 默认情况下,Global Ordinals是在收到聚合查询请求并且该查询会命中相关字段时构建,而构建动作是在查询最开始做的,即在Filter之前

这样的构建方式,在遇到某个字段的值种类很多(即下文所述的High Cardinality问题)时会变的非常慢,会严重影响聚合查询速度,即使Filter出来的document 很少也需要花费很久,也就是上文笔者遇到的问题,即在High Cardinality情况下,构建Global Ordinals非常慢。比如我们的消息索引,因为消息本身都是随机的 导致了很多性能问题:

  • High Cardinality会导致构建Global Ordinals过程变慢,从而导致聚合查询变慢内存使用过高
  • High Cardinality会导致压缩比率降低,从而导致存储空间增加,特别是像hash值这样完全随机的字符串。
  • 对High Cardinality字段执行Cardinality聚合查询时,会受到精度控制从而导致结果不精确。

ClickHouse

无独有偶,除了ES在实现快速查询时的优化使用了Ordinal之外,Clickhouse也有采用。

我们目前线上的监控采用Grafana+Clickhouse来实现,对于列式数据库在海量数据聚合计算中的优势不用多说,性能非常优秀,但是还是存在磁盘空间占用 过大以及查询速度存在优化空间的问题,如某些字段为string类型的,没有非常高的Cardinality时,对存储空间是一种极大的浪费,如一个字段 包括了数量有限的字符串,即Low Cardinality。

LowCardinality

这是一种新增的数据类型,用于替换某些场景下的string类型,可以在查询、聚合、过滤等场景有非常明显的性能优势,同时还可以降低磁盘的存储空间。

LowCardinality 是字符串字典编码实现的,其中字符串被编码为 Position(positions,可以理解为索引),并通过 position-to-string 的映射引用字典。 当源字符串很长且去重后值的数量不是很大时,它的效果最佳。ClickHouse 没有硬性限制具体去重后值的大小,如果去重后值的数量低于 1000 万,效果通常会很好。 对于具有多个 partition 和 part 的 ClickHouse 大表,如果在 part 级别保留 1000 万限制,则去重后值的总数甚至可能更高。

LowCardinality 支持 String、Number、Date、DateTime、Nullable数据类型。

在内部,ClickHouse 创建一个或多个文件以存储 LowCardinality 字典数据。如果所有 LowCardinality 列都符合 8192 个不同的值,那么每个表可以是一个单独的文件,如果去重值的数量更多,则每个 LowCardinality 列就使用一个文件。

ClickHouse LowCardinality 优化不仅限于存储,它还使用字典 position 进行过滤、分组和加速某些查询功能(例如 length())等。 这就是为什么我们在 Query 1 中看到的改进要比纯粹从存储效率提升的效果更大的原因。在分布式查询中,ClickHouse 还将尝试在大多数查询处理中对词典 position 进行操作。 

References

本文首次发布于 S.L’s Blog, 作者 @stuartlau , 转载请保留原文链接.