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}