kevy_cli/backfill_keys.rs
1//! `backfill-keys` — the union of every structure that can name an item.
2//!
3//! Lesson 3 of the migration playbook, and only the half a machine can
4//! do. The lesson splits itself: *"build the backfill key-set from the
5//! **union** of every structure that can name an item (old indexes, the
6//! primary keyspace scan, archives), then write rows from the
7//! authoritative record."* The union is mechanical. What the
8//! authoritative record is, and what a row looks like, is knowledge
9//! that lives in the application — a tool that guessed would write the
10//! wrong rows confidently.
11//!
12//! So this command produces the key-set and nothing else, and it splits
13//! its output the way a pipeline needs: **the names go to stdout**, one
14//! per line, ready to feed whatever writes the rows; **the accounting
15//! goes to stderr**, so redirecting the list does not lose it.
16//!
17//! The accounting is the point of doing this at all. Each source
18//! reports how many names *only it* contributed — and every non-zero
19//! number there is a row that backfilling from any single source would
20//! have missed. That is the 89 % / 76 % drift the lesson was paid for,
21//! measured on your own data instead of quoted from someone else's.
22//!
23//! ```
24//! use kevy_cli::backfill_keys::{Source, collect};
25//! # let port = include!(concat!(env!("CARGO_MANIFEST_DIR"), "/tests/doc_server/serve.rs"));
26//! let mut client = kevy_resp_client::RespClient::connect("127.0.0.1", port)?;
27//! // The index lost item 3; the keyspace still has it.
28//! client.request_borrowed(&[b"ZADD", b"idx:mail-by-date", b"1", b"1", b"2", b"2"])?;
29//! for id in ["1", "2", "3"] {
30//! client.request_borrowed(&[b"SET", format!("mail:{id}").as_bytes(), b"body"])?;
31//! }
32//! let sources = [
33//! Source::Index("idx:mail-by-date".into()),
34//! Source::Prefix { prefix: "mail:".into(), keep: false },
35//! ];
36//! let union = collect(&mut client, &sources)?;
37//! assert!(union.names.contains(&b"3".to_vec()), "the union has what the index lost");
38//! assert_eq!(union.sources[1].unique, 1, "only the keyspace named item 3");
39//! # Ok::<(), Box<dyn std::error::Error>>(())
40//! ```
41
42// The progress report goes to stderr, and a stderr that has gone away
43// (a closed pipe, `| head`) is not a reason to abandon a backfill that
44// is otherwise succeeding. What matters is written to the store.
45#![expect(clippy::let_underscore_must_use, reason = "a report nobody is reading is not a failure")]
46
47use std::collections::BTreeSet;
48use std::io::{self, Write};
49use std::process::ExitCode;
50
51use crate::link::Link;
52
53/// Where a set of item names comes from.
54///
55/// ```
56/// use kevy_cli::backfill_keys::Source;
57/// // `--from-index mail:by-date --from-prefix mail: --from-file archive.txt`
58/// let sources = [
59/// Source::Index("mail:by-date".into()),
60/// Source::Prefix { prefix: "mail:".into(), keep: false },
61/// Source::File("archive.txt".into()),
62/// ];
63/// let labels: Vec<String> = sources.iter().map(Source::label).collect();
64/// assert_eq!(labels, ["index mail:by-date", "prefix mail:", "file archive.txt"]);
65/// ```
66#[derive(Debug, Clone, PartialEq, Eq, Hash)]
67#[non_exhaustive]
68pub enum Source {
69 /// The members of a set, sorted set, or list key.
70 ///
71 /// ```
72 /// use kevy_cli::backfill_keys::{Source, collect};
73 /// # let port = include!(concat!(env!("CARGO_MANIFEST_DIR"), "/tests/doc_server/serve.rs"));
74 /// let mut client = kevy_resp_client::RespClient::connect("127.0.0.1", port)?;
75 /// client.request_borrowed(&[b"SADD", b"tags:rust", b"a", b"b"])?;
76 /// let u = collect(&mut client, &[Source::Index("tags:rust".into())])?;
77 /// assert_eq!(u.names.len(), 2);
78 /// # Ok::<(), Box<dyn std::error::Error>>(())
79 /// ```
80 Index(String),
81 /// Every key in the keyspace under a prefix.
82 ///
83 /// ```
84 /// use kevy_cli::backfill_keys::{Source, collect};
85 /// # let port = include!(concat!(env!("CARGO_MANIFEST_DIR"), "/tests/doc_server/serve.rs"));
86 /// let mut client = kevy_resp_client::RespClient::connect("127.0.0.1", port)?;
87 /// client.request_borrowed(&[b"SET", b"user:7", b"x"])?;
88 /// let source = Source::Prefix { prefix: "user:".into(), keep: false };
89 /// assert_eq!(collect(&mut client, &[source])?.names, vec![b"7".to_vec()]);
90 /// # Ok::<(), Box<dyn std::error::Error>>(())
91 /// ```
92 Prefix {
93 /// The prefix to scan.
94 ///
95 /// ```
96 /// use kevy_cli::backfill_keys::Source;
97 /// let s = Source::Prefix { prefix: "order:".into(), keep: false };
98 /// assert_eq!(s.label(), "prefix order:");
99 /// ```
100 prefix: String,
101 /// Keep the whole key rather than stripping the prefix.
102 ///
103 /// Stripping is the default because the names then line up with
104 /// the members of an index: `mail:123` under `mail:` becomes
105 /// `123`, which is what a sorted set of ids holds. Keeping the
106 /// prefix is right when the key *is* the name.
107 ///
108 /// ```
109 /// use kevy_cli::backfill_keys::{Source, collect};
110 /// # let port = include!(concat!(env!("CARGO_MANIFEST_DIR"), "/tests/doc_server/serve.rs"));
111 /// let mut client = kevy_resp_client::RespClient::connect("127.0.0.1", port)?;
112 /// client.request_borrowed(&[b"SET", b"mail:123", b"x"])?;
113 /// let stripped = Source::Prefix { prefix: "mail:".into(), keep: false };
114 /// let whole = Source::Prefix { prefix: "mail:".into(), keep: true };
115 /// assert_eq!(collect(&mut client, &[stripped])?.names, vec![b"123".to_vec()]);
116 /// assert_eq!(collect(&mut client, &[whole])?.names, vec![b"mail:123".to_vec()]);
117 /// # Ok::<(), Box<dyn std::error::Error>>(())
118 /// ```
119 keep: bool,
120 },
121 /// One name per line, from a file (an archive listing, an export).
122 ///
123 /// ```
124 /// use kevy_cli::backfill_keys::{Source, collect};
125 /// # let port = include!(concat!(env!("CARGO_MANIFEST_DIR"), "/tests/doc_server/serve.rs"));
126 /// let mut client = kevy_resp_client::RespClient::connect("127.0.0.1", port)?;
127 /// let dir = kevy_tmpdir::TmpDir::new("backfill-file");
128 /// let listing = dir.path().join("archive.txt");
129 /// std::fs::write(&listing, "41\n\n42\n")?; // blank lines are skipped
130 /// let source = Source::File(listing.to_string_lossy().into_owned());
131 /// let u = collect(&mut client, &[source])?;
132 /// assert_eq!(u.names, vec![b"41".to_vec(), b"42".to_vec()]);
133 /// # Ok::<(), Box<dyn std::error::Error>>(())
134 /// ```
135 File(String),
136}
137
138impl Source {
139 /// How this source prints in the report.
140 ///
141 /// ```
142 /// use kevy_cli::backfill_keys::Source;
143 /// assert_eq!(Source::Index("by-date".into()).label(), "index by-date");
144 /// let whole = Source::Prefix { prefix: "mail:".into(), keep: true };
145 /// assert_eq!(whole.label(), "prefix mail: (whole keys)");
146 /// assert_eq!(Source::File("ids.txt".into()).label(), "file ids.txt");
147 /// ```
148 pub fn label(&self) -> String {
149 match self {
150 Source::Index(k) => format!("index {k}"),
151 Source::Prefix { prefix, keep } => {
152 format!("prefix {prefix}{}", if *keep { " (whole keys)" } else { "" })
153 }
154 Source::File(p) => format!("file {p}"),
155 }
156 }
157}
158
159/// What one source contributed.
160///
161/// ```
162/// use kevy_cli::backfill_keys::{Source, collect};
163/// # let port = include!(concat!(env!("CARGO_MANIFEST_DIR"), "/tests/doc_server/serve.rs"));
164/// let mut client = kevy_resp_client::RespClient::connect("127.0.0.1", port)?;
165/// client.request_borrowed(&[b"SADD", b"a", b"1", b"2"])?;
166/// client.request_borrowed(&[b"SADD", b"b", b"2", b"3"])?;
167/// let u = collect(&mut client, &[Source::Index("a".into()), Source::Index("b".into())])?;
168/// let r = &u.sources[0];
169/// assert_eq!((r.label.as_str(), r.total, r.unique), ("index a", 2, 1));
170/// # Ok::<(), Box<dyn std::error::Error>>(())
171/// ```
172#[derive(Debug, Clone, PartialEq, Eq, Hash, Default)]
173#[non_exhaustive]
174pub struct SourceReport {
175 /// How the source was named on the command line.
176 ///
177 /// ```
178 /// use kevy_cli::backfill_keys::{Source, collect};
179 /// # let port = include!(concat!(env!("CARGO_MANIFEST_DIR"), "/tests/doc_server/serve.rs"));
180 /// let mut client = kevy_resp_client::RespClient::connect("127.0.0.1", port)?;
181 /// client.request_borrowed(&[b"SADD", b"ids", b"1"])?;
182 /// let u = collect(&mut client, &[Source::Index("ids".into())])?;
183 /// assert_eq!(u.sources[0].label, "index ids");
184 /// # Ok::<(), Box<dyn std::error::Error>>(())
185 /// ```
186 pub label: String,
187 /// Names this source produced.
188 ///
189 /// ```
190 /// use kevy_cli::backfill_keys::{Source, collect};
191 /// # let port = include!(concat!(env!("CARGO_MANIFEST_DIR"), "/tests/doc_server/serve.rs"));
192 /// let mut client = kevy_resp_client::RespClient::connect("127.0.0.1", port)?;
193 /// client.request_borrowed(&[b"RPUSH", b"queue", b"x", b"y", b"z"])?;
194 /// let u = collect(&mut client, &[Source::Index("queue".into())])?;
195 /// assert_eq!(u.sources[0].total, 3);
196 /// # Ok::<(), Box<dyn std::error::Error>>(())
197 /// ```
198 pub total: usize,
199 /// Names **no other source** produced. Non-zero means backfilling
200 /// from any single source would have missed these rows.
201 ///
202 /// ```
203 /// use kevy_cli::backfill_keys::{Source, collect};
204 /// # let port = include!(concat!(env!("CARGO_MANIFEST_DIR"), "/tests/doc_server/serve.rs"));
205 /// let mut client = kevy_resp_client::RespClient::connect("127.0.0.1", port)?;
206 /// client.request_borrowed(&[b"SADD", b"old", b"1", b"2"])?;
207 /// client.request_borrowed(&[b"SADD", b"new", b"1", b"2", b"9"])?;
208 /// let u = collect(&mut client, &[Source::Index("old".into()), Source::Index("new".into())])?;
209 /// assert_eq!(u.sources[0].unique, 0, "the old index alone misses nothing");
210 /// assert_eq!(u.sources[1].unique, 1, "only the new one names 9");
211 /// # Ok::<(), Box<dyn std::error::Error>>(())
212 /// ```
213 pub unique: usize,
214}
215
216/// The union, and where each name came from.
217///
218/// ```
219/// use kevy_cli::backfill_keys::{Source, collect};
220/// # let port = include!(concat!(env!("CARGO_MANIFEST_DIR"), "/tests/doc_server/serve.rs"));
221/// let mut client = kevy_resp_client::RespClient::connect("127.0.0.1", port)?;
222/// client.request_borrowed(&[b"SADD", b"a", b"1"])?;
223/// client.request_borrowed(&[b"SADD", b"b", b"1", b"2"])?;
224/// let u = collect(&mut client, &[Source::Index("a".into()), Source::Index("b".into())])?;
225/// assert_eq!((u.names.len(), u.sources.len()), (2, 2));
226/// # Ok::<(), Box<dyn std::error::Error>>(())
227/// ```
228#[derive(Debug, Clone, PartialEq, Eq, Hash, Default)]
229#[non_exhaustive]
230pub struct Union {
231 /// Every name, first-seen order, deduplicated.
232 ///
233 /// ```
234 /// use kevy_cli::backfill_keys::{Source, collect};
235 /// # let port = include!(concat!(env!("CARGO_MANIFEST_DIR"), "/tests/doc_server/serve.rs"));
236 /// let mut client = kevy_resp_client::RespClient::connect("127.0.0.1", port)?;
237 /// client.request_borrowed(&[b"RPUSH", b"first", b"b", b"a"])?;
238 /// client.request_borrowed(&[b"RPUSH", b"second", b"a", b"c"])?;
239 /// let sources = [Source::Index("first".into()), Source::Index("second".into())];
240 /// let u = collect(&mut client, &sources)?;
241 /// assert_eq!(u.names, vec![b"b".to_vec(), b"a".to_vec(), b"c".to_vec()]);
242 /// # Ok::<(), Box<dyn std::error::Error>>(())
243 /// ```
244 pub names: Vec<Vec<u8>>,
245 /// One entry per source, in the order they were given.
246 ///
247 /// ```
248 /// use kevy_cli::backfill_keys::{Source, collect};
249 /// # let port = include!(concat!(env!("CARGO_MANIFEST_DIR"), "/tests/doc_server/serve.rs"));
250 /// let mut client = kevy_resp_client::RespClient::connect("127.0.0.1", port)?;
251 /// client.request_borrowed(&[b"SADD", b"x", b"1"])?;
252 /// client.request_borrowed(&[b"SADD", b"y", b"1"])?;
253 /// let u = collect(&mut client, &[Source::Index("y".into()), Source::Index("x".into())])?;
254 /// let labels: Vec<_> = u.sources.iter().map(|s| s.label.as_str()).collect();
255 /// assert_eq!(labels, ["index y", "index x"]);
256 /// # Ok::<(), Box<dyn std::error::Error>>(())
257 /// ```
258 pub sources: Vec<SourceReport>,
259}
260
261/// Read every source and union their names.
262///
263/// A source that cannot be read is an error, never an empty
264/// contribution:
265///
266/// ```
267/// use kevy_cli::backfill_keys::{Source, collect};
268/// # let port = include!(concat!(env!("CARGO_MANIFEST_DIR"), "/tests/doc_server/serve.rs"));
269/// let mut client = kevy_resp_client::RespClient::connect("127.0.0.1", port)?;
270/// client.request_borrowed(&[b"ZADD", b"by-date", b"1", b"m1"])?;
271/// let u = collect(&mut client, &[Source::Index("by-date".into())])?;
272/// assert_eq!(u.names, vec![b"m1".to_vec()]);
273///
274/// let err = collect(&mut client, &[Source::Index("no-such-index".into())]).unwrap_err();
275/// assert!(err.to_string().contains("does not exist"));
276/// # Ok::<(), Box<dyn std::error::Error>>(())
277/// ```
278pub fn collect(client: &mut dyn Link, sources: &[Source]) -> io::Result<Union> {
279 let mut per_source: Vec<BTreeSet<Vec<u8>>> = Vec::with_capacity(sources.len());
280 let mut names: Vec<Vec<u8>> = Vec::new();
281 let mut seen: BTreeSet<Vec<u8>> = BTreeSet::new();
282 for s in sources {
283 let got = read_source(client, s)?;
284 for n in &got {
285 if seen.insert(n.clone()) {
286 names.push(n.clone());
287 }
288 }
289 per_source.push(got.into_iter().collect());
290 }
291 let labels: Vec<String> = sources.iter().map(Source::label).collect();
292 Ok(Union { names, sources: account(&labels, &per_source) })
293}
294
295/// Who contributed what. A name is *unique* to a source when no other
296/// source produced it — which is the only number here worth reading,
297/// because each one is a row that backfilling from a single source
298/// would have missed.
299fn account(labels: &[String], per_source: &[BTreeSet<Vec<u8>>]) -> Vec<SourceReport> {
300 labels
301 .iter()
302 .zip(per_source)
303 .enumerate()
304 .map(|(i, (label, mine))| SourceReport {
305 label: label.clone(),
306 total: mine.len(),
307 unique: mine
308 .iter()
309 .filter(|n| !per_source.iter().enumerate().any(|(j, o)| j != i && o.contains(*n)))
310 .count(),
311 })
312 .collect()
313}
314
315fn read_source(client: &mut dyn Link, s: &Source) -> io::Result<Vec<Vec<u8>>> {
316 match s {
317 Source::Index(key) => crate::collections::members(client, key),
318 Source::Prefix { prefix, keep } => read_prefix(client, prefix, *keep),
319 Source::File(path) => Ok(std::fs::read_to_string(path)?
320 .lines()
321 .map(str::trim)
322 .filter(|l| !l.is_empty())
323 .map(|l| l.as_bytes().to_vec())
324 .collect()),
325 }
326}
327
328/// Every key under a prefix, stripped unless the caller wants the key
329/// itself: stripped names line up with the members of an index, which
330/// is what makes the union meaningful.
331fn read_prefix(client: &mut dyn Link, prefix: &str, keep: bool) -> io::Result<Vec<Vec<u8>>> {
332 Ok(crate::collections::scan_prefix(client, prefix)?
333 .into_iter()
334 .map(|k| if keep { k } else { k[prefix.len().min(k.len())..].to_vec() })
335 .collect())
336}
337
338/// The accounting, on stderr so redirecting the names keeps it.
339///
340/// ```
341/// use kevy_cli::backfill_keys::{Source, collect, print_report};
342/// # let port = include!(concat!(env!("CARGO_MANIFEST_DIR"), "/tests/doc_server/serve.rs"));
343/// let mut client = kevy_resp_client::RespClient::connect("127.0.0.1", port)?;
344/// client.request_borrowed(&[b"SADD", b"ids", b"1", b"2"])?;
345/// let u = collect(&mut client, &[Source::Index("ids".into())])?;
346/// for name in &u.names {
347/// println!("{}", String::from_utf8_lossy(name)); // stdout: the key-set
348/// }
349/// print_report(&u); // stderr: "2 name(s) in the union", then one line per source
350/// # Ok::<(), Box<dyn std::error::Error>>(())
351/// ```
352pub fn print_report(u: &Union) {
353 let e = io::stderr();
354 let mut e = e.lock();
355 let _ = writeln!(e, "{} name(s) in the union", u.names.len());
356 for s in &u.sources {
357 let _ = writeln!(e, " {:<32} {} name(s), {} only here", s.label, s.total, s.unique);
358 }
359 let missed: usize = u.sources.iter().map(|s| s.unique).sum();
360 let _ = if missed == 0 && u.sources.len() > 1 {
361 writeln!(e, "every source named the same items — no source alone would have missed a row")
362 } else if u.sources.len() > 1 {
363 writeln!(
364 e,
365 "{missed} name(s) appear in only one source — backfilling from any single one \
366 would have missed them"
367 )
368 } else {
369 writeln!(e, "one source given; there is nothing to union it against")
370 };
371}
372
373/// The sources, in the order given.
374fn parse_args(args: &[String]) -> Result<Vec<Source>, String> {
375 let (mut sources, mut keep) = (Vec::new(), false);
376 let mut scan = crate::tools::argscan::Scan::new(args);
377 while let Some(word) = scan.next() {
378 match word {
379 "--keep-prefix" => keep = true,
380 "--from-index" => sources.push(Source::Index(scan.value(word)?.to_string())),
381 "--from-prefix" => {
382 sources.push(Source::Prefix { prefix: scan.value(word)?.to_string(), keep: false })
383 }
384 "--from-file" => sources.push(Source::File(scan.value(word)?.to_string())),
385 other => return Err(crate::tools::argscan::unexpected(other)),
386 }
387 }
388 if sources.is_empty() {
389 return Err("give at least one source".into());
390 }
391 if keep {
392 for s in &mut sources {
393 if let Source::Prefix { keep: k, .. } = s {
394 *k = true;
395 }
396 }
397 }
398 Ok(sources)
399}
400
401/// `backfill-keys --from-index K --from-prefix P [--keep-prefix]
402/// --from-file F …` on `client`. Names to stdout, accounting to stderr. A
403/// source that cannot be read is an error rather than an empty
404/// contribution — a silently empty source is exactly the hole this command
405/// exists to close.
406pub(crate) fn run_on(client: &mut dyn Link, args: &[String]) -> ExitCode {
407 let sources = match parse_args(args) {
408 Ok(s) => s,
409 Err(msg) => {
410 eprintln!("kevy-cli backfill-keys: {msg}");
411 eprintln!(
412 "usage: kevy-cli --kevy backfill-keys [--from-index <key>] \
413 [--from-prefix <p> [--keep-prefix]] [--from-file <path>] …"
414 );
415 return ExitCode::FAILURE;
416 }
417 };
418 let u = match collect(client, &sources) {
419 Ok(u) => u,
420 Err(e) => {
421 eprintln!("kevy-cli backfill-keys: {e}");
422 return ExitCode::FAILURE;
423 }
424 };
425 let out = io::stdout();
426 let mut out = out.lock();
427 for n in &u.names {
428 let _ = out.write_all(n);
429 let _ = out.write_all(b"\n");
430 }
431 let _ = out.flush();
432 print_report(&u);
433 ExitCode::SUCCESS
434}
435
436#[cfg(test)]
437mod tests {
438 use super::*;
439
440 fn set(names: &[&str]) -> BTreeSet<Vec<u8>> {
441 names.iter().map(|n| n.as_bytes().to_vec()).collect()
442 }
443
444 fn labels(n: usize) -> Vec<String> {
445 (0..n).map(|i| format!("s{i}")).collect()
446 }
447
448 /// A name is unique to a source when no *other* source has it —
449 /// the number that says "backfilling from this one alone would
450 /// have missed these".
451 #[test]
452 fn unique_means_no_other_source_named_it() {
453 let sources =
454 [set(&["1", "2", "3"]), set(&["3", "4", "7"]), set(&["1", "2", "3", "4", "5"])];
455 let r = account(&labels(3), &sources);
456 assert_eq!((r[0].total, r[0].unique), (3, 0), "all of s0 is covered elsewhere");
457 assert_eq!((r[1].total, r[1].unique), (3, 1), "only s1 names 7");
458 assert_eq!((r[2].total, r[2].unique), (5, 1), "only s2 names 5");
459 }
460
461 /// Sources that agree contribute nothing unique — which is the
462 /// answer that means the drift this lesson warns about is absent.
463 #[test]
464 fn sources_that_agree_have_nothing_unique() {
465 let sources = [set(&["a", "b"]), set(&["b", "a"])];
466 for r in account(&labels(2), &sources) {
467 assert_eq!(r.unique, 0);
468 }
469 }
470
471 /// With one source there is nothing to be unique against, so every
472 /// name is — the report says so in words rather than letting the
473 /// number read as drift.
474 #[test]
475 fn a_lone_source_owns_everything_it_names() {
476 let r = account(&labels(1), &[set(&["a", "b"])]);
477 assert_eq!((r[0].total, r[0].unique), (2, 2));
478 }
479}