Elasticsearch 核心原理：倒排索引、压缩算法与 FST

Elasticsearch 广为人知的一面是”开箱即用的搜索引擎”，但很多人用了很久也不太清楚搜索”快”在底层是怎么做到的。这篇文章从最核心的数据结构开始，一步步还原 ES（或者说 Lucene）的底层原理。

---

倒排索引（Inverted Index）

什么是倒排索引

传统的正排索引是”文档 → 词”的映射：给定一篇文档，你能查到它包含了哪些词。倒排索引反过来——“词 → 文档”的映射：给定一个词，你能查到它出现在哪些文档的哪个位置。

举个例子，有三篇文档：

文档 ID	内容
1	城管打电话给你
2	小明被城管抓了
3	国家政策支持地摊经济发展

经过分词后，倒排索引大致长这样：

城管    → 文档1（位置1）, 文档2（位置3）
打电话  → 文档1（位置2）
小明    → 文档2（位置1）
地摊    → 文档3（位置3）

搜索”城管”时，ES 直接在倒排索引中命中文档 1 和 2，完全不用全表扫描。这就是搜索”快”的第一层秘密。

倒排索引的构成

一个完整的倒排索引包含两部分：

• Term Dictionary（词项字典）：所有不重复的词项，按字典序排列。它需要支持快速的查找（精确查找 + 前缀查找），单靠二分查找在大数据量下还不够快，所以 Lucene 用 FST 来加速。
• Posting List（倒排列表）：记录每个词项出现在哪些文档（Doc ID），以及在该文档中的位置、词频等信息。

倒排列表的核心信息：

Term → [DocID, 词频, 位置列表]

---

压缩算法：如何让倒排索引更小更快

倒排列表中的 Doc ID 通常是一串有序的整数，比如 [1, 3, 4, 7, 10]。Lucene 使用了两层压缩策略。

Frame of Reference（FOR）

FOR 的核心思路是：只存差值（Delta），不存原始值。

原始 Doc ID 列表：[73, 300, 302, 332, 343, 372]

段	基准	差值存储	最大差值 → 所需位数
[73, 300, 302, 332]	73	[0, 227, 229, 259]	259 < 2⁸ → 每值 8 位
[343, 372]	343	[0, 29]	29 < 2⁵ → 每值 5 位

每个块（Block）独立决定自己的压缩位数。这里原本 6 个整数需要 6×32=192 位，压缩后只需要 8×4 + 5×2 + 一些元数据开销，大约节省 75% 空间。

FOR 在值分布密集时压缩率极好。但如果 Doc ID 分布很稀疏（比如 [1, 1000, 2000]），差值依然很大，FOR 就没什么优势了。这时需要 RBM。

Roaring Bitmap（RBM）

RBM 把整个整数空间按 2¹⁶ = 65536 为一块做分桶：

• 高位（高 16 位）：决定属于哪个桶。
• 低位（低 16 位）：在桶内的偏移。

整数 65537 → 高位 = 1, 低位 = 1
整数 131073 → 高位 = 2, 低位 = 1

每个桶内部的存储方式根据数据密度自适应：

桶内元素数量	存储方式	说明
≤ 4096 个	Array Container	直接存 16 位整数数组，空间优先
> 4096 个	Bitmap Container	用 65536 bit 的位图标记，计算优先

这种设计让 RBM 在稀疏和密集场景下都有不错的表现，且支持高效的集合运算（交集、并集、差集），直接对 Bitmap Container 做位运算即可。

---

Term Dictionary 的加速：从 Trie 到 FST

倒排索引还需要一个”词项字典”来快速定位某个词对应的倒排列表。最简单的实现是 HashMap，但 HashMap 在内存中的开销很大——每个 key 需要存完整的字符串，而且无法支持前缀搜索（比如搜”城管”时同时提示”城管电话”）。

Trie 前缀树

Trie（前缀树）把共享前缀合并存储：

        root
       / | \
      j  a  e
      |  |  |
      k  b  s
     / \    |
    s   k   t

搜索 “jksj” 时，只需沿着 root → j → k → s → j 的路径走一遍，不需要比较完整字符串。Trie 天然支持前缀匹配，适合做搜索建议（Search-as-you-type）。

但 Trie 只能做 key 的快速查找，不能把 key 映射到一个 value。Lucene 需要的是：给定一个词项，拿到它对应的倒排列表在文件中的偏移量。这就是 FST 的用武之地。

