solr 路由算法

sorl支持两种路由，支持split的路由方式为compositeId方式。其背后使用的也是一致性哈希算法，每个collection在创建的时候哈希空间都是一样的：80000000~7fffffff，就是一个int的范围：2的32次方。同时，collection在创建的时候必须指定shards的个数，所有的shards均分哈希空间中素有的桶。最终，每个shard就有一个Range对象，代表该shard拥有的hash范围。

DocCollection

private final Map<String, Slice> activeSlices;

DocCollection代表一个索引，其中有一个activeSlices成员变量，表示该索引下的所有shard。

Slice

private final DocRouter.Range range;

Slice就是一个shard，其中有一个成员变量Range，代表该shard拥有的哈希空间范围

DocRouter.Range

public static class Range implements JSONWriter.Writable, Comparable<Range> {
    public int min;  // inclusive
    public int max;  // inclusive

    public Range(int min, int max) {
      assert min <= max;
      this.min = min;
      this.max = max;
    }

每个range对象代表一段连续的空间，有个最小值和最大值。

怎么确定某个文档所属的slice

HashBasedRouter

public Slice getTargetSlice(String id, SolrInputDocument sdoc, String route, SolrParams params, DocCollection collection) {
    int hash;
    if (route != null) {
      hash = sliceHash(route, sdoc, params, collection);
    } else {
      if (id == null) id = getId(sdoc, params);
      hash = sliceHash(id, sdoc, params, collection);
    }
    return hashToSlice(hash, collection);
  }

getTargetSlice方法返回每个文档所属的slice，首先确定hash值，然后调用hashToSlice方法确定slice。

protected Slice hashToSlice(int hash, DocCollection collection) {

    for (Slice slice : collection.getActiveSlices()) {
      //获取该colleciton下的每个slice的hash 范围
      Range range = slice.getRange();
       //如果文档的hash值属于该slice的range，则直接返回该slice。
      if (range != null && range.includes(hash)) return slice;
    }
    throw new SolrException(SolrException.ErrorCode.BAD_REQUEST, "No active slice servicing hash code " + Integer.toHexString(hash) + " in " + collection);
  }

Range

public boolean includes(int hash) {
      return hash >= min && hash <= max;
    }

elasticsearch 路由算法

elasticsearch 路由算法分析介绍可以看这篇文章：elasticsearch shard split 分析（五）

与elasticsearch比较

• elasticsearch直接通过hash值取模然后除以routingFactor来确定所属的shard，而solr中必须要遍历索引下的每个shard才能确定所属shard。从效率看如果有n个shard，那么solr的时间复杂度为O(n)，而elasticserach的时间复杂度为O(1)。对于shard数比较大，索引数据很多的情况下，elasticsearch会快上不少。
• elasticsearch不支持单个shard split， 而solr支持