记录一些关于distributed hash table(DHT)的感想和tips
service register and descovery id
比如以db的server为例，在client决定需要把request发送到哪个server上时，首先要对server进行标记，which one is which。因为许多dht算法都是要通过id标记来进行的，这里列出来找到的几种方案。之后还要有id到ip的映射，比如client明确说要把请求发送给server with id = 1 这个时候要能提供一个index的service，将id index 成ip然后让client获取到。
MPI+parallel file system
MPI的程序可以通过MPI_Comm_rank (MPI_COMM_WORLD, &rank);来得到当前process所在的id。之后通过shared file system来管理id到ip的mapping，比如以id名称为目录以ip名称为文件名称，或者采用其他的自定义文件内容的方式，总之因为parallel file system可以被所有的client 和 server access，get ip的操作就变得简单了许多
third party service
在cloud环境中就需要一个单独的server来管理ip的注册和发现(所谓的服务注册和服务发现)。主要的方法就是生成id，然后将这个id记录在一个global access的third party 服务中，具体参考这个，以及这个，这个<如何缓解由于centrlized server引发的单点问题>。
sharding, horizental partition, vertical partition
这个youtube video讲sharding比较有意思。用简单的话说就是把所有的data分配在不同的server上(根据某一个key)，key可以映射成某个range的数字，比如server1负责处理key=1到key=99的case，server2负责处理key=100到199的case， 然后query的时候每个client请求不同的server。
consistent hash
这个 youtube video了解概念比较快。可以看到的一点是这里比较灵活的是不断有server adding或者move out时候，consistent hash 比较有用。（adding or removing servers）要是纯粹的load balancing的问题，使用之前的partition或者定期进行重新分配<比如经过一段时间的存取删除操作，有的server上的data比较多，有的server上的data比较少，这时候可以采用redistribution进行重新分配>，问题就可以解决。还有一些比较有名的dht协议，这里不一一介绍，比如chord，比较近的Kademlia，具体可以参考 wiki dht。
fault tolerance
fault tolerance主要解决的问题就是有一个server突然down掉了或者网络环境不稳定的时候有的服务连不上该怎么弄。主要的策略就是主从备份，server会分不同的role，比较popular的protocol有raft以及paxsos协议。这里就不具体展开，这一部分需要专门的一篇来介绍。stright forward的master slave策略可以参考redis的实现。
real example
redis
- The ability to automatically split your dataset among multiple nodes:
redis doesn’t use the consistance hash, it use data sharding (every key is conceptually part of what we call an hash slot) 这里的策略也比较straight forward，就是horizontal sharding的直接应用
add move server? how to do this in redis <using redirect?> reshard data??
(Redirection and resharding in https://redis.io/topics/cluster-spec)the client could cache the new key position <client end 的map 在不断动态给更新>
这种支持online add and delete server的操作需要很多设计考量，但是实际场景中可能并不需要动态地move in 以及 move out。在prototype的产品中，如果focuse的点不在db上，这里就可以略过。
- The ability to continue operations when a subset of the nodes are experiencing failures or are unable to communicate with the rest of the cluster.
use master slave patterns between different nodes, there are communications between different nodes.
感觉越是infra的东西就越是简单可靠能用起来就就好，之前有一些dynamic redistribution或者是machine learning 去fetch data，或者是很花哨的dht（总能找到更简单的strategy来实现同样的功能），这些应该是建立在本身稳定的infra的再上一层的layer而不是去代替原本的方法，实际上是有点不切实际，越是infra的越是要实现原理简单，然后合理与硬件层结合，这一块使用ML总感觉是不那么fit，大多是原理层面的事情，或者是strategy或者是设计层面的事情。
比如rebalcance，reshard这种操作，原理上几句话就能说清楚，原理上已经很清楚的方法，但是实现起来并不容易，所以是偏向industry的点而不是很适合paper的点，这些就不适合弄paper，因为不是在做一个avalibale的product，适合发paper的点是以前没有的新的abstraction，总之要把二者区分开，要考虑自己做事的时候是处在哪个context下。
geoindex
之前还遇到过一个项目，为了支持很多的数据存储，在index的时候就采用round roubin的方式，也就是说client可能把数据放在任意一个点上（均匀地），之后再维护一个dht（使用的是space filling curve来mapping data and index position），每次存数据之后都update dht。这种模式在read data的时候dht还是比较费时间（特别是节点上的数据变多的时候，第二级和第三级的Index分别是name 和timespace），因为一次read操作需要多次request才能确定实际的data所在的位置。好处就是比较好的load balancing或者说是绝对的load balancin，并且能根据地理位置进行索引[采用这种index的主要原因]，因为采用的是round roubin的方式，所以数据肯定是均匀地分配在所有的节点上。但是以性能为代价去做这种load balancing个人感觉并不是一个合适的选择[如果不是因为地理信息的原因使用space filling curve 建立索引的话]，因为Load balancing总可以通过选择合适的hash function来进行尽量匀称的分布，即使name一样，timestep也总是有可能不一样啊。总可以构建出不一样的key然后比较均匀地hash到不同的节点上。或者使用多次hash，比如name或者timestep先hash一次，这个时候可能hash到某一些server，然后在geolocation再hash一次。总之不管怎样，hash之后的结果是一个server id 而hash之前的信息可能是string或者是地理位置的坐标。但是scintific的data又和geo db的data不同，scientifc是一个data range作为一个data point，粒度更大而geo db是一个坐标的位置就是一个point，粒度更小的point data，需要的算法更复杂一些，具体可以参考geohash的wiki，如何通过坐标生成一个id。
其他的一些geolocation的index技术比如参考mongodb的geoindex的实现。
比较trick的case是，query某个地理范围的数据时候，这个地理范围与实际的data存储范围不一一对应，就是实际上取回来的数据总是多一些的。或者数据存在两个地方需要拿回来拼接等等，这些问题比较复杂。
kd-tree Rtree octree 也是一些常用的geoindex的数据结构，比如参考这个
还有一些相关的index技术 比如 fastbit 或者 bloom-filter indexing 在paper中经常看到
reference
redis cluster documentation
https://redis.io/topics/cluster-tutorial
https://redis.io/topics/cluster-spec
mogodb geoindex
https://stackoverflow.com/questions/4576892/how-does-a-geospatial-index-work
