TS-2332: Add Consistent Hash Class
Project: http://git-wip-us.apache.org/repos/asf/trafficserver/repo Commit: http://git-wip-us.apache.org/repos/asf/trafficserver/commit/123590fb Tree: http://git-wip-us.apache.org/repos/asf/trafficserver/tree/123590fb Diff: http://git-wip-us.apache.org/repos/asf/trafficserver/diff/123590fb Branch: refs/heads/master Commit: 123590fb30dec31a2c304fc41f49c81d33f1db21 Parents: 5d0d6d8 Author: Phil Sorber <[email protected]> Authored: Fri Aug 8 15:20:14 2014 -0600 Committer: Phil Sorber <[email protected]> Committed: Fri Aug 8 16:06:25 2014 -0600 ---------------------------------------------------------------------- CHANGES | 2 + lib/ts/ConsistentHash.cc | 182 ++++++++++++++++++++++++++++++++++++++++++ lib/ts/ConsistentHash.h | 65 +++++++++++++++ lib/ts/Makefile.am | 2 + lib/ts/libts.h | 1 + 5 files changed, 252 insertions(+) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/trafficserver/blob/123590fb/CHANGES ---------------------------------------------------------------------- diff --git a/CHANGES b/CHANGES index 0050a2d..48e637e 100644 --- a/CHANGES +++ b/CHANGES @@ -1,6 +1,8 @@ -*- coding: utf-8 -*- Changes with Apache Traffic Server 5.1.0 + *) [TS-2332] Add Consistent Hash class. + *) [TS-1800] Create one hashing infrastructure. *) [TS-2860] Add AArch64 support. http://git-wip-us.apache.org/repos/asf/trafficserver/blob/123590fb/lib/ts/ConsistentHash.cc ---------------------------------------------------------------------- diff --git a/lib/ts/ConsistentHash.cc b/lib/ts/ConsistentHash.cc new file mode 100644 index 0000000..69b414b --- /dev/null +++ b/lib/ts/ConsistentHash.cc @@ -0,0 +1,182 @@ +/** @file + + @section license License + + Licensed to the Apache Software Foundation (ASF) under one + or more contributor license agreements. See the NOTICE file + distributed with this work for additional information + regarding copyright ownership. The ASF licenses this file + to you under the Apache License, Version 2.0 (the + "License"); you may not use this file except in compliance + with the License. You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. + */ + +#include "ConsistentHash.h" +#include <cstring> +#include <string> +#include <sstream> +#include <cmath> +#include <climits> +#include <cstdio> + +std::ostream & +operator << (std::ostream & os, ATSConsistentHashNode & thing) { + return os << thing.name; +} + +ATSConsistentHash::ATSConsistentHash(int r, ATSHash64 *h) : replicas(r), hash(h) { +} + +void +ATSConsistentHash::insert(ATSConsistentHashNode *node, float weight, ATSHash64 *h) { + int i; + char numstr[256]; + ATSHash64 *thash; + std::ostringstream string_stream; + std::string std_string; + + if (h) { + thash = h; + } else if (hash) { + thash = hash; + } else { + return; + } + + string_stream << *node; + std_string = string_stream.str(); + + for (i = 0; i < (int) roundf(replicas * weight); i++) { + snprintf(numstr, 256, "%d-", i); + thash->update(numstr, strlen(numstr)); + thash->update(std_string.c_str(), strlen(std_string.c_str())); + thash->final(); + NodeMap.insert(std::pair<uint64_t,ATSConsistentHashNode*>(thash->get(), node)); + thash->clear(); + } +} + +ATSConsistentHashNode* +ATSConsistentHash::lookup(const char *url, ATSConsistentHashIter *i, bool *w, ATSHash64 *h) { + uint64_t url_hash; + ATSConsistentHashIter NodeMapIterUp, *iter; + ATSHash64 *thash; + bool *wptr, wrapped = false; + + if (h) { + thash = h; + } else if (hash) { + thash = hash; + } else { + return NULL; + } + + if (w) { + wptr = w; + } else { + wptr = &wrapped; + } + + if (i) { + iter = i; + } else { + iter = &NodeMapIterUp; + } + + if (url) { + thash->update(url, strlen(url)); + thash->final(); + url_hash = thash->get(); + thash->clear(); + + *iter = NodeMap.lower_bound(url_hash); + + if (*iter == NodeMap.end()) { + *wptr = true; + *iter = NodeMap.begin(); + } + + } else { + (*iter)++; + } + + if (!(*wptr) && *iter == NodeMap.end()) { + *wptr = true; + *iter = NodeMap.begin(); + } + + if (*wptr && *iter == NodeMap.end()) { + return NULL; + } + + return (*iter)->second; +} + +ATSConsistentHashNode* +ATSConsistentHash::lookup_available(const char *url, ATSConsistentHashIter *i, bool *w, ATSHash64 *h) { + uint64_t url_hash; + ATSConsistentHashIter NodeMapIterUp, *iter; + ATSHash64 *thash; + bool *wptr, wrapped = false; + + if (h) { + thash = h; + } else if (hash) { + thash = hash; + } else { + return NULL; + } + + if (w) { + wptr = w; + } else { + wptr = &wrapped; + } + + if (i) { + iter = i; + } else { + iter = &NodeMapIterUp; + } + + if (url) { + thash->update(url, strlen(url)); + thash->final(); + url_hash = thash->get(); + thash->clear(); + + *iter = NodeMap.lower_bound(url_hash); + } + + if (*iter == NodeMap.end()) { + *wptr = true; + *iter = NodeMap.begin(); + } + + while (!(*iter)->second->available) { + (*iter)++; + + if (!(*wptr) && *iter == NodeMap.end()) { + *wptr = true; + *iter = NodeMap.begin(); + } else if (*wptr && *iter == NodeMap.end()) { + return NULL; + } + } + + return (*iter)->second; +} + +ATSConsistentHash::~ATSConsistentHash() { + if (hash) { + delete hash; + } +} http://git-wip-us.apache.org/repos/asf/trafficserver/blob/123590fb/lib/ts/ConsistentHash.h ---------------------------------------------------------------------- diff --git a/lib/ts/ConsistentHash.h b/lib/ts/ConsistentHash.h new file mode 100644 index 0000000..b6efd85 --- /dev/null +++ b/lib/ts/ConsistentHash.h @@ -0,0 +1,65 @@ +/** @file + + @section license License + + Licensed to the Apache Software Foundation (ASF) under one + or more contributor license agreements. See the NOTICE file + distributed with this work for additional information + regarding copyright ownership. The ASF licenses this file + to you under the Apache License, Version 2.0 (the + "License"); you may not use this file except in compliance + with the License. You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. + */ + +#ifndef __CONSISTENT_HASH_H__ +#define __CONSISTENT_HASH_H__ + +#include "Hash.h" +#include <stdint.h> +#include <iostream> +#include <map> + +/* + Helper class to be extended to make ring nodes. + */ + +struct ATSConsistentHashNode +{ + bool available; + char *name; +}; + +std::ostream & +operator<< (std::ostream & os, ATSConsistentHashNode & thing); + +typedef std::map<uint64_t,ATSConsistentHashNode*>::iterator ATSConsistentHashIter; + +/* + TSConsistentHash requires a TSHash64 object + + Caller is responsible for freeing ring node memory. + */ + +struct ATSConsistentHash +{ + ATSConsistentHash(int r = 1024, ATSHash64 *h = NULL); + void insert(ATSConsistentHashNode *node, float weight = 1.0, ATSHash64 *h = NULL); + ATSConsistentHashNode *lookup(const char *url = NULL, ATSConsistentHashIter *i = NULL, bool *w = NULL, ATSHash64 *h = NULL); + ATSConsistentHashNode *lookup_available(const char *url = NULL, ATSConsistentHashIter *i = NULL, bool *w = NULL, ATSHash64 *h = NULL); + ~ATSConsistentHash(); + +private: + int replicas; + ATSHash64 *hash; + std::map<uint64_t, ATSConsistentHashNode*> NodeMap; +}; + +#endif http://git-wip-us.apache.org/repos/asf/trafficserver/blob/123590fb/lib/ts/Makefile.am ---------------------------------------------------------------------- diff --git a/lib/ts/Makefile.am b/lib/ts/Makefile.am index 6d207eb..c0d4517 100644 --- a/lib/ts/Makefile.am +++ b/lib/ts/Makefile.am @@ -47,6 +47,8 @@ libtsutil_la_SOURCES = \ Bitops.h \ Compatability.h \ Cryptohash.h \ + ConsistentHash.cc \ + ConsistentHash.h \ Diags.cc \ Diags.h \ DynArray.h \ http://git-wip-us.apache.org/repos/asf/trafficserver/blob/123590fb/lib/ts/libts.h ---------------------------------------------------------------------- diff --git a/lib/ts/libts.h b/lib/ts/libts.h index 245ef77..c7cbc5e 100644 --- a/lib/ts/libts.h +++ b/lib/ts/libts.h @@ -79,6 +79,7 @@ #include "Arena.h" #include "Bitops.h" #include "Compatability.h" +#include "ConsistentHash.h" #include "DynArray.h" #include "EventNotify.h" #include "Hash.h"