FSM / FSA / FST

有限状态机（FSM, Finite State Machines） 是一种数学模型，包含：

• 有限个状态
• 同一时间只能处于同一个状态
• 不同状态可以互相转换
• 状态是无序的

有限状态接收机（FSA, Finite State Acceptor） 是 FSM 的一个子类：它只判断某个字符串是否属于这个集合，没有 value。相当于一个 Set。

有限状态转换机（FST, Finite State Transducer） 是 FSA 的升级版：它不仅接受字符串，还能输出对应的 value。相当于一个 Map。

FST 的核心价值在于：

• 查询速度比 HashMap 稍慢，但内存消耗远低于 HashMap —— 因为共享了前缀和后缀路径。
• Lucene 大量使用 FST：倒排索引的 Term Dictionary、同义词词典、搜索关键字建议（Suggest）。

示例：插入 jksj→10, jksjtech→5, jkb→2：

     root
      |
      j
      |
      k
     / \
    s   b/2
    |   
    j/10──t──e──c──h/5

注意 jks 前缀被共享了，jksj 和 jksjtech 也共享了 jks 直到 j 之前的部分。FST 不仅能共享前缀（如 Trie），还能共享后缀，因此在内存效率上远远优于 HashMap。

---

集群与分片

理解完底层数据结构，再来看 ES 在分布式层面是如何组织数据的。

节点角色

一个 ES 集群中的节点可以承担不同角色：

角色	说明
master / candidate	主/候选节点，负责集群管理操作
data	数据节点，存储分片
data_hot	热节点，活跃数据的写入和查询
data_warm	温节点，索引不再定期更新
data_cold	冷节点，只读数据
ingest	预处理节点，类似 Logstash 的 Filter
ml	机器学习节点
voting_only	仅投票节点，参与选举但不做候选主节点

分片（Shard）

ES 的核心抽象：一个索引包含一个或多个分片，每个分片就是一个 Lucene 实例，拥有完整的创建索引和处理请求的能力。

关键规则：

• 7.0 之后默认一个索引一个主分片（之前默认 5 个）。
• 主分片数量一旦确定不可修改（因为分片路由算法基于 hash(id) % primary_count）。
• 副本分片数量可以在索引创建后修改。
• 一个 doc 不可能同时存在于多个主分片中，但可以同时存在于多个副本中。
• 每个主分片和其副本分片不能同时存在于同一个节点上（否则节点挂了数据就丢了）。

ES 会自动在节点间做分片均衡，保证负载合理。

健康值状态

状态	含义
Green	所有 Primary 和 Replica 均为 active
Yellow	至少一个 Replica 不可用，但所有 Primary 可用，数据完整
Red	至少一个 Primary 不可用，数据不完整

分片路由

写入时，ES 计算 routing = hash(doc_id) % number_of_primary_shards，决定该文档写入哪个分片。默认 routing 就是文档 ID，也可以自定义 routing 值来实现特定维度的数据聚合。

---

Docker 搭建测试环境

# 启动 ES
docker run -p 9200:9200 -p 9300:9300 --name elasticsearch \
  -e "discovery.type=single-node" \
  -e "cluster.name=elasticsearch" \
  -e "ES_JAVA_OPTS=-Xms512m -Xmx1024m" \
  -e "ingest.geoip.downloader.enabled=false" \
  -v /path/to/es/data:/usr/share/elasticsearch/data \
  -d elasticsearch:7.17.9

# 启动 Kibana
docker run --name kibana --link=elasticsearch -p 5601:5601 \
  -d kibana:7.17.9

# 启动 ES-Head 可视化插件
docker run -d --name=elasticsearch-head -p 9100:9100 \
  mobz/elasticsearch-head:5-alpine

---

总结

从倒排索引到压缩算法再到 FST，ES 底层的每个设计选择都在回答一个问题：在 PB 级数据下，如何在毫秒级完成全文搜索？

• FOR 用差值压缩密集的 Doc ID 列表。
• RBM 用分桶 + 自适应存储处理稀疏场景。
• FST 用有限状态转换机压缩 Term Dictionary，兼顾速度和内存。
• 分片 让这些数据结构可以水平扩展到上百台机器。

理解这些底层机制，不仅能帮你更好地使用 ES（比如为什么分片数不能改、为什么聚合在某些字段上更慢），也为排查性能问题提供了理论依据。