proxygen::RendezvousHash Class Reference

#include <RendezvousHash.h>

Inheritance diagram for proxygen::RendezvousHash:

Public Member Functions
double	getMaxErrorRate () const override
void	build (std::vector< std::pair< std::string, uint64_t >> &) override
size_t	get (const uint64_t key, const size_t rank=0) const override
std::vector< size_t >	selectNUnweighted (const uint64_t key, const size_t rank) const
Public Member Functions inherited from proxygen::ConsistentHash
virtual	~ConsistentHash ()
virtual void	build (std::vector< std::pair< std::string, uint64_t > > &)=0

Private Member Functions
size_t	getNthByWeightedHash (const uint64_t key, const size_t modRank, std::vector< size_t > *returnRankIds) const
uint64_t	computeHash (const char *data, size_t len) const
uint64_t	computeHash (uint64_t i) const

Private Attributes
std::vector< std::pair< uint64_t, uint64_t > >	weights_

Detailed Description

Definition at line 24 of file RendezvousHash.h.

Member Function Documentation

void proxygen::RendezvousHash::build ( std::vector< std::pair< std::string, uint64_t >> &  )

override

Definition at line 20 of file RendezvousHash.cpp.

References computeHash(), string, uint64_t, and weights_.

Referenced by TEST().

                                                         {
  for (auto it = nodes.begin(); it != nodes.end(); ++it) {
    std::string key = it->first;
    uint64_t weight = it->second;
    weights_.emplace_back(computeHash(key.c_str(), key.size()), weight);
  }
}

uint64_t proxygen::RendezvousHash::computeHash ( const char *  data, size_t  len  ) const

private

Definition at line 214 of file RendezvousHash.cpp.

References folly::hash::fnv64_buf().

Referenced by build(), and getNthByWeightedHash().

                                                                       {
  return folly::hash::fnv64_buf(data, len);
}

uint64_t proxygen::RendezvousHash::computeHash ( uint64_t  i ) const

private

Definition at line 218 of file RendezvousHash.cpp.

References folly::hash::twang_mix64().

                                                     {
  return folly::hash::twang_mix64(i);
}

size_t proxygen::RendezvousHash::get ( const uint64_t  key, const size_t  rank = 0  ) const

overridevirtual

get(key, N) finds the node ranked N in the consistent hashing space for the given key.

The returning value is the node's index in the input vector of build().

Implements proxygen::ConsistentHash.

Definition at line 127 of file RendezvousHash.cpp.

References getNthByWeightedHash().

Referenced by TEST().

                                                                      {
  return getNthByWeightedHash(key, rank, nullptr);
}

double proxygen::RendezvousHash::getMaxErrorRate ( ) const

overridevirtual

get max error rate the current hashing space

Implements proxygen::ConsistentHash.

Definition at line 222 of file RendezvousHash.cpp.

                                             {
  return 0;
}

size_t proxygen::RendezvousHash::getNthByWeightedHash ( const uint64_t  key, const size_t  modRank, std::vector< size_t > *  returnRankIds  ) const

private

Definition at line 134 of file RendezvousHash.cpp.

References computeHash(), FOR_EACH_ENUMERATE, i, max, and weights_.

Referenced by get(), and selectNUnweighted().

                                            {
  size_t modRank = rank % weights_.size();
  // optimize if required to return element with max weight, rank ==
  // weights_.size(), keep track of the maxWeightIndex instead of populating
  // scaledWeights array.
  double maxWeight = -1;
  int maxWeightIndex = 0;

  std::vector<std::pair<double, size_t>> scaledWeights;
  if (modRank != 0) {
    scaledWeights.reserve(weights_.size());
  }
  FOR_EACH_ENUMERATE(i, entry, weights_) {
    // combine the hash with the cluster together
    double combinedHash = computeHash(entry->first + key);
    double scaledHash =
        (double)combinedHash / std::numeric_limits<uint64_t>::max();
    double scaledWeight = 0;
    if (entry->second != 0) {
      scaledWeight = pow(scaledHash, (double)1 / entry->second);
    }
    if (modRank == 0) {
      if (scaledWeight > maxWeight) {
        maxWeight = scaledWeight;
        maxWeightIndex = i;
      }
    } else {
      scaledWeights.emplace_back(scaledWeight, i);
    }
  }

  size_t rankIndex;
  if (modRank == 0) {
    rankIndex = maxWeightIndex;
  } else {
    std::nth_element(scaledWeights.begin(),
                     scaledWeights.begin() + modRank,
                     scaledWeights.end(),
                     std::greater<std::pair<double, size_t>>());
    rankIndex = scaledWeights[modRank].second;
  }

  if (returnRankIds) {
    if (modRank == 0) {
      returnRankIds->push_back(rankIndex);
    } else {
      returnRankIds->reserve(modRank);
      for (size_t i = 0; i < modRank; i++) {
        returnRankIds->push_back(scaledWeights[i].second);
      }
    }
  }

  return rankIndex;
}

std::vector< size_t > proxygen::RendezvousHash::selectNUnweighted	(	const uint64_t	key,
		const size_t	rank
	)		const

Definition at line 199 of file RendezvousHash.cpp.

References getNthByWeightedHash(), and weights_.

Referenced by TEST().

                                                                               {
  std::vector<size_t> selection;
  // shortcut if rank is equal or larger than array size
  if (rank >= weights_.size()) {
    selection = std::vector<size_t>(weights_.size());
    std::generate(
        selection.begin(), selection.end(), [n = 0]() mutable { return n++; });
    return selection;
  }

  getNthByWeightedHash(key, rank, &selection);
  return selection;
}

Member Data Documentation

std::vector<std::pair<uint64_t, uint64_t> > proxygen::RendezvousHash::weights_

private

Definition at line 43 of file RendezvousHash.h.

Referenced by build(), getNthByWeightedHash(), and selectNUnweighted().

---

The documentation for this class was generated from the following files:

• proxygen/lib/utils/RendezvousHash.h
• proxygen/lib/utils/RendezvousHash.cpp