倒排索引

ES最主要的数据结构是倒排索引，即某些信息出现在哪些记录中，之后问题就转化成了字符串匹配问题。

ES和RDS最大的区别就是ES不支持更新，更没有事务一说，就只有插入和删除以及查询操作。

ES会把一个search转化成一个树结构的query，每个叶子结点对应一个Lucene的查询请求，相应的返回结果会被加上cache。

https://www.elastic.co/cn/blog/found-elasticsearch-from-the-bottom-up

搜索过程

用户输入查询语句。
对查询语句经过语法分析和语言分析得到一系列词。
通过语法分析得到一个查询树。
通过索引存储将索引读入到内存。
利用查询树搜索索引，从而得到每个词的文档链表（应该是 bitmap？），对文档链表进行交、差，并得到结果文档。
将搜索到的结果文档对查询的相关性进行排序。
返回查询结果给用户。

写入过程

https://www.elastic.co/guide/cn/elasticsearch/guide/current/inside-a-shard.html

写入相关的过程非常复杂，类似LSM tree：

一个写入来了就在内存追加一个新的倒排索引（和其他相关操作，总而言之就是更新状态），并且将其追加到translog，此时这个记录还无法被搜索到。
refresh：每隔1s buffer中的数据会被写入到文件系统缓存，虽然没有被写入磁盘，但这个缓存文件已经像正常文件一样可以被打开和读取了，也就是说一个记录从写入ES到可以被搜索到，默认需要1s的时间间隔。
flush：当translog的大小超过一个阈值，或者距离上次flush已过30分钟后，把文件系统缓存中的translog合并成一个全量提交（即“段”）。
段在后台不断的被合并，两个大小相似的段会被合并成一个大段，之后便被删除，此时被删除的记录才会真正被删除，之前只是在 .del 文件里被标记为删除

默认translog每5秒被fsync刷新到磁盘，或者在每次写请求完车之后执行，保证操作不会丢失。

结构

ES从最顶层往下的结构是：

index
node：
1. master node，主节点，负责接收写入并push写入到相应从节点，根据一致性策略（one, quorum, all）决定一次写入何时结束。
2. data node，负责存储数据的从节点。
3. none node，负责收发、解析、路由外界请求。
shard，一个index的不同replicas ~，分布在同一个cluster下不同的zone里面for availability；~ 每个shard各自对应着一个Lucene index；水平切分就发生在这儿，hash(routing key) % number of shards决定了一个index请求应该存在哪个shard上，routing key的默认值是ID，也可以我们自己指定。

另外，shard下不同节点备份的逻辑是基于translog来的，即不同node之间互相同步translog。关于translog和更多的容灾备份，请见

https://www.elastic.co/cn/blog/found-elasticsearch-top-down

搜索优化

FST，有限状态机，一个搜索词对应的倒排索引关键词由FST推导出（这个论断应该是错的，错词怎么推导呢？网络上说有BK tree，还是看ES的实现更靠谱）。然后我们再由这些被推导出的关键词，去计算各个文档的得分，以及对应文档。
TF-IDF：term X在文档Y中出现的次数 * log(总文档数 / 所有包含X的文档数)，这是ES中的相关性权重。 https://www.slideshare.net/rahuldausa/introduction-to-elasticsearch-with-basics-of-lucene
tag（或其他一些我不知道的搜索操作）等filter操作，可以很容易地被缓存在一个bitmap里，几个filter操作其实就是几个bitmap之间的操作，非常快速。
Query then fetch，client node根据一个查询去不同node上请求document id和相关的分数，之后client node负责聚合，得到在结果中的document id，并去其他node中取回相关的document。
- 一个例子：ES fetch top k，client node去不同node上请求各自的top k，各个data node根据自己的数据情况计算出自己的top k返回，之后client进行merge。
- 一个问题是，各个data node计算top k只考虑了自己的数据，一些属性的计算是需要考虑全局数据的，此时top k的计算就是不精确的，这时可以考虑去各个节点拿回k * 10个数据，这样不准确的概率会变小。又或者考虑DFS的query then fetch。
DFS query then fetch
- client node先去各个节点上请求计算TF-IDF需要的数据，汇成一个总数据，把这个数据发给各个节点，让它们根据全局的数据进行打分，并做好相关的filter和其他计算，之后操作和query then fetch一样。

一些分词器会去掉 stop word，即 'the', 'a', 'this' 这种在某种语言中过于频繁出现的单词，以及去除词性，统一变成词根形式等，这些都可以减少倒排索引的大小。