架构师训练营第 1 期第 5 周作业

#include <algorithm>#include <functional>#include <list>#include <map>#include <string>
#ifndef __CONSISTENT_HASH_H__#define __CONSISTENT_HASH_H__
template <typename T, typename Hash,          typename Alloc = std::allocator<std::pair<const typename Hash::result_type, T>>>class consistent_hash_map { public:  typedef typename Hash::result_type size_type;  typedef std::map<size_type, T, std::less<size_type>, Alloc> map_type;  typedef typename map_type::value_type value_type;  typedef value_type& reference;  typedef const value_type& const_reference;  typedef typename map_type::iterator iterator;  typedef typename map_type::reverse_iterator reverse_iterator;  typedef Alloc allocator_type;
  consistent_hash_map() {}  ~consistent_hash_map() {}
  std::size_t size() const { return nodes_.size(); }
  bool empty() const { return nodes_.empty(); }
  std::pair<iterator, bool> insert(const T& node) {    size_type hash = hasher_(node);    return nodes_.insert(value_type(hash, node));  }
  void erase(iterator it) { nodes_.erase(it); }
  std::size_t erase(const T& node) {    size_type hash = hasher_(node);    return nodes_.erase(hash);  }
  iterator find(size_type hash) {    if (nodes_.empty()) {      return nodes_.end();    }
    iterator it = nodes_.lower_bound(hash);
    if (it == nodes_.end()) {      it = nodes_.begin();    }
    return it;  }
  iterator begin() { return nodes_.begin(); }  iterator end() { return nodes_.end(); }  reverse_iterator rbegin() { return nodes_.rbegin(); }  reverse_iterator rend() { return nodes_.rend(); }
 private:  Hash hasher_;  map_type nodes_;};
#endif

#include <stdint.h>#include <boost/crc.hpp>#include <boost/format.hpp>#include <boost/functional/hash.hpp>#include <iostream>#include <string>
#include "consistent_hash_map.hpp"
constexpr int NODE_COUNT = 100;constexpr int VIRTUAL_NODE_COUNT = 1000000;
const char* nodes[] = {"192.168.1.100", "192.168.1.101", "192.168.1.102", "192.168.1.103",                       "192.168.1.104", "192.168.1.105", "192.168.1.106", "192.168.1.107",                       "192.168.1.108", "192.168.1.109"};
struct vnode_t {  vnode_t() {}  vnode_t(std::size_t n, std::size_t v) : node_id(n), vnode_id(v) {}
  std::string to_str() const {    // return boost::str(boost::format("%1%-%2%") % nodes[node_id] % vnode_id);    return "test";  }
  std::size_t node_id;  std::size_t vnode_id;};
struct crc32_hasher {  uint32_t operator()(const vnode_t& node) {    boost::crc_32_type ret;    std::string vnode = node.to_str();    // std::cout << "vnode:" << vnode << std::endl;    ret.process_bytes(vnode.c_str(), vnode.size());    return ret.checksum();  }  typedef uint32_t result_type;};
int main(int argc, char const* argv[]) {  typedef consistent_hash_map<vnode_t, crc32_hasher> consistent_hash_t;  consistent_hash_t consistent_hash_;
  for (std::size_t i = 0; i < NODE_COUNT; ++i) {    for (std::size_t j = 0; j < VIRTUAL_NODE_COUNT; j++) {      consistent_hash_.insert(vnode_t(i, j));    }  }
  {    // std::cout << "=========================================================" << std::endl;    std::size_t sums[] = {0, 0, 0, 0, 0};    consistent_hash_t::iterator i = consistent_hash_.begin();    consistent_hash_t::reverse_iterator j = consistent_hash_.rbegin();    std::size_t n = i->first + UINT32_MAX - j->first;    // std::cout << boost::format("vnode:%1%,hash:%2%,contains:%3%") % i->second.to_str() % i->first %    //                  n    //           << std::endl;    sums[i->second.node_id] += n;
    uint32_t priv = i->first;    uint32_t cur;    consistent_hash_t::iterator end = consistent_hash_.end();    while (++i != end) {      cur = i->first;      n = cur - priv;      // std::cout << boost::format("vnode:%1%,hash:%2%,contains:%3%") % i->second.to_str() % cur % n                // << std::endl;      sums[i->second.node_id] += n;      priv = cur;    }
    // for (std::size_t i = 0; i < NODE_COUNT; ++i) {    //   std::cout << boost::format("node:%1% contains:%2%") % nodes[i] % sums[i] << std::endl;    // }  }
  {    consistent_hash_t::iterator it;    it = consistent_hash_.find(290235110);    // std::cout << boost::format("node:%1%,vnode:%2%,hash:%3%") % nodes[it->second.node_id] %    //                  it->second.vnode_id % it->first    //           << std::endl;  }
  return 0;}