steid
Sign in

@jamesgill /

steid

steid/src/infrastructure/merge_cache.rs
Rust8.6 KBCode·Blame·History·Raw
1//! The answer `git merge-tree --write-tree` gave for one pair of commits, remembered.
2//!
3//! A pull request's Conversation tab asks whether its two branches merge on **every**
4//! view, and for the genuine three-way case that is a `merge-tree` per view: a full
5//! three-way merge in the object database, and — because `--write-tree` writes — a fresh
6//! set of blobs and trees that nothing references, every time somebody reloads the page.
7//! A conflicted request is the worst of it, since a conflict is exactly the state people
8//! sit on and refresh.
9//!
10//! Keyed by the **pair of commit ids**, which is what makes the entry safe rather than
11//! merely useful: git objects are content-addressed, so two commit ids determine their
12//! merge base, their trees and therefore their merge completely. Nothing about a
13//! repository can change the answer for a pair without changing one of the ids, so there
14//! is no invalidation problem and no staleness — the same property the highlight cache
15//! gets from keying on content.
16//!
17//! Bounded the way [`HighlightCache`](super::highlight::HighlightCache) is: an
18//! [`LruCache`] with no count limit and a byte budget enforced on insert. The budget is
19//! much smaller because the entries are: a clean answer is one object id, and a
20//! conflicted one is a list of paths.
21
22use std::sync::Mutex;
23
24use lru::LruCache;
25
26use crate::{application::port::MergePreview, domain::ObjectId, infrastructure::metrics::metrics};
27
28/// How much the process keeps before it starts evicting.
29///
30/// One mebibyte, which is thousands of clean answers or hundreds of conflicted ones. The
31/// working set this serves is small by nature — the open pull requests somebody is
32/// actually looking at — so a bigger budget would buy nothing a personal instance can
33/// use.
34const MAX_CACHE_BYTES: usize = 1024 * 1024;
35
36/// A rough per-entry overhead, charged so that an entry with one short path is not
37/// accounted as a handful of bytes. Not exact; the budget is a bound, not an audit.
38const PER_ENTRY_OVERHEAD: usize = 128;
39
40/// A pair of commits, in the order they were asked about.
41///
42/// Order matters: merging `main` into `spike` and `spike` into `main` are different
43/// questions with different conflict sides, so the pair is a key rather than a set.
44type Key = (ObjectId, ObjectId);
45
46/// Merge previews, remembered across requests.
47///
48/// One per process, in app context — a cache built per request would remember nothing,
49/// the same reason the `cat-file` pool and the highlight cache live there.
50///
51/// `Debug` prints the shape rather than the contents: `DiskGitQuery` derives it, and a
52/// dump of every remembered merge would be pages of object ids.
53pub struct MergeCache {
54 entries: Mutex<Entries>,
55}
56
57struct Entries {
58 cache: LruCache<Key, MergePreview>,
59 bytes: usize,
60}
61
62impl std::fmt::Debug for MergeCache {
63 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
64 let entries = self.lock();
65
66 f.debug_struct("MergeCache")
67 .field("entries", &entries.cache.len())
68 .field("bytes", &entries.bytes)
69 .finish()
70 }
71}
72
73impl Default for MergeCache {
74 fn default() -> Self {
75 Self::new()
76 }
77}
78
79impl MergeCache {
80 pub fn new() -> Self {
81 Self {
82 entries: Mutex::new(Entries {
83 // Unbounded by count; [`MAX_CACHE_BYTES`] is the real bound and is
84 // enforced on insert.
85 cache: LruCache::unbounded(),
86 bytes: 0,
87 }),
88 }
89 }
90
91 /// What this pair merged to last time, if it is still remembered.
92 pub fn get(&self, target: &ObjectId, source: &ObjectId) -> Option<MergePreview> {
93 let mut entries = self.lock();
94
95 let found = entries
96 .cache
97 .get(&(target.clone(), source.clone()))
98 .cloned();
99
100 // A miss is a `git merge-tree` about to run — a full three-way merge that writes
101 // objects nothing references — so the ratio between these two is the cost of the
102 // pull request pages, in processes.
103 match found.is_some() {
104 true => metrics().record_merge_hit(),
105 false => metrics().record_merge_miss(),
106 }
107
108 found
109 }
110
111 /// Remembers an answer.
112 pub fn put(&self, target: &ObjectId, source: &ObjectId, preview: MergePreview) {
113 let weight = weight_of(&preview);
114
115 // An entry bigger than the whole budget would evict everything and then itself.
116 // It is simply not cached — the highlight cache's rule.
117 if weight > MAX_CACHE_BYTES {
118 return;
119 }
120
121 let mut entries = self.lock();
122
123 if let Some(replaced) = entries.cache.put((target.clone(), source.clone()), preview) {
124 entries.bytes = entries.bytes.saturating_sub(weight_of(&replaced));
125 }
126 entries.bytes += weight;
127
128 while entries.bytes > MAX_CACHE_BYTES {
129 match entries.cache.pop_lru() {
130 Some((_, evicted)) => {
131 entries.bytes = entries.bytes.saturating_sub(weight_of(&evicted))
132 }
133 // Unreachable while the accounting is right, and a `break` rather than a
134 // panic if it ever is not: an over-counted cache holds less than it
135 // could, it does not fail a page.
136 None => break,
137 }
138 }
139 }
140
141 /// A poisoned lock means another thread panicked mid-insert. The cache holds nothing
142 /// anyone needs, so reading on is better than propagating a panic into a page — the
143 /// highlight cache's rule.
144 fn lock(&self) -> std::sync::MutexGuard<'_, Entries> {
145 match self.entries.lock() {
146 Ok(entries) => entries,
147 Err(poisoned) => poisoned.into_inner(),
148 }
149 }
150
151 /// How many entries and how many accounted bytes are held.
152 ///
153 /// Public for `/metrics`, which reports the bytes as `steid_cache_bytes`, and read by
154 /// the tests below — the same reasoning as
155 /// [`HighlightCache::stats`](super::highlight::HighlightCache::stats).
156 #[must_use]
157 pub fn stats(&self) -> (usize, usize) {
158 let entries = self.lock();
159 (entries.cache.len(), entries.bytes)
160 }
161}
162
163/// What an entry is charged against the budget.
164fn weight_of(preview: &MergePreview) -> usize {
165 let paths = match preview {
166 MergePreview::Clean { .. } => 0,
167 MergePreview::Conflicted { paths } => paths.iter().map(|path| path.len() + 16).sum(),
168 };
169
170 paths + PER_ENTRY_OVERHEAD
171}
172
173#[cfg(test)]
174mod tests {
175 use super::*;
176
177 fn oid(byte: char) -> ObjectId {
178 ObjectId::new(byte.to_string().repeat(40)).expect("valid id")
179 }
180
181 fn clean() -> MergePreview {
182 MergePreview::Clean { tree: oid('c') }
183 }
184
185 #[test]
186 fn an_answer_comes_back_for_the_pair_it_was_stored_under() {
187 let cache = MergeCache::new();
188 cache.put(&oid('a'), &oid('b'), clean());
189
190 assert_eq!(cache.get(&oid('a'), &oid('b')), Some(clean()));
191 }
192
193 #[test]
194 fn the_pair_is_ordered() {
195 // Merging main into spike is not the same question as the other way round, and
196 // answering one with the other's result would show the wrong conflicts.
197 let cache = MergeCache::new();
198 cache.put(&oid('a'), &oid('b'), clean());
199
200 assert_eq!(cache.get(&oid('b'), &oid('a')), None);
201 }
202
203 #[test]
204 fn an_answer_larger_than_the_whole_budget_is_not_cached() {
205 // Caching it would evict everything and then itself.
206 let cache = MergeCache::new();
207 cache.put(
208 &oid('a'),
209 &oid('b'),
210 MergePreview::Conflicted {
211 paths: vec!["x".repeat(MAX_CACHE_BYTES); 1],
212 },
213 );
214
215 assert_eq!(cache.stats(), (0, 0));
216 }
217
218 #[test]
219 fn a_repeated_pair_is_one_entry_and_one_charge() {
220 let cache = MergeCache::new();
221
222 for _ in 0..5 {
223 cache.put(&oid('a'), &oid('b'), clean());
224 }
225
226 let (entries, bytes) = cache.stats();
227 assert_eq!(entries, 1);
228 assert_eq!(bytes, weight_of(&clean()));
229 }
230
231 #[test]
232 fn the_budget_evicts_the_least_recently_used() {
233 let cache = MergeCache::new();
234 // Two-thirds of the budget each, so the second insert must push the first out.
235 let big = || MergePreview::Conflicted {
236 paths: vec!["x".repeat(MAX_CACHE_BYTES * 2 / 3); 1],
237 };
238
239 cache.put(&oid('a'), &oid('b'), big());
240 cache.put(&oid('c'), &oid('d'), big());
241
242 assert_eq!(cache.stats().0, 1);
243 assert_eq!(cache.get(&oid('a'), &oid('b')), None);
244 assert!(cache.get(&oid('c'), &oid('d')).is_some());
245 }
246}