Skip to main content

kevy_cli/
shadow.rs

1//! `shadow` — run the old query and the new one side by side and say
2//! where they disagree.
3//!
4//! Lesson 4 of the migration playbook, which is the one that decides
5//! whether anyone dares cut over: *serve reads from the old path while
6//! computing the new answer beside it, and compare the **order** too,
7//! not just the membership.* Score drift produces identical sets in
8//! different orders, and a paginated UI turns that into user-visible
9//! churn.
10//!
11//! It also carries lesson 2 without being asked to. A writer nobody
12//! remembered to update shows up here as rows the new path is missing —
13//! which is the same signal `TABLE.VERIFY` reports after the fact, seen
14//! before the cutover instead of after.
15
16use std::io;
17
18use std::process::ExitCode;
19
20use kevy_resp_client::{Reply, RespClient};
21
22/// One side's reading of a reply: the row keys in order, each with the
23/// sort value it was ordered by (empty when the shape does not carry
24/// one).
25type Rows = Vec<(Vec<u8>, Vec<u8>)>;
26
27/// How to read a reply into rows. Guessing is not free here — reading
28/// `ZRANGE … WITHSCORES` as a plain list silently treats every score as
29/// a row key and reports a divergence on every sample — so the two
30/// ambiguous shapes are told apart by the caller, not by a heuristic.
31#[derive(Debug, Clone, Copy, PartialEq)]
32pub enum Shape {
33    /// `[cursor, [key, sortval, key, sortval, …]]` — kevy's paged
34    /// index reply. Detected, not declared: a two-element array whose
35    /// second element is an array cannot be anything else here.
36    Paged,
37    /// `[a, b, c, …]` — every element is a row key.
38    Flat,
39    /// `[member, score, member, score, …]` — `WITHSCORES` and friends.
40    Pairs,
41}
42
43/// Read a reply into ordered rows under `shape`. `Paged` is recognised
44/// from the reply itself, so passing `Flat` for a kevy index reply
45/// still does the right thing rather than reporting nonsense.
46pub fn rows_of(reply: &Reply, shape: Shape) -> Rows {
47    let Reply::Array(items) = reply else { return Vec::new() };
48    if let [Reply::Bulk(_), Reply::Array(inner)] = items.as_slice() {
49        return pairs(inner);
50    }
51    match shape {
52        Shape::Paged | Shape::Pairs => pairs(items),
53        Shape::Flat => items
54            .iter()
55            .filter_map(|r| match r {
56                Reply::Bulk(b) => Some((b.clone(), Vec::new())),
57                _ => None,
58            })
59            .collect(),
60    }
61}
62
63fn pairs(items: &[Reply]) -> Rows {
64    let bulks: Vec<&Vec<u8>> =
65        items.iter().filter_map(|r| if let Reply::Bulk(b) = r { Some(b) } else { None }).collect();
66    bulks
67        .chunks(2)
68        .map(|c| (c[0].clone(), c.get(1).map(|v| (*v).clone()).unwrap_or_default()))
69        .collect()
70}
71
72/// What one comparison found.
73#[derive(Debug)]
74pub struct Divergence {
75    /// Position of the first place the two orders differ.
76    pub at: usize,
77    /// The old side's row and the value it was ordered by.
78    pub old: Option<(Vec<u8>, Vec<u8>)>,
79    /// The new side's, at the same position.
80    pub new: Option<(Vec<u8>, Vec<u8>)>,
81}
82
83/// Rows the new side lacks, rows it invents, and the first ordering
84/// difference. Membership and order are reported separately because
85/// they fail for different reasons: a missing row is a writer nobody
86/// updated, a reordering is score drift.
87#[derive(Debug)]
88pub struct Compared {
89    /// Rows the old path returns and the new one does not.
90    pub missing: Vec<Vec<u8>>,
91    /// Rows the new path returns and the old one does not.
92    pub extra: Vec<Vec<u8>>,
93    /// The first position where the two orders differ, if any.
94    pub first: Option<Divergence>,
95}
96
97/// Compare two readings: what is missing, what is extra, and where the
98/// orders first part company.
99pub fn compare(old: &Rows, new: &Rows) -> Compared {
100    let old_set: std::collections::HashSet<&[u8]> = old.iter().map(|(k, _)| k.as_slice()).collect();
101    let new_set: std::collections::HashSet<&[u8]> = new.iter().map(|(k, _)| k.as_slice()).collect();
102    let missing = old
103        .iter()
104        .filter(|(k, _)| !new_set.contains(k.as_slice()))
105        .map(|(k, _)| k.clone())
106        .collect();
107    let extra = new
108        .iter()
109        .filter(|(k, _)| !old_set.contains(k.as_slice()))
110        .map(|(k, _)| k.clone())
111        .collect();
112    let mut first = None;
113    for i in 0..old.len().max(new.len()) {
114        if old.get(i).map(|(k, _)| k) != new.get(i).map(|(k, _)| k) {
115            first = Some(Divergence { at: i, old: old.get(i).cloned(), new: new.get(i).cloned() });
116            break;
117        }
118    }
119    Compared { missing, extra, first }
120}
121
122/// Outcome of a shadow run — the paste-able conclusion.
123#[derive(Debug)]
124pub struct ShadowReport {
125    /// How many times both sides were asked.
126    pub samples: u64,
127    /// How many of those disagreed in membership or order.
128    pub diverged: u64,
129    /// The first sample that disagreed, and how.
130    pub first: Option<(u64, Compared)>,
131}
132
133/// Run both commands `samples` times and compare each pair.
134///
135/// Both sides are issued on the same connection, back to back, so the
136/// window between them is as small as this can make it. A row written
137/// between the two reads shows up as a divergence, which is why a
138/// single disagreement is a lead rather than a verdict — the report
139/// carries the count so a rate can be read off it.
140pub fn run(
141    client: &mut RespClient,
142    old_cmd: &[Vec<u8>],
143    new_cmd: &[Vec<u8>],
144    old_shape: Shape,
145    new_shape: Shape,
146    samples: u64,
147) -> io::Result<ShadowReport> {
148    let mut report = ShadowReport { samples: 0, diverged: 0, first: None };
149    for i in 0..samples {
150        let old_ref: Vec<&[u8]> = old_cmd.iter().map(|a| a.as_slice()).collect();
151        let new_ref: Vec<&[u8]> = new_cmd.iter().map(|a| a.as_slice()).collect();
152        let old = rows_of(&client.request_borrowed(&old_ref)?, old_shape);
153        let new = rows_of(&client.request_borrowed(&new_ref)?, new_shape);
154        report.samples += 1;
155        let c = compare(&old, &new);
156        if !c.missing.is_empty() || !c.extra.is_empty() || c.first.is_some() {
157            report.diverged += 1;
158            if report.first.is_none() {
159                report.first = Some((i, c));
160            }
161        }
162    }
163    Ok(report)
164}
165
166/// Print the report the way lesson 4 asks for: the first divergence
167/// with **both** sort keys, because that one line names the drifting
168/// writer.
169pub fn print_report(r: &ShadowReport) {
170    let show = |b: &[u8]| String::from_utf8_lossy(b).into_owned();
171    match &r.first {
172        None => println!(
173            "shadow: {} samples, 0 divergences — the new path answers what the old one does",
174            r.samples
175        ),
176        Some((n, c)) => {
177            println!(
178                "shadow: {} samples, {} diverged (first at sample {})",
179                r.samples, r.diverged, n
180            );
181            if !c.missing.is_empty() {
182                println!(
183                    "  MISSING from the new path ({}): {}",
184                    c.missing.len(),
185                    c.missing.iter().take(5).map(|k| show(k)).collect::<Vec<_>>().join(", ")
186                );
187                println!("    a row the old path has and the new one does not is usually a writer");
188                println!(
189                    "    that was never updated — the same class TABLE.VERIFY's `missing` finds"
190                );
191            }
192            if !c.extra.is_empty() {
193                println!(
194                    "  EXTRA in the new path ({}): {}",
195                    c.extra.len(),
196                    c.extra.iter().take(5).map(|k| show(k)).collect::<Vec<_>>().join(", ")
197                );
198            }
199            if let Some(d) = &c.first {
200                let side = |x: &Option<(Vec<u8>, Vec<u8>)>| match x {
201                    Some((k, v)) if v.is_empty() => show(k),
202                    Some((k, v)) => format!("{} (sort {})", show(k), show(v)),
203                    None => "<past the end>".to_string(),
204                };
205                println!("  ORDER differs at position {}:", d.at);
206                println!("    old: {}", side(&d.old));
207                println!("    new: {}", side(&d.new));
208                println!("    identical sets in different orders is score drift, and a paged UI");
209                println!("    shows it to users as churn — compare the two sort values above");
210            }
211        }
212    }
213}
214
215/// `shadow [-h host] [-p port] --old "<cmd>" --new "<cmd>"
216/// [--old-pairs] [--new-flat] [--samples n]`
217///
218/// Both sides are whole commands, quoted, because the old path is
219/// whatever the application already runs — a ZRANGE, an LRANGE, a
220/// SMEMBERS — and the new one is an IDX.QUERY. Nothing here knows
221/// which; it compares the two orders of row keys they produce.
222/// Everything `shadow` takes from the command line.
223struct ShadowArgs {
224    host: String,
225    port: u16,
226    old: Option<String>,
227    new: Option<String>,
228    old_shape: Shape,
229    new_shape: Shape,
230    samples: u64,
231}
232
233fn parse_shadow_flags(args: &[String]) -> ShadowArgs {
234    // A kevy paged reply is recognised from its shape. The ambiguity
235    // that needs declaring is member/score pairs versus a plain list,
236    // and only on the old side in practice.
237    let mut a = ShadowArgs {
238        host: crate::DEFAULT_HOST.to_string(),
239        port: crate::DEFAULT_PORT,
240        old: None,
241        new: None,
242        old_shape: Shape::Flat,
243        new_shape: Shape::Paged,
244        samples: 1,
245    };
246    let mut i = 0;
247    while i < args.len() {
248        match args[i].as_str() {
249            "-h" if i + 1 < args.len() => {
250                a.host = args[i + 1].clone();
251                i += 2;
252            }
253            "-p" if i + 1 < args.len() => {
254                a.port = args[i + 1].parse().unwrap_or(crate::DEFAULT_PORT);
255                i += 2;
256            }
257            "--old" if i + 1 < args.len() => {
258                a.old = Some(args[i + 1].clone());
259                i += 2;
260            }
261            "--new" if i + 1 < args.len() => {
262                a.new = Some(args[i + 1].clone());
263                i += 2;
264            }
265            "--old-pairs" => {
266                a.old_shape = Shape::Pairs;
267                i += 1;
268            }
269            "--new-flat" => {
270                a.new_shape = Shape::Flat;
271                i += 1;
272            }
273            "--samples" if i + 1 < args.len() => {
274                a.samples = args[i + 1].parse().unwrap_or(1);
275                i += 2;
276            }
277            _ => i += 1,
278        }
279    }
280    a
281}
282
283/// `shadow [-h host] [-p port] --old "<cmd>" --new "<cmd>"
284/// [--old-pairs] [--new-flat] [--samples n]`
285///
286/// Both sides are whole commands, quoted, because the old path is
287/// whatever the application already runs — a ZRANGE, an LRANGE, a
288/// SMEMBERS — and the new one is an `IDX.QUERY`. Nothing here knows
289/// which; it compares the two orders of row keys they produce.
290///
291/// Exits non-zero on any divergence, so a cutover script can gate on
292/// it without parsing the text.
293pub fn run_shadow_cli(args: &[String]) -> ExitCode {
294    let ShadowArgs { host, port, old, new, old_shape, new_shape, samples } =
295        parse_shadow_flags(args);
296    let (Some(old), Some(new)) = (old, new) else {
297        eprintln!(
298            "usage: kevy-cli shadow [-h host] [-p port] --old \"<command>\" \
299             --new \"<command>\" [--old-pairs] [--new-flat] [--samples n]"
300        );
301        return ExitCode::FAILURE;
302    };
303    let split =
304        |s: &str| -> Vec<Vec<u8>> { s.split_whitespace().map(|t| t.as_bytes().to_vec()).collect() };
305    let mut client = match RespClient::connect(&host, port) {
306        Ok(c) => c,
307        Err(e) => {
308            eprintln!("kevy-cli: could not connect to {host}:{port}: {e}");
309            return ExitCode::FAILURE;
310        }
311    };
312    match run(&mut client, &split(&old), &split(&new), old_shape, new_shape, samples) {
313        Ok(report) => {
314            print_report(&report);
315            // A divergence is a finding, not a crash: exit non-zero so a
316            // cutover script can gate on it without parsing the text.
317            if report.diverged > 0 { ExitCode::FAILURE } else { ExitCode::SUCCESS }
318        }
319        Err(e) => {
320            eprintln!("kevy-cli shadow: {e}");
321            ExitCode::FAILURE
322        }
323    }
324}
325
326#[cfg(test)]
327mod tests {
328    use super::*;
329
330    fn bulk(s: &str) -> Reply {
331        Reply::Bulk(s.as_bytes().to_vec())
332    }
333
334    /// kevy's paged reply is recognised from its shape, so a caller who
335    /// never thought about shapes still gets rows rather than nonsense.
336    #[test]
337    fn a_paged_reply_is_read_without_being_declared() {
338        let reply = Reply::Array(vec![
339            bulk("0"),
340            Reply::Array(vec![bulk("u:1"), bulk("10"), bulk("u:2"), bulk("20")]),
341        ]);
342        let rows = rows_of(&reply, Shape::Flat); // deliberately the "wrong" shape
343        assert_eq!(rows.len(), 2);
344        assert_eq!(rows[0], (b"u:1".to_vec(), b"10".to_vec()));
345    }
346
347    /// The ambiguity that cannot be detected: member/score pairs look
348    /// exactly like a plain list. Reading WITHSCORES as flat would make
349    /// every score a row key and report a divergence on every sample.
350    #[test]
351    fn pairs_and_flat_are_told_apart_by_the_caller() {
352        let reply = Reply::Array(vec![bulk("u:1"), bulk("10"), bulk("u:2"), bulk("20")]);
353        assert_eq!(rows_of(&reply, Shape::Flat).len(), 4, "flat: four rows");
354        assert_eq!(rows_of(&reply, Shape::Pairs).len(), 2, "pairs: two rows with scores");
355    }
356
357    /// Lesson 2's consequence: a row the old path has and the new one
358    /// does not is a writer nobody updated.
359    #[test]
360    fn a_row_only_the_old_path_has_is_reported_missing() {
361        let old = vec![(b"u:1".to_vec(), vec![]), (b"u:2".to_vec(), vec![])];
362        let new = vec![(b"u:1".to_vec(), vec![])];
363        let c = compare(&old, &new);
364        assert_eq!(c.missing, vec![b"u:2".to_vec()]);
365        assert!(c.extra.is_empty());
366    }
367
368    /// Lesson 4's whole point: identical membership, different order.
369    /// Set comparison alone calls this a match.
370    #[test]
371    fn identical_sets_in_different_orders_still_diverge() {
372        let old = vec![(b"u:2".to_vec(), b"5".to_vec()), (b"u:1".to_vec(), b"10".to_vec())];
373        let new = vec![(b"u:1".to_vec(), b"10".to_vec()), (b"u:2".to_vec(), b"20".to_vec())];
374        let c = compare(&old, &new);
375        assert!(c.missing.is_empty() && c.extra.is_empty(), "same membership");
376        let d = c.first.expect("order must still diverge");
377        assert_eq!(d.at, 0);
378        // Both sort keys travel with it — that pair is what names the
379        // drifting writer.
380        assert_eq!(d.old.unwrap().1, b"5".to_vec());
381        assert_eq!(d.new.unwrap().1, b"10".to_vec());
382    }
383
384    #[test]
385    fn agreement_reports_nothing() {
386        let rows = vec![(b"u:1".to_vec(), b"10".to_vec())];
387        let c = compare(&rows, &rows);
388        assert!(c.missing.is_empty() && c.extra.is_empty() && c.first.is_none());
389    }
390}