Elasticsearch：数据重分配

之前看elasticsearch按照_routing的hash对文档进行分片的时候，竟然都没有注意到elasticsearch是先做虚拟分片，再映射到实体分片……

routing_factor = num_routing_shards / num_primary_shards
shard_num = (hash(_routing) % num_routing_shards) / routing_factor

num_routing_shards就是虚拟分片的个数。

为什么要这么搞？因为分布式系统涉及到节点变动时数据重新分配的问题。

1. 数据重分配
   1. rehash
   2. 一致性哈希 Consistent Hashing
   3. HashMap：一分为二
   4. elasticsearch：虚拟hashmap
      1. 为什么
   5. 手动分配
   6. 总结
2. 索引拆分：index split
3. 结论

数据重分配

大前提：分布式系统，每一个服务节点都只能有部分数据。当节点增加或减少的时候，需要重新分配数据。如果分配数据到节点只是单纯地使用了hash算法，那么就需要rehash。

rehash

方案最简单，但是每当增减一个节点，几乎所有的key都要rehash到不同的节点，对服务来说变动太大，要移动的数据太多。

一致性哈希 Consistent Hashing

• https://bbs.huaweicloud.com/blogs/333158

两种hash：

1. 节点做hash（比如用自己的ip做hash），找到自己在环上的位置；
2. 数据做hash，找到自己在环上的位置；

数据未必正好落在节点上，所以数据在环上顺时针走的下一个节点，就是目标节点。

本质上是在哈希环上新增一个节点之后，只去分担下一个后继节点的部分key，所以完全不影响其他节点上的key，要移动的数据范围很小。删除节点的时候也是把数据给到下一个后继节点。

但是如果节点本身比较少，节点所在的位置不均衡，会导致数据分布不均匀，所以一致性哈希还要使用大量的虚拟节点，把数据切分的比较细，再把多个虚拟节点映射到一个物理节点上，就均匀了。如果新增一个物理节点，就会相应增加一些虚拟节点，抢过来一些其他虚拟节点的数据，可以理解为是均匀抢的其他节点。如果下掉一个物理节点，就下掉它对应的虚拟节点，把这些虚拟节点的数据都分配给环上的下一个虚拟节点，对其他物理机来说，基本也是均匀增加数据。

不过es没有用一致性哈希~

HashMap：一分为二

在JDK的HashMap里，扩容是这么玩的：每次容量扩大一倍，就可以做到把一个桶只拆为对应的两个桶。

一分为二的rehash相比于普通rehash，数据挪动起来更快，只需要挪一半。比如一开始有两个桶，只看hash值的最后一个bit就行，二分四后，每个桶里的数据看hash值的倒数第二个bit是0还是1就知道是走（1）还是留了（0）了。因此一分为二的hash可以在一开始就把hash值记录下来，后面根本不需要再计算一遍了。

相比于无脑使用rehash重新分配所有数据，HashMap的这种一拆二rehash还是要快不少。但是它也不适用于大规模数据集：

• 适用于数据量不多的情况，因为要挪1/2的数据；
• 最好数据在内存里，挪起来比较快；

elasticsearch：虚拟hashmap

elasticsearch分片拆分的原理跟HashMap几乎一样。当elasticsearch的分片太大的时候，可以增加分片数，使用split API将大分片拆分为体积较小的分片。

再看elasticsearch的_routing，虽然是hash取模分片，但在按照实际分片数取模之前，先按照虚拟分片数取模：

routing_factor = num_routing_shards / num_primary_shards
shard_num = (hash(_routing) % num_routing_shards) / routing_factor

虚拟分片数是通过index.number_of_routing_shards设置的，默认值是主分片数的2^n，同时不超过1024。比如primary shard=30，虚拟分片数就是30x2^5=960，此时每个分片上有2^5个虚拟分片。

拆分索引的时候就可以按照主分片的2^n拆分，比如一拆二就是设置新索引的主分片数为30x2=60，此时每个分片上有2^4个虚拟分片，少了一半。

为什么

问题一：为什么elasticsearch不采用普通的rehash？

rehash代价太大，挪动数据太多，对key value系统如此，对es这种既不是kv，又适用文件系统的服务就更不用说了。

问题二：为什么不采用一致性哈希？

虽然只需要挪n分之一的数据，es仍然认为代价太大。因为相比简单的key value系统，es的每个文档都要在创建时建立索引，显然快不起来。

es先是肯定了一致性哈希在key value系统上的优势：

The most common way that key-value stores do this efficiently is by using consistent hashing. Consistent hashing only requires 1/N-th of the keys to be relocated when growing the number of shards from N to N+1.

然后阐明了它不适合es：

However Elasticsearch’s unit of storage, shards, are Lucene indices. Because of their search-oriented data structure, taking a significant portion of a Lucene index, be it only 5% of documents, deleting them and indexing them on another shard typically comes with a much higher cost than with a key-value store.

问题三：为什么不使用和hashmap一样的一分二的算法？为什么要提前预设好虚拟分片个数？

道理同上，hashmap一分二依然要给一半的数据rehash，要给一半的数据重新建立索引，太慢了。

那么设置好虚拟分片之后呢？一分二不一样要挪数据吗？

