foundationdb/tuple_ext/hca.rs
1// Copyright 2018 foundationdb-rs developers, https://github.com/Clikengo/foundationdb-rs/graphs/contributors
2// Copyright 2013-2018 Apple, Inc and the FoundationDB project authors.
3//
4// Licensed under the Apache License, Version 2.0, <LICENSE-APACHE or
5// http://apache.org/licenses/LICENSE-2.0> or the MIT license <LICENSE-MIT or
6// http://opensource.org/licenses/MIT>, at your option. This file may not be
7// copied, modified, or distributed except according to those terms.
8
9//! The directory layer offers subspace indirection, where logical application subspaces are mapped to short, auto-generated key prefixes. This prefix assignment is done by the High Contention Allocator, which allows many clients to allocate short directory prefixes efficiently.
10//!
11//! The allocation process works over candidate value windows. It uses two subspaces to operate, the "counters" subspace and "recents" subspace (derived from the subspace used to create the HCA).
12//!
13//! "counters" contains a single key : "counters : window_start", whose value is the number of allocations in the current window. "window_start" is an integer that marks the lower bound of values that can be assigned from the current window.
14//! "recents" can contain many keys : "recents : candidate", where each "candidate" is an integer that has been assigned to some client
15//!
16//! Assignment has two stages that are executed in a loop until they both succeed.
17//!
18//! 1. Find the current window. The client scans "counters : *" to get the current "window_start" and how many allocations have been made in the current window.
19//! If the window is more than half-full (using pre-defined window sizes), the window is advanced: "counters : *" and "recents : *" are both cleared, and a new "counters : window_start + window_size" key is created with a value of 0. (1) is retried
20//! If the window still has space, it moves to (2).
21//!
22//! 2. Find a candidate value inside that window. The client picks a candidate number between "[window_start, window_start + window_size)" and tries to set the key "recents : candidate".
23//! If the write succeeds, the candidate is returned as the allocated value. Success!
24//! If the write fails because the window has been advanced, it repeats (1).
25//! If the write fails because the value was already set, it repeats (2).
26
27use std::fmt;
28use std::sync::{Mutex, PoisonError};
29
30use futures::future;
31use rand::{RngExt, rngs::SmallRng};
32
33use crate::options::{ConflictRangeType, MutationType, TransactionOption};
34use crate::tuple::{PackError, Subspace};
35use crate::*;
36
37const ONE_BYTES: &[u8] = &[0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00];
38
39// Separate allocators may share a transaction and subspace. Serialize their
40// read-before-write sequences across instances, releasing the lock before await.
41static ALLOCATION_MUTEX: Mutex<()> = Mutex::new(());
42
43pub enum HcaError {
44 FdbError(FdbError),
45 PackError(PackError),
46 InvalidDirectoryLayerMetadata,
47 PoisonError,
48}
49
50impl fmt::Debug for HcaError {
51 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
52 match self {
53 HcaError::FdbError(err) => err.fmt(f),
54 HcaError::PackError(err) => err.fmt(f),
55 HcaError::InvalidDirectoryLayerMetadata => {
56 write!(f, "invalid directory layer metadata")
57 }
58 HcaError::PoisonError => write!(f, "mutex poisoned"),
59 }
60 }
61}
62
63impl fmt::Display for HcaError {
64 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
65 fmt::Debug::fmt(self, f)
66 }
67}
68
69impl std::error::Error for HcaError {
70 fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
71 match self {
72 HcaError::FdbError(e) => Some(e),
73 HcaError::PackError(e) => Some(e),
74 HcaError::InvalidDirectoryLayerMetadata | HcaError::PoisonError => None,
75 }
76 }
77}
78
79impl From<FdbError> for HcaError {
80 fn from(err: FdbError) -> Self {
81 Self::FdbError(err)
82 }
83}
84impl From<PackError> for HcaError {
85 fn from(err: PackError) -> Self {
86 Self::PackError(err)
87 }
88}
89impl<T> From<PoisonError<T>> for HcaError {
90 fn from(_err: PoisonError<T>) -> Self {
91 Self::PoisonError
92 }
93}
94
95impl TransactError for HcaError {
96 fn try_into_fdb_error(self) -> Result<FdbError, Self> {
97 match self {
98 HcaError::FdbError(err) => Ok(err),
99 _ => Err(self),
100 }
101 }
102}
103
104/// Represents a High Contention Allocator for a given subspace
105#[derive(Debug)]
106pub struct HighContentionAllocator {
107 counters: Subspace,
108 recent: Subspace,
109}
110
111impl HighContentionAllocator {
112 /// Constructs an allocator that will use the input subspace for assigning values.
113 /// The given subspace should not be used by anything other than the allocator
114 pub fn new(subspace: Subspace) -> HighContentionAllocator {
115 HighContentionAllocator {
116 counters: subspace.subspace(&0i64),
117 recent: subspace.subspace(&1i64),
118 }
119 }
120
121 /// Returns a byte string that
122 /// 1) has never and will never be returned by another call to this method on the same subspace
123 /// 2) is nearly as short as possible given the above
124 pub async fn allocate(&self, trx: &Transaction) -> Result<i64, HcaError> {
125 let (begin, end) = self.counters.range();
126 let begin = KeySelector::first_greater_or_equal(begin);
127 let end = KeySelector::first_greater_than(end);
128 let counters_range = RangeOption {
129 begin,
130 end,
131 limit: Some(1),
132 reverse: true,
133 ..RangeOption::default()
134 };
135 let mut rng: SmallRng = rand::make_rng();
136
137 loop {
138 let kvs = trx.get_range(&counters_range, 1, true).await?;
139
140 let mut start: i64 = if let Some(first) = kvs.first() {
141 self.counters.unpack(first.key())?
142 } else {
143 0
144 };
145
146 let mut window_advanced = false;
147
148 let window = loop {
149 let counters_start = self.counters.subspace(&start);
150
151 let count_future = {
152 let _mutex_guard = ALLOCATION_MUTEX.lock()?;
153 if window_advanced {
154 trx.clear_range(self.counters.bytes(), counters_start.bytes());
155 trx.set_option(TransactionOption::NextWriteNoWriteConflictRange)?;
156 trx.clear_range(self.recent.bytes(), self.recent.subspace(&start).bytes());
157 };
158
159 // Increment the allocation count for the current window
160 trx.atomic_op(counters_start.bytes(), ONE_BYTES, MutationType::Add);
161 trx.get(counters_start.bytes(), true)
162 };
163
164 let count_value = count_future.await?;
165 let count = if let Some(count_value) = count_value {
166 if count_value.len() != 8 {
167 return Err(HcaError::InvalidDirectoryLayerMetadata);
168 }
169 let mut bytes = [0u8; 8];
170 bytes.copy_from_slice(&count_value);
171 i64::from_le_bytes(bytes)
172 } else {
173 0
174 };
175
176 let window = Self::window_size(start);
177 if count * 2 < window {
178 break window;
179 }
180
181 start += window;
182 window_advanced = true;
183 };
184
185 loop {
186 // As of the snapshot being read from, the window is less than half
187 // full, so this should be expected to take 2 tries. Under high
188 // contention (and when the window advances), there is an additional
189 // subsequent risk of conflict for this transaction.
190 let candidate: i64 = rng.random_range(start..start + window);
191 let recent_candidate = self.recent.subspace(&candidate);
192
193 let (latest_counter, candidate_value) = {
194 let _mutex_guard = ALLOCATION_MUTEX.lock()?;
195 let latest_counter = trx.get_range(&counters_range, 1, true);
196 let candidate_value = trx.get(recent_candidate.bytes(), false);
197 trx.set_option(TransactionOption::NextWriteNoWriteConflictRange)?;
198 trx.set(recent_candidate.bytes(), &[]);
199 (latest_counter, candidate_value)
200 };
201
202 let (latest_counter, candidate_value) =
203 future::try_join(latest_counter, candidate_value).await?;
204
205 let current_window_start: i64 = if let Some(first) = latest_counter.first() {
206 self.counters.unpack(first.key())?
207 } else {
208 0
209 };
210
211 if current_window_start > start {
212 break;
213 }
214
215 if candidate_value.is_none() {
216 let mut after = recent_candidate.bytes().to_vec();
217 after.push(0x00);
218 trx.add_conflict_range(
219 recent_candidate.bytes(),
220 &after,
221 ConflictRangeType::Write,
222 )?;
223 return Ok(candidate);
224 }
225 }
226 }
227 }
228
229 fn window_size(start: i64) -> i64 {
230 // Larger window sizes are better for high contention, smaller sizes for
231 // keeping the keys small. But if there are many allocations, the keys
232 // can't be too small. So start small and scale up. We don't want this to
233 // ever get *too* big because we have to store about window_size/2 recent
234 // items.
235 match start {
236 _ if start < 255 => 64,
237 _ if start < 65535 => 1024,
238 _ => 8192,
239 }
240 }
241}