Multi-Raft PlaceDriver

为什么需要pd(place driver)

在multiple-raft 里面 需要有一个中心化的机制，来协调多个raft-group的数据管理，比如parition 扩容split，merge；
数据routing等；以及一些监控和管理；ti-kv 中实现了multiple-raft,有一个 pd 的模块来管理整个集群的元素据；
他们使用的是etcd 这样一个分布式的存储，作为meta管理；etcd 由于被k8s使用，而变得越来越流行，在服务发现等元数据领域
被人大量使用，有点代替zookeep的趋势；etcd 分布式容错，也使用的raft协议，ti-kv使用etcd是自然而然的事情；

mutipl-raft在图数据中应用

目前c++生态的nebula被认为是开源里面速度最开的，各个大厂如美团等都在上面构建自己的应用；
在java 生态里面，主要是hugegraph，主要使用第三方外存，所以速度上没有nebula快，因为nebula 自己用rocksdb做kv，实现了自己的存储层，
同时做了很多的计算下推的优化，速度更快； nebula有一个meta service　的服务，来管理 raft 层的多个partition，起到的作用
类似于ti-kv 的pd；目前hugegraph 实现了single-raft 版本的 存储支持；
我学习mutple-raft的一个初衷就是想有机会使用hugegraph branch构建一个java 生态的，性能和nebula 一样的数据库，且能够支持gremlin；

我在github上search，java下的multiple-raft的项目很少；
https://github.com/PZXWHU/MultiRaft 貌似对ti-kv中的概念做了部分实现，先来学习一下他的思想；
万丈高楼平地起。

pd 主要的概念：

• 存储，我们知道pd需要管理meta data，这些meta必须是要高可用的；在这个demo项目中，使用的是rocksdb，单机作为演示；
  我们看到ti-kv，nebula都是高可用版本的，我的打算未来集成etcd管理meta；

• meta 信息。 主要包括store，region（partition）一个store 通常是一个机器，一个store 下面需要包含多个分区；
  一个region，是对一个分区的描述，比如 start-end_key; epoch, 等等；

• RegionRouteTable: region的路由表； 就是会记录所有的region信息，当用户要查询一个 key的时候，那么会通过这个表获取
  到具体操作的region；并且随着集群的变更，动态的更新table的状态。

• pdService: pd 和各个集群节点rpc通信的服务，比如和 store节点/region节点，比如heartbeat等；
  我们先看看pdservice主要的接口：

public interface PlaceDriverService {

    StoreHeartbeatResponse storeHeartbeat(StoreHeartbeatRequest request);

    RegionHeartbeatResponse regionHeartbeat(RegionHeartbeatRequest request);

    StoreInfo getStoreInfo(long storeId);

    void setStoreInfo(StoreInfo storeInfo);

    RegionInfo getRegionInfo(long regionId);

    void setRegionInfo(RegionInfo regionInfo);

    Long createRegionId();

    RegionInfo findRegionByKey(byte[] key);

    List<RegionInfo> findRegionsByKeyRange(byte[] startKey, byte[] endKey);

}

通常在HeartBeatResponse里面，会更具集群的状态下发命令给节点，比如某个分区达到了最大的size，就可能需要分裂split；
或者是集群扩容等时候，需要动态管理partition；这些都是很复杂的事情；
最后palceDriverService,通过Rpc框架发布出去，就可以和集群节点开始通信了；

集群初始化的时候，可以指定parition，store的个数，这样我们就有一个初始化的，RegionRoutable:
我们可以看看，如何实现一个基于 range-key 的routeTable；
核心的数据结构：

     private NavigableMap<byte[], Long> rangeTable = 
        new ConcurrentSkipListMap<>(ByteUtils.BYTES_LEXICO_COMPARATOR);

    public RegionInfo findRegionByKey(byte[] key) {
        if (key == null) return null;
        final Map.Entry<byte[], Long> entry = this.rangeTable.floorEntry(key);
        /*System.out.println(ByteUtils.compare(key,
                entry.getKey()));
        System.out.println(ByteUtils.bytesToInteger(key) + "  " +
                ByteUtils.bytesToInteger(entry.getKey()));*/
        return metaStorage.getRegionInfo(entry.getValue());
    }
    /**
     * Returns the list of regions covered by startKey and endKey.
     */
    public List<RegionInfo> findRegionsByKeyRange(byte[] startKey, byte[] endKey){

        final NavigableMap<byte[], Long> subRegionMap;
        if (endKey == null) {
            subRegionMap = this.rangeTable.tailMap(startKey, false);
        } else {
            subRegionMap = this.rangeTable.subMap(startKey, false, endKey, true);
        }
        List<RegionInfo> res = new ArrayList<>(subRegionMap.size() + 1);
        for(long regionId : subRegionMap.values())
            res.add(metaStorage.getRegionInfo(regionId));

        Map.Entry<byte[], Long> entry = this.rangeTable.floorEntry(startKey);
        res.add(metaStorage.getRegionInfo(entry.getValue()));

        return res;

    }

NavigableMap: 是 sortedMap的子接口；有很多个方法，可以查看一些 map-view; SkipListMAP 是sortedMap 多线程的一个
条约表的实现；他存储的是startKey-RegionId的一个映射；

我们查找 startKey对应的region的时候； floorEntry的方法；对应比 小于等Key 的最接近的 Entry；
tailMap, 为大于等于Key 的所有mapView；
navigableMap的方法可以参考： https://blog.csdn.net/cgsyck/article/details/108493266， 实现环一致hash还是很有用；