You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@trafficserver.apache.org by so...@apache.org on 2014/08/09 00:08:22 UTC
[5/6] git commit: TS-2332: Add Consistent Hash Class
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 <so...@apache.org>
Authored: Fri Aug 8 15:20:14 2014 -0600
Committer: Phil Sorber <so...@apache.org>
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"