dynamo-kv-router 1.4.0

KV Router - Radix tree for LLM KV cache routing
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

// SPDX-FileCopyrightText: Copyright (c) 2024-2026 NVIDIA CORPORATION & AFFILIATES. All rights reserved.
// SPDX-License-Identifier: Apache-2.0

/// Shared cursor state for monotonically increasing event streams.
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub enum CursorState {
    #[default]
    Initial,
    Live(u64),
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum CursorObservation {
    Initial { got: u64 },
    Contiguous { got: u64 },
    Gap { expected: u64, got: u64 },
    Stale { got: u64, last_applied: Option<u64> },
}

impl CursorState {
    #[must_use]
    pub fn last_applied_id(self) -> Option<u64> {
        match self {
            CursorState::Initial => None,
            CursorState::Live(id) => Some(id),
        }
    }

    #[must_use]
    pub fn observe(self, got: u64) -> CursorObservation {
        match self {
            CursorState::Initial => CursorObservation::Initial { got },
            CursorState::Live(last) if got <= last => CursorObservation::Stale {
                got,
                last_applied: Some(last),
            },
            CursorState::Live(last) if got == last + 1 => CursorObservation::Contiguous { got },
            CursorState::Live(last) => CursorObservation::Gap {
                expected: last + 1,
                got,
            },
        }
    }

    #[must_use]
    pub fn advance_to(self, id: u64) -> Self {
        let _ = self;
        CursorState::Live(id)
    }
}

#[cfg(test)]
mod tests {
    use super::{CursorObservation, CursorState};

    #[test]
    fn initial_observation_preserves_first_id() {
        assert_eq!(
            CursorState::Initial.observe(0),
            CursorObservation::Initial { got: 0 }
        );
        assert_eq!(
            CursorState::Initial.observe(5),
            CursorObservation::Initial { got: 5 }
        );
    }

    #[test]
    fn live_observation_detects_contiguous_gap_and_stale_ids() {
        assert_eq!(
            CursorState::Live(10).observe(11),
            CursorObservation::Contiguous { got: 11 }
        );
        assert_eq!(
            CursorState::Live(10).observe(15),
            CursorObservation::Gap {
                expected: 11,
                got: 15,
            }
        );
        assert_eq!(
            CursorState::Live(10).observe(10),
            CursorObservation::Stale {
                got: 10,
                last_applied: Some(10),
            }
        );
        assert_eq!(
            CursorState::Live(10).observe(9),
            CursorObservation::Stale {
                got: 9,
                last_applied: Some(10),
            }
        );
    }
}