chadtmiller.com/knotless
git that lives in your Atmosphere account
1
10
A repository's ref records past the first page are read side by side
.changeset/refs-side-by-side.mdnew+7−0
| @@ -0,0 +1,7 @@ | ||
--- | ||
default: patch | ||
--- | ||
| ||
# Reading a repository with many deleted branches is faster | ||
| ||
A repository keeps a record for every branch it ever had. Past the first 100, knotless now reads those records in ranges side by side rather than one page after another. Pushing to, cloning and listing a repository that has had hundreds of branches, as a busy one does, takes a fraction of the time, for example 0.37 seconds rather than 1.7 for 590. | ||
crates/knotless/src/remote.rs+80−1
| @@ -42,6 +42,27 @@ impl<T> Default for Page<T> { | ||
} | ||
} | ||
| ||
/// Where a scan of a repository's records past its first page is cut, to | ||
/// be read side by side: first letters of the hashes that end their keys. | ||
const CUTS: &str = "6cgkosw"; | ||
| ||
/// The ranges, as where each starts and the least key it holds, that the | ||
/// records of the repository `key` below `next` are read in, the highest | ||
/// first. | ||
fn ranges(key: &str, next: &str) -> Vec<(String, String)> { | ||
let cut = |c: char| format!("{key}.{c}"); | ||
let mut lows: Vec<String> = CUTS | ||
.chars() | ||
.map(cut) | ||
.filter(|c| c.as_str() < next) | ||
.collect(); | ||
lows.insert(0, format!("{key}.")); | ||
let starts: Vec<String> = lows.iter().skip(1).cloned().chain([next.into()]).collect(); | ||
let mut ranges: Vec<(String, String)> = starts.into_iter().zip(lows).collect(); | ||
ranges.reverse(); | ||
ranges | ||
} | ||
| ||
/// Everything a `list` needs, read in one round trip when the repository's | ||
/// key is cached. | ||
#[derive(Clone, Debug, Default)] | ||
| @@ -481,8 +502,42 @@ impl Remote { | ||
} | ||
} | ||
| ||
/// The records of `key`'s in `collection` from `start` down to `low`, | ||
/// newest first: one range of a scan read side by side with others. | ||
async fn scan_down<T: DeserializeOwned>( | ||
&self, | ||
collection: &str, | ||
key: &str, | ||
start: String, | ||
low: String, | ||
) -> Result<Vec<Stored<T>>> { | ||
let mut all = Vec::new(); | ||
let mut cursor = Some(start); | ||
while let Some(at) = cursor { | ||
let page = self.scan(collection, key, Some(&at)).await?; | ||
let past = page.items.last().is_some_and(|r| r.rkey < low); | ||
all.extend(page.items.into_iter().filter(|r| r.rkey >= low)); | ||
cursor = page.next.filter(|_| !past); | ||
} | ||
Ok(all) | ||
} | ||
| ||
/// Every ref record of the repository `key`, the deleted refs' among | ||
/// them. A repository keeps one for every branch it ever had, which | ||
/// a busy one counts in hundreds: past the first page, the rest are | ||
/// read as ranges of their keys side by side, rather than as pages one | ||
/// after another. | ||
pub async fn refs(&self, key: &str) -> Result<Vec<Stored<RefRecord>>> { | ||
self.scan_all(nsid::REF, key).await | ||
let first = self.scan(nsid::REF, key, None).await?; | ||
let Some(next) = first.next.clone() else { | ||
return Ok(first.items); | ||
}; | ||
let read = ranges(key, &next).into_iter(); | ||
let read = read.map(|(start, low)| self.scan_down(nsid::REF, key, start, low)); | ||
let rest = futures::future::try_join_all(read).await?; | ||
let mut all = first.items; | ||
all.extend(rest.into_iter().flatten()); | ||
Ok(all) | ||
} | ||
| ||
pub async fn packs(&self, key: &str, cursor: Option<&str>) -> Result<Page<PackRecord>> { | ||
| @@ -711,3 +766,27 @@ impl Remote { | ||
} | ||
} | ||
} | ||
| ||
#[cfg(test)] | ||
mod tests { | ||
use super::*; | ||
| ||
#[test] | ||
fn ranges_cover_what_is_below_the_first_page() { | ||
let pair = |a: &str, b: &str| (a.to_string(), b.to_string()); | ||
// From where the first page ended down to the least key, cut at each | ||
// letter below it, the highest range first. | ||
assert_eq!( | ||
ranges("k", "k.mz"), | ||
[ | ||
pair("k.mz", "k.k"), | ||
pair("k.k", "k.g"), | ||
pair("k.g", "k.c"), | ||
pair("k.c", "k.6"), | ||
pair("k.6", "k."), | ||
] | ||
); | ||
// Below every cut: one range. | ||
assert_eq!(ranges("k", "k.3a"), [pair("k.3a", "k.")]); | ||
} | ||
} | ||
docs/design/storage.md+8−0
| @@ -80,6 +80,14 @@ A ref record holds the full ref `name`, its `target` commit, and a | ||
moves. A deleted ref keeps its record with no target, so its generation never | ||
repeats. | ||
| ||
A repository therefore holds a ref record for every branch it ever had. A | ||
busy one holds hundreds, most of them deleted, and a read of its refs lists | ||
them all. Past the first page of 100, the rest of the range is cut by the | ||
first letter of the hash that ends each key and read in up to eight ranges | ||
side by side, not as pages one after another. On a repository with 590 ref | ||
records, this takes 0.37 seconds rather than 1.7. A repository whose refs | ||
fit on one page is read in one call, as before. | ||
| ||
A claim records one move of one ref. Its key ends in the generation the ref | ||
moved from, and its body holds `from`, `to` and the `pack` written with the | ||
move. A delete's has no `to`. A new ref has no claim: creating its record | ||