一致性哈希

一致性哈希

一致性hash

// http://walkerdu.com/2020/01/02/consistent_hash/
/* 
 * map
 * 对于map的底层原理，是通过红黑树（一种非严格意义上的平衡二叉树）来实现的，因此map内部所有的数据都是有序的，map的查询、插入、删除操作的时间复杂度都是O(logn)。
 * 此外，map的key需要定义operator <，对于一般的数据类型已被系统实现，若是用户自定义的数据类型，则要重新定义该操作符。
 * 
 * unordered_map
 * unordered_map和map类似，都是存储的key-value的值，可以通过key快速索引到value。不同的是unordered_map不会根据key的大小进行排序，存储时是根据key的hash值判断元素是否相同，
 * 即unordered_map内部元素是无序的。unordered_map的底层是一个防冗余的哈希表（开链法避免地址冲突）。unordered_map的key需要定义hash_value函数并且重载operator ==
*/

#include <climits>
#include <string>
#include <map>
#include <vector>
#include <cstdint>
#include <sstream>
#include <iostream>
#include <functional>
#include <numeric>

template<typename T>
std::string ToString(const T & t)
{
  std::ostringstream os;
  os<<t;
  return os.str();
}

template<typename Node, typename Data, typename Hash>
class ConsistentHash
{
  public:
    ConsistentHash(uint32_t virtual_nodes = 100)
      : hash_(Hash()), virtual_nodes_(virtual_nodes)
    {}

    void AddNode(const Node & node)
    {
      std::string str_node = ToString(node);
      for(uint32_t loop_i = 0; loop_i < virtual_nodes_; ++loop_i)
      {
        std::string key = str_node + "_" + ToString(loop_i);
        uint64_t hash_value = hash_(key);
        unit_circle_.insert(std::make_pair(hash_value, node));
      }
    }

    void DelNode(const Node & node)
    {
      std::string str_node = ToString(node);
      for(uint32_t loop_i = 0; loop_i < virtual_nodes_; ++loop_i)
      {
        std::string key = str_node + "_" + ToString(loop_i);
        uint64_t hash_value = hash_(key);
        unit_circle_.erase(hash_value);
      }
    }

    const Node * GetNode(const Data & data) const
    {
      if(unit_circle_.empty())
        return nullptr;

      uint64_t hash_value = hash_(ToString(data));
      auto itr = unit_circle_.lower_bound(hash_value);
      if(itr == unit_circle_.end())
        return &unit_circle_.begin()->second;
      return &itr->second;
    }

    void PrintBalacne() const
    {
      std::map<uint64_t, uint64_t> distribute_map;

      uint64_t last_val = 0;
      for(auto & val : unit_circle_)
      {
        auto itr = unit_circle_.upper_bound(val.first);
        if(itr == unit_circle_.end())
          distribute_map[val.second] += uint64_t(-1) - val.first + unit_circle_.begin()->first;

        distribute_map[val.second] += itr->first - val.first;
      }

      for(auto & val : distribute_map)
        std::cout<<val.first<<": "<<val.second<<": "<<val.second * 1.0 / double(uint64_t(-1))<<std::endl;
    }

  private:
    std::map<uint64_t, Node> unit_circle_;
    uint32_t virtual_nodes_;
    Hash hash_;
};

// class CityHasher {
//   public:
//     int operator()(std::string t) {
//       int res;
//         for (int i=0; i<t.size(); i++) {
//           res += t[i];
//           res *= 13;
//           res %= INT_MAX;
//         }
//         return res;
//     }
// };

int main()
{
  auto hash_int = std::hash<int>();
  auto v = std::vector<int>(1000);
  iota(v.begin(),v.end(), 0);
  for (const auto& i: v) {
    std::cout << "hash int i: "<< hash_int(i) << "\n";
  }

  ConsistentHash<uint32_t, uint32_t, std::hash<std::string>> consistent_hash;
  for(uint32_t loop_i = 1; loop_i <= 5; ++loop_i)
    consistent_hash.AddNode(loop_i);

  std::cout << "********original hash\n";
  consistent_hash.PrintBalacne();

  std::cout << "********delete 3 hash\n";
  consistent_hash.DelNode(3);
  consistent_hash.PrintBalacne();
  return 0;
}