This is an automated email from the ASF dual-hosted git repository.
masaori335 pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/trafficserver.git
The following commit(s) were added to refs/heads/master by this push:
new 38076cc460 Bound the ring walk of ParentConsistentHash::selectParent
(#13368)
38076cc460 is described below
commit 38076cc46040d88e10c7b7a3a95bde3b4f4e996e
Author: Masaori Koshiba <[email protected]>
AuthorDate: Fri Aug 7 09:54:42 2026 +0900
Bound the ring walk of ParentConsistentHash::selectParent (#13368)
* Bound the ring walk of ParentConsistentHash::selectParent
When every parent in a consistent_hash pool is down, selectParent walked the
whole hash ring taking the global host_status_rwlock on every hop. The ring
holds 1024 replica nodes per parent (num_parents * 1024 nodes) and the
chash_lookup() gate withholds wrap_around until the ring is traversed
twice, so
one all-down selection cost ~2 * num_parents * 1024
HostStatus::getHostStatus()
calls (~49k for 24 parents) -- inline ET_NET CPU that starved the loopback
health probe and drove the VIP flap in inc-p1s2-260703.
Track the distinct parents examined on each ring: skip the locked
getHostStatus
read for a parent already seen, and force wrap_around once every distinct
parent
has been rejected. The expensive locked read is now paid at most once per
parent
(O(num_parents)); the ring still advances ~O(N*logN) cheap, lock-free hops
to
reach every distinct parent. Selection order and the retry-window logic are
unchanged.
The seen-parent tracking is sized to num_parents (std::vector<bool>), not
MAX_PARENTS: the parent.config parser does not cap num_parents at
MAX_PARENTS, so
a fixed [MAX_PARENTS] array would overflow the stack for pools larger than
64.
Add consistent_hash_ring_walk.test.py: an all-down 100-parent pool (marked
down
via HostStatus, >MAX_PARENTS on purpose) must report "getHostStatus calls:
100",
proving the walk reads each parent once instead of walking the full ring.
* Keep the parent seen-flags out of the heap in selectParent
selectParent() runs inline on ET_NET for every transaction, so the two
std::vector<bool> allocations per call are pure overhead for what is a
64-flag bitmap in the ordinary case.
ts::LocalBuffer<bool, MAX_PARENTS> keeps both rings' flags on the stack
(80 bytes each) and falls back to the heap only for a pool larger than
MAX_PARENTS, which stays necessary because the parent.config parser does
not cap num_parents.
---
src/proxy/ParentConsistentHash.cc | 45 ++++++-
.../parent_proxy/consistent_hash_ring_walk.test.py | 143 +++++++++++++++++++++
2 files changed, 184 insertions(+), 4 deletions(-)
diff --git a/src/proxy/ParentConsistentHash.cc
b/src/proxy/ParentConsistentHash.cc
index fad0d94e6f..29be36b511 100644
--- a/src/proxy/ParentConsistentHash.cc
+++ b/src/proxy/ParentConsistentHash.cc
@@ -20,10 +20,12 @@
See the License for the specific language governing permissions and
limitations under the License.
*/
+#include <algorithm>
#include <atomic>
#include "proxy/HostStatus.h"
#include "proxy/ParentConsistentHash.h"
#include "tscore/HashSip.h"
+#include "tsutil/LocalBuffer.h"
namespace
{
@@ -151,6 +153,19 @@ ParentConsistentHash::selectParent(bool first_call,
ParentResult *result, Reques
HostStatus &pStatus = HostStatus::instance();
TSHostStatus host_stat = TSHostStatus::TS_HOST_STATUS_INIT;
+ // Bound the all-down ring walk: read each distinct parent's status at most
once.
+ // Stack resident up to MAX_PARENTS -- the parent.config parser does not cap
num_parents, so a bigger
+ // pool falls back to the heap rather than overflowing the stack.
+ int const num_parents_in_ring[2] =
{result->rec->num_parents, result->rec->num_secondary_parents};
+ ts::LocalBuffer<bool, MAX_PARENTS>
primary_seen(num_parents_in_ring[PRIMARY]);
+ ts::LocalBuffer<bool, MAX_PARENTS>
secondary_seen(num_parents_in_ring[SECONDARY]);
+ bool *const seen_parent[2] = {primary_seen.data(),
secondary_seen.data()};
+ int seen_count[2] = {0, 0};
+ int host_status_calls = 0; // getHostStatus()
calls this selection (== distinct parents examined)
+
+ std::fill_n(seen_parent[PRIMARY], num_parents_in_ring[PRIMARY], false);
+ std::fill_n(seen_parent[SECONDARY], num_parents_in_ring[SECONDARY], false);
+
Dbg(dbg_ctl_parent_select, "ParentConsistentHash::%s(): Using a consistent
hash parent selection strategy.", __func__);
ink_assert(numParents(result) > 0 || result->rec->go_direct == true);
@@ -220,8 +235,14 @@ ParentConsistentHash::selectParent(bool first_call,
ParentResult *result, Reques
//
----------------------------------------------------------------------------------------------------
// didn't find a parent or the parent is marked unavailable or the parent is
marked down
- HostStatRec *hst = (pRec) ? pStatus.getHostStatus(pRec->hostname) : nullptr;
- host_stat = (hst) ? hst->status : TSHostStatus::TS_HOST_STATUS_UP;
+ HostStatRec *hst = nullptr;
+ if (pRec) {
+ hst = pStatus.getHostStatus(pRec->hostname);
+ host_status_calls++;
+ seen_parent[last_lookup][pRec->idx] = true;
+ seen_count[last_lookup]++;
+ }
+ host_stat = (hst) ? hst->status : TSHostStatus::TS_HOST_STATUS_UP;
if (firstCall) {
result->first_choice_status = host_stat;
}
@@ -234,6 +255,8 @@ ParentConsistentHash::selectParent(bool first_call,
ParentResult *result, Reques
}
}
if (!pRec || (pRec && !pRec->available.load()) || host_stat ==
TS_HOST_STATUS_DOWN) {
+ // All-down walk: ~O(N*logN) lock-free ring hops to reach every distinct
parent, but <= N (num_parents) getHostStatus reads (see
+ // seen_parent below).
do {
// check if the host is retryable. It's retryable if the retry window
has elapsed
// and the global host status is HOST_STATUS_UP
@@ -312,7 +335,21 @@ ParentConsistentHash::selectParent(bool first_call,
ParentResult *result, Reques
Dbg(dbg_ctl_parent_select, "No available parents.");
break;
}
- hst = (pRec) ? pStatus.getHostStatus(pRec->hostname) : nullptr;
+ // Read each distinct parent's status at most once; force wrap when all
are rejected.
+ if (pRec && seen_parent[last_lookup][pRec->idx]) {
+ if (seen_count[last_lookup] >= num_parents_in_ring[last_lookup]) {
+ wrap_around[last_lookup] = true;
+ }
+ host_stat = TS_HOST_STATUS_DOWN;
+ continue;
+ }
+ hst = nullptr;
+ if (pRec) {
+ hst = pStatus.getHostStatus(pRec->hostname);
+ host_status_calls++;
+ seen_parent[last_lookup][pRec->idx] = true;
+ seen_count[last_lookup]++;
+ }
host_stat = (hst) ? hst->status : TSHostStatus::TS_HOST_STATUS_UP;
// if the config ignore_self_detect is set to true and the host is down
due to SELF_DETECT reason
// ignore the down status and mark it as available
@@ -324,7 +361,7 @@ ParentConsistentHash::selectParent(bool first_call,
ParentResult *result, Reques
} while (!pRec || !pRec->available.load() || host_stat ==
TS_HOST_STATUS_DOWN);
}
- Dbg(dbg_ctl_parent_select, "Additional parent lookups: %d", lookups);
+ Dbg(dbg_ctl_parent_select, "Additional parent lookups: %d, getHostStatus
calls: %d", lookups, host_status_calls);
//
----------------------------------------------------------------------------------------------------
// Validate and return the final result.
diff --git a/tests/gold_tests/parent_proxy/consistent_hash_ring_walk.test.py
b/tests/gold_tests/parent_proxy/consistent_hash_ring_walk.test.py
new file mode 100644
index 0000000000..a279c2c7c7
--- /dev/null
+++ b/tests/gold_tests/parent_proxy/consistent_hash_ring_walk.test.py
@@ -0,0 +1,143 @@
+"""
+Verify ParentConsistentHash::selectParent() does not waste work walking an
+all-down consistent_hash pool.
+
+A consistent-hash ring has 1024 replica nodes per parent (default
+ATSConsistentHash replicas, DEFAULT_PARENT_WEIGHT=1.0), so num_parents*1024
ring
+nodes total. When every parent is down, selectParent must walk the ring to
+conclude so -- but it must read each parent's HostStatus (the global
+host_status_rwlock) at most ONCE, not once per replica node. selectParent
tracks
+the distinct parents examined and stops as soon as all are rejected, so an
+all-down selection over N parents costs exactly N getHostStatus calls -- not
the
+~2*N*1024 (two ring passes) the naive walk cost, which put ~8-13 ms of inline
+ET_NET CPU per request and wedged the vipd health probe in inc-p1s2-260703.
+
+Proven by the per-selection "getHostStatus calls: <N>" debug line
+(ParentConsistentHash.cc): it must equal the parent count, not a five-figure
ring
+walk.
+
+Pool size > MAX_PARENTS (64) on purpose: num_parents is NOT capped at
+MAX_PARENTS by the config parser, so the per-selection "seen parent" tracking
+must be sized to the actual pool (a fixed [MAX_PARENTS] array would overflow).
+Running a >64-parent pool to completion (no crash, correct 502, bounded count)
+guards that sizing.
+
+no_dns_just_forward_to_parent=1 lets ATS skip origin resolution and go straight
+to parent selection, so this test needs no DNS server and no origin -- every
+parent is HostStatus-DOWN => PARENT_FAIL => 502 before any connect.
+"""
+# 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.
+
+import os
+
+from ports import get_port
+
+Test.Summary = '''
+An all-down consistent_hash parent pool (marked down via HostStatus) drives
+selectParent to read each distinct parent's HostStatus exactly once
+(O(num_parents)), not once per ring replica node (~2 * num_parents * 1024).
+'''
+Test.ContinueOnFail = True
+
+# > MAX_PARENTS (64): exercises the pool-sized "seen parent" tracking and would
+# overflow a fixed [MAX_PARENTS] array. Distinct names matter --
consistent_hash
+# keys the ring on hostname, so identical names would collapse to one ring
node.
+NUM_PARENTS = 100
+
+
+class ParentDownRingWalkTest:
+ """All parents HostStatus-DOWN => selectParent reads each parent once =>
502."""
+
+ parent_hostnames = [f'deadparent{i:03d}' for i in range(1, NUM_PARENTS +
1)]
+
+ def __init__(self):
+ self._setupTS()
+
+ def _setupTS(self):
+ self.ts = Test.MakeATSProcess('ts', enable_cache=False)
+
+ # A dead (reserved-but-unbound) port per parent. They are never
actually
+ # connected -- every parent is HostStatus-DOWN so selectParent returns
+ # PARENT_FAIL before any connect -- but parent.config needs a port.
+ self._parent_ports = []
+ for i in range(len(self.parent_hostnames)):
+ name = f'dead_parent_port_{i}'
+ get_port(self.ts, name)
+ self._parent_ports.append(getattr(self.ts.Variables, name))
+
+ self.ts.Disk.records_config.update(
+ {
+ # Enable only the parent_select debug ctl so the per-selection
+ # "getHostStatus calls: <N>" line is emitted.
+ 'proxy.config.diags.debug.enabled': 1,
+ 'proxy.config.diags.debug.tags': 'parent_select',
+ # Skip origin DNS: forward straight to parent selection. No DNS
+ # server / origin needed for this isolation.
+ 'proxy.config.http.no_dns_just_forward_to_parent': 1,
+ # self_detect off: this test populates the HostStatus map via
+ # `traffic_ctl host down` below, not via self_detect (the
+ # deadparents never resolve to this box anyway).
+ 'proxy.config.http.parent_proxy.fail_threshold': 10,
+ 'proxy.config.http.parent_proxy.retry_time': 300,
+ 'proxy.config.http.parent_proxy.self_detect': 0,
+ 'proxy.config.url_remap.remap_required': 0,
+ })
+
+ # Consistent-hash pool of distinct parent hostnames, go_direct=false
so an
+ # all-down pool yields 502 (not a direct-to-origin fallback).
+ self._parents = list(zip(self.parent_hostnames, self._parent_ports))
+ parent_list = ', '.join(f'{host}:{port}|1' for host, port in
self._parents)
+ self.ts.Disk.parent_config.AddLine(
+ f'dest_domain=. parent="{parent_list}" round_robin=consistent_hash
'
+ 'go_direct=false parent_is_proxy=true')
+
+ # The all-down selection is a single findParent call. selectParent
reads
+ # each distinct parent's HostStatus at most once and stops once all are
+ # rejected, so the per-selection "getHostStatus calls" count equals the
+ # parent count -- not the ~2*N*1024 five-figure ring walk it cost
before.
+ self.ts.Disk.traffic_out.Content += Testers.ContainsExpression(
+ r'getHostStatus calls: %d\b' % NUM_PARENTS,
+ 'selectParent read each distinct parent once (O(num_parents)), not
the full ring.')
+ # It must NOT take the HostStatus lock once per ring replica node (the
old
+ # bug reported a five-figure count).
+ self.ts.Disk.traffic_out.Content += Testers.ExcludesExpression(
+ r'getHostStatus calls: [0-9]{5}', 'selectParent must not read
HostStatus once per ring replica node.')
+
+ def run(self):
+ traffic_ctl = os.path.join(self.ts.Variables.BINDIR, 'traffic_ctl')
+
+ # 1. Bring the whole parent pool DOWN via HostStatus (one RPC call).
+ # Populates hosts_statuses (=> every getHostStatus takes the rwlock)
+ # and forces host_stat==DOWN (=> the full ring walk, no early exit).
+ down = Test.AddTestRun('Mark the entire parent pool down via
HostStatus')
+ down.Processes.Default.StartBefore(self.ts)
+ down.Processes.Default.Command = f'{traffic_ctl} host down ' + '
'.join(self.parent_hostnames)
+ down.Processes.Default.Env = self.ts.Env
+ down.Processes.Default.ReturnCode = 0
+
+ # 2. One request through the all-down pool -> bounded walk -> 502. A
crash
+ # here (e.g. seen-parent tracking overflowing on a >64 pool) fails
the test.
+ load = Test.AddTestRun('Request through the all-down pool -> bounded
selection -> 502')
+ load.MakeCurlCommand(
+ f'-s -o /dev/null -w "%{{http_code}}" --proxy
127.0.0.1:{self.ts.Variables.port} http://example.com/ring-walk-probe',
+ ts=self.ts)
+ load.Processes.Default.Streams.stdout =
Testers.ContainsExpression('502', 'All parents down => 502.')
+ load.Processes.Default.ReturnCode = 0
+ load.StillRunningAfter = self.ts
+
+
+ParentDownRingWalkTest().run()