不需要，因为es可以直接给新索引创建硬链接指向之前要挪过来的那些虚拟分片的数据，同时老索引标记这些虚拟分片的数据不再属于该分片的数据即可。比重新索引一个个文档简单。

The split is done efficiently by hard-linking the data in the source primary shard into multiple primary shards in the new index, then running a fast Lucene Delete-By-Query to mark documents which should belong to a different shard as deleted. These deleted documents will be physically removed over time by the background merge process.

• https://www.elastic.co/cn/blog/elasticsearch-6-1-0-released

如果系统不支持硬链接，直接整块把虚拟索引拷过来也是可以的，一定比重新索引分片上的全部文档要高效得多：

If the file system doesn’t support hard-linking, then all segments are copied into the new index, which is a much more time consuming process.

不如把es的这一虚拟分片的处理方式称之为虚拟hashmap，它同时借鉴了一致性哈希（虚拟分片）和hashmap（一分二）：

• 优点：
  • 对于文件系统来说，可以高效一分二；
• 缺点：
  • 但是不能像hashmap一样无限拆分，虚拟分片个数就是它的上限；

Why does elasticsearch still use simple routing value using modulo?

• https://stackoverflow.com/questions/46236029/why-does-elasticsearch-still-use-simple-routing-value-using-modulo

手动分配

redis cluster存放数据的基本单位是slot（很像一致性哈希的虚拟节点，或者elasticsearch的虚拟分片）。slot数目是固定的，以slot为单位手动指定存放slot的node。需要重新分配的时候直接把整个slot挪过去就行了。

Redis - cluster的slot部分。

redis cluster直接挪一整个slot，其实也是避免了rehash。但是需要记住每一个slot都在哪个地方。

redis的这个挪动方式挺像elasticsearch的，slot其实就是虚拟分片：

• 都有上限：elasticsearch是最多不超过2^10个虚拟分片，redis是固定2^14个slot；
  • 只不过redis的slot直接暴露给用户了，elasticsearch没有
• 挪动：二者类似，都是以整个虚拟节点/slot为单位整个挪过去，都避免了rehash
  • 不过elasticsearch用的是文件，使用了硬链接，redis是内存，就是直接copy；

灵活性上二者不同：elasticsearch只能一分二分下去，redis可以随便挪。缺点就是整个redis集群要记住哪个slot在哪个节点上。

总结

• 普通rehash：最简单，最大的数据重分配代价。适用于数据量很小的情况；
• 一致性hash：比较麻烦，但是数据重分配代价小。适用于大量数据的分布式系统；
• HashMap：一分为二的rehash，相对简单，同时只需要移动一半的数据；
• elasticsearch：虚拟hashmap，和文件系统相适应，但是不能像hashmap一样无限拆分下去；
• 手动分配：redis直接挪一整个slot，其实也是避免了rehash。好处是可以随便挪，灵活性很强，但是redis集群需要记住每一个slot都在哪个节点上；

索引拆分：index split

A split operation:

1. Creates a new target index with the same definition as the source index, but with a larger number of primary shards.
2. Hard-links segments from the source index into the target index. (If the file system doesn’t support hard-linking, then all segments are copied into the new index, which is a much more time consuming process.)
3. Hashes all documents again, after low level files are created, to delete documents that belong to a different shard.
4. Recovers the target index as though it were a closed index which had just been re-opened.

首先设置索引禁止写入：

PUT stored_kol_split_lhb/_settings
{
  "settings": {
    "index.blocks.write": true
  }
}

由于原索引主分片为2，这里新索引设置为它的2^5=32倍，64片，所以相当于原来的索引一拆32：

POST /stored_kol_split_lhb/_split/stored_kol_split_after_lhb
{
  "settings": {
    "index.number_of_shards": 64
  }
}

新的索引把禁止写入的设置也同步了过来，所以搞定后别忘了取消禁止写入：

PUT stored_kol_split_after_lhb/_settings
{
  "settings": {
    "index.blocks.write": false
  }
}

分片增加之后，虽然文档数没变，但占用空间变大了不少。

如果有某些分片没有成功分配，可以使用diagnose api查查原因：

GET _cluster/allocation/explain
{
  "index": "stored_kol_split_after_lhb", 
  "shard": 4, 
  "primary": true 
}

虽然split api需要先设置索引禁止写入，看起来还不如reindex（新建一个索引重新设置主分片数），但是根据上面的介绍，在数据量比较大的时候，使用splite api直接copy索引的segment文件并删除一半数据，一定比reindex快非常多！

split index api文档还提到了一句话：如果data是append only，就没必要拆分了。新的数据写到新索引，老索引和新索引设置同样的alias，就可以一起查了。在查询速度表现上和直接查一个主分片数叠加的索引没什么区别：

In the case of append-only data, it is possible to get more flexibility by creating a new index and pushing new data to it, while adding an alias that covers both the old and the new index for read operations. Assuming that the old and new indices have respectively M and N shards, this has no overhead compared to searching an index that would have M+N shards.

结论

又到了那句真理：没有永远的真理，只有合适不合适。大家都基于自己的系统特性，选择了很多不同的hash方案。知识越辩越明，对比起来学习真的是太爽了。