倒排索引
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:
- master node,主节点,负责接收写入并push写入到相应从节点,根据一致性策略(one, quorum, all)决定一次写入何时结束。
- data node,负责存储数据的从节点。
- 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' 这种在某种语言中过于频繁出现的单词,以及去除词性,统一变成词根形式等,这些都可以减少倒排索引的大小。