TS-2996: Add consistent hash method to parent selection
Project: http://git-wip-us.apache.org/repos/asf/trafficserver/repo Commit: http://git-wip-us.apache.org/repos/asf/trafficserver/commit/7fa5c5c7 Tree: http://git-wip-us.apache.org/repos/asf/trafficserver/tree/7fa5c5c7 Diff: http://git-wip-us.apache.org/repos/asf/trafficserver/diff/7fa5c5c7 Branch: refs/heads/master Commit: 7fa5c5c7ae1837f0cc867924342e03cccb45b9f6 Parents: 123590f Author: Phil Sorber <[email protected]> Authored: Fri Aug 8 15:22:09 2014 -0600 Committer: Phil Sorber <[email protected]> Committed: Fri Aug 8 16:06:28 2014 -0600 ---------------------------------------------------------------------- CHANGES | 2 + proxy/ParentSelection.cc | 149 ++++++++++++++++++++++++++++++++++++------ proxy/ParentSelection.h | 20 ++++-- 3 files changed, 148 insertions(+), 23 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/trafficserver/blob/7fa5c5c7/CHANGES ---------------------------------------------------------------------- diff --git a/CHANGES b/CHANGES index 48e637e..a6db8d9 100644 --- a/CHANGES +++ b/CHANGES @@ -1,6 +1,8 @@ -*- coding: utf-8 -*- Changes with Apache Traffic Server 5.1.0 + *) [TS-2996] Add consistent hash method to parent selection. + *) [TS-2332] Add Consistent Hash class. *) [TS-1800] Create one hashing infrastructure. http://git-wip-us.apache.org/repos/asf/trafficserver/blob/7fa5c5c7/proxy/ParentSelection.cc ---------------------------------------------------------------------- diff --git a/proxy/ParentSelection.cc b/proxy/ParentSelection.cc index de2e94e..8b8af24 100644 --- a/proxy/ParentSelection.cc +++ b/proxy/ParentSelection.cc @@ -336,6 +336,8 @@ ParentConfigParams::recordRetrySuccess(ParentResult * result) ink_assert((int) (result->last_parent) < result->rec->num_parents); pRec = result->rec->parents + result->last_parent; + pRec->available = true; + ink_atomic_swap(&pRec->failedAt, (time_t)0); int old_count = ink_atomic_swap(&pRec->failCount, 0); @@ -399,6 +401,7 @@ ParentConfigParams::markParentDown(ParentResult * result) if (new_fail_count > 0 && new_fail_count == FailThreshold) { Note("http parent proxy %s:%d marked down", pRec->hostname, pRec->port); + pRec->available = false; } } @@ -483,6 +486,9 @@ ParentRecord::FindParent(bool first_call, ParentResult * result, RequestData * r bool parentUp = false; bool parentRetry = false; bool bypass_ok = (go_direct == true && config->DNS_ParentOnly == 0); + char *url, *path = NULL; + ATSHash64Sip24 hash; + pRecord *prtmp = NULL; HttpRequestData *request_info = (HttpRequestData *) rdata; @@ -506,7 +512,7 @@ ParentRecord::FindParent(bool first_call, ParentResult * result, RequestData * r case P_HASH_ROUND_ROBIN: // INKqa12817 - make sure to convert to host byte order // Why was it important to do host order here? And does this have any - // impact with the transition to IPv6? The IPv4 functionality is + // impact with the transition to IPv6? The IPv4 functionality is // preserved for now anyway as ats_ip_hash returns the 32-bit address in // that case. if (rdata->get_client_ip() != NULL) { @@ -515,6 +521,26 @@ ParentRecord::FindParent(bool first_call, ParentResult * result, RequestData * r cur_index = 0; } break; + case P_CONSISTENT_HASH: + url = rdata->get_string(); + path = strstr(url + 7, "/"); + if (path) { + prtmp = (pRecord *) chash->lookup(path, &(result->chashIter), NULL, (ATSHash64 *) &hash); + if (prtmp) { + cur_index = prtmp->idx; + result->foundParents[cur_index] = true; + result->start_parent++; + } else { + Error("Consistent Hash loopup returned NULL"); + cur_index = ink_atomic_increment((int32_t *) & rr_next, 1); + cur_index = cur_index % num_parents; + } + } else { + Error("Could not find path in URL: %s",url); + cur_index = ink_atomic_increment((int32_t *) & rr_next, 1); + cur_index = cur_index % num_parents; + } + break; case P_NO_ROUND_ROBIN: cur_index = result->start_parent = 0; break; @@ -523,19 +549,38 @@ ParentRecord::FindParent(bool first_call, ParentResult * result, RequestData * r } } } else { - // Move to next parent due to failure - cur_index = (result->last_parent + 1) % num_parents; - - // Check to see if we have wrapped around - if ((unsigned int) cur_index == result->start_parent) { - // We've wrapped around so bypass if we can - if (bypass_ok == true) { - goto NO_PARENTS; - } else { - // Bypass disabled so keep trying, ignoring whether we think - // a parent is down or not - FORCE_WRAP_AROUND: + if (round_robin == P_CONSISTENT_HASH) { + if (result->start_parent == (unsigned int) num_parents) { result->wrap_around = true; + result->start_parent = 0; + memset(result->foundParents, 0, sizeof(result->foundParents)); + url = rdata->get_string(); + path = strstr(url + 7, "/"); + } + + do { + prtmp = (pRecord *) chash->lookup(path, &(result->chashIter), NULL, (ATSHash64 *) &hash); + path = NULL; + } while (result->foundParents[prtmp->idx]); + + cur_index = prtmp->idx; + result->foundParents[cur_index] = true; + result->start_parent++; + } else { + // Move to next parent due to failure + cur_index = (result->last_parent + 1) % num_parents; + + // Check to see if we have wrapped around + if ((unsigned int) cur_index == result->start_parent) { + // We've wrapped around so bypass if we can + if (bypass_ok == true) { + goto NO_PARENTS; + } else { + // Bypass disabled so keep trying, ignoring whether we think + // a parent is down or not + FORCE_WRAP_AROUND: + result->wrap_around = true; + } } } } @@ -575,9 +620,28 @@ ParentRecord::FindParent(bool first_call, ParentResult * result, RequestData * r return; } - cur_index = (cur_index + 1) % num_parents; + if (round_robin == P_CONSISTENT_HASH) { + if (result->start_parent == (unsigned int) num_parents) { + result->wrap_around = false; + result->start_parent = 0; + memset(result->foundParents, 0, sizeof(result->foundParents)); + url = rdata->get_string(); + path = strstr(url + 7, "/"); + } + + do { + prtmp = (pRecord *) chash->lookup(path, &(result->chashIter), NULL, (ATSHash64 *) &hash); + path = NULL; + } while (result->foundParents[prtmp->idx]); - } while ((unsigned int) cur_index != result->start_parent); + cur_index = prtmp->idx; + result->foundParents[cur_index] = true; + result->start_parent++; + } else { + cur_index = (cur_index + 1) % num_parents; + } + + } while ((round_robin == P_CONSISTENT_HASH ? result->wrap_around : ((unsigned int) cur_index != result->start_parent))); // We can't bypass so retry, taking any parent that we can if (bypass_ok == false) { @@ -613,8 +677,9 @@ ParentRecord::ProcessParents(char *val) int numTok; const char *current; int port; - char *tmp; + char *tmp, *tmp2; const char *errPtr; + float weight = 1.0; if (parents != NULL) { return "Can not specify more than one set of parents"; @@ -646,10 +711,26 @@ ParentRecord::ProcessParents(char *val) errPtr = "Malformed parent port"; goto MERROR; } + + // See if there is an optional parent weight + tmp2 = (char *) strchr(current, '|'); + + if (tmp2) { + if (sscanf(tmp2 + 1, "%f", &weight) != 1) { + errPtr = "Malformed parent weight"; + goto MERROR; + } + } + // Make sure that is no garbage beyond the parent - // port - char *scan = tmp + 1; - for (; *scan != '\0' && ParseRules::is_digit(*scan); scan++); + // port or weight + char *scan; + if (tmp2) { + scan = tmp2 + 1; + } else { + scan = tmp + 1; + } + for (; *scan != '\0' && (ParseRules::is_digit(*scan) || *scan == '.'); scan++); for (; *scan != '\0' && ParseRules::is_wslfcr(*scan); scan++); if (*scan != '\0') { errPtr = "Garbage trailing entry or invalid separator"; @@ -670,6 +751,10 @@ ParentRecord::ProcessParents(char *val) this->parents[i].port = port; this->parents[i].failedAt = 0; this->parents[i].scheme = scheme; + this->parents[i].idx = i; + this->parents[i].name = this->parents[i].hostname; + this->parents[i].available = true; + this->parents[i].weight = weight; } num_parents = numTok; @@ -715,6 +800,21 @@ ParentRecord::DefaultInit(char *val) } } +void +ParentRecord::buildConsistentHash(void) { + ATSHash64Sip24 hash; + int i; + + if (chash) { + return; + } + + chash = new ATSConsistentHash(); + + for (i = 0; i < num_parents; i++) { + chash->insert(&(this->parents[i]), this->parents[i].weight, (ATSHash64 *) &hash); + } +} // char* ParentRecord::Init(matcher_line* line_info) // @@ -755,6 +855,11 @@ ParentRecord::Init(matcher_line * line_info) round_robin = P_STRICT_ROUND_ROBIN; } else if (strcasecmp(val, "false") == 0) { round_robin = P_NO_ROUND_ROBIN; + } else if (strcasecmp(val, "consistent_hash") == 0) { + round_robin = P_CONSISTENT_HASH; + if (this->parents != NULL) { + buildConsistentHash(); + } } else { round_robin = P_NO_ROUND_ROBIN; errPtr = "invalid argument to round_robin directive"; @@ -763,6 +868,9 @@ ParentRecord::Init(matcher_line * line_info) } else if (strcasecmp(label, "parent") == 0) { errPtr = ProcessParents(val); used = true; + if (round_robin == P_CONSISTENT_HASH) { + buildConsistentHash(); + } } else if (strcasecmp(label, "go_direct") == 0) { if (strcasecmp(val, "false") == 0) { go_direct = false; @@ -833,6 +941,9 @@ ParentRecord::UpdateMatch(ParentResult * result, RequestData * rdata) ParentRecord::~ParentRecord() { + if (chash) { + delete chash; + } ats_free(parents); } http://git-wip-us.apache.org/repos/asf/trafficserver/blob/7fa5c5c7/proxy/ParentSelection.h ---------------------------------------------------------------------- diff --git a/proxy/ParentSelection.h b/proxy/ParentSelection.h index 0a4dc77..e02bcc9 100644 --- a/proxy/ParentSelection.h +++ b/proxy/ParentSelection.h @@ -40,6 +40,10 @@ #include "P_RecProcess.h" +#include "libts.h" + +#define MAX_PARENTS 64 + struct RequestData; struct matcher_line; @@ -62,7 +66,7 @@ struct ParentResult ParentResult() : r(PARENT_UNDEFINED), hostname(NULL), port(0), line_number(0), epoch(NULL), rec(NULL), last_parent(0), start_parent(0), wrap_around(false), retry(false) - { }; + { memset(foundParents, 0, sizeof(foundParents)); }; // For outside consumption ParentResultType r; @@ -78,6 +82,9 @@ struct ParentResult uint32_t start_parent; bool wrap_around; bool retry; + //Arena *a; + ATSConsistentHashIter chashIter; + bool foundParents[MAX_PARENTS]; }; class HttpRequestData; @@ -154,7 +161,7 @@ public: // // A record for an invidual parent // -struct pRecord +struct pRecord : ATSConsistentHashNode { char hostname[MAXDNAME + 1]; int port; @@ -162,13 +169,16 @@ struct pRecord int failCount; int32_t upAt; const char *scheme; // for which parent matches (if any) + int idx; + float weight; }; enum ParentRR_t { P_NO_ROUND_ROBIN = 0, P_STRICT_ROUND_ROBIN, - P_HASH_ROUND_ROBIN + P_HASH_ROUND_ROBIN, + P_CONSISTENT_HASH }; // class ParentRecord : public ControlBase @@ -180,7 +190,7 @@ class ParentRecord: public ControlBase { public: ParentRecord() - : parents(NULL), num_parents(0), round_robin(P_NO_ROUND_ROBIN), rr_next(0), go_direct(true) + : parents(NULL), num_parents(0), round_robin(P_NO_ROUND_ROBIN), rr_next(0), go_direct(true), chash(NULL) { } ~ParentRecord(); @@ -198,9 +208,11 @@ public: const char *scheme; //private: const char *ProcessParents(char *val); + void buildConsistentHash(void); ParentRR_t round_robin; volatile uint32_t rr_next; bool go_direct; + ATSConsistentHash *chash; }; // Helper Functions
