Skip to main content

spec_stream_cache/
table.rs

1use crate::allocator::{compute_block_prefix_hash, BlockAllocator};
2use crate::block::PhysicalBlockId;
3use crate::error::CacheError;
4use spec_stream_core::TokenId;
5
6/// Virtual-to-Physical block mapping table for a single sequence or request.
7#[derive(Debug, Clone)]
8pub struct BlockTable {
9    /// Ordered list of physical blocks allocated to this sequence.
10    pub physical_blocks: Vec<PhysicalBlockId>,
11    /// Prefix hash of each committed block in this sequence.
12    pub prefix_hashes: Vec<u64>,
13    /// Number of tokens currently registered in the sequence.
14    pub seq_len: usize,
15    /// Size of each block in tokens.
16    pub block_size: usize,
17}
18
19impl BlockTable {
20    pub fn new(block_size: usize) -> Self {
21        Self {
22            physical_blocks: Vec::new(),
23            prefix_hashes: Vec::new(),
24            seq_len: 0,
25            block_size,
26        }
27    }
28
29    /// Appends a new token to this sequence's KV-cache, allocating a block if needed
30    /// and performing Copy-on-Write if the target block is shared.
31    pub fn append_token(
32        &mut self,
33        token_id: TokenId,
34        allocator: &mut BlockAllocator,
35    ) -> Result<(), CacheError> {
36        // Check if we need to allocate a new physical block
37        if self.seq_len % self.block_size == 0 {
38            let block_id = allocator.allocate()?;
39            self.physical_blocks.push(block_id);
40        }
41
42        let last_idx = self.physical_blocks.len() - 1;
43        let current_block_id = self.physical_blocks[last_idx];
44
45        // Copy-on-Write: If block is currently shared (ref_count > 1), clone it first
46        let block_id_to_use = if allocator.get_block(current_block_id)?.ref_count > 1 {
47            let new_block_id = allocator.clone_block(current_block_id)?;
48            allocator.free(current_block_id)?;
49            self.physical_blocks[last_idx] = new_block_id;
50            new_block_id
51        } else {
52            current_block_id
53        };
54
55        let block = allocator.get_block_mut(block_id_to_use)?;
56        block.tokens.push(token_id);
57        block.num_tokens += 1;
58        self.seq_len += 1;
59
60        // If the block just became full, compute and register its prefix hash
61        if block.is_full() {
62            let parent_hash = self.prefix_hashes.last().copied();
63            let hash = compute_block_prefix_hash(parent_hash, &block.tokens);
64            self.prefix_hashes.push(hash);
65            allocator.register_prefix(hash, block_id_to_use);
66        }
67
68        Ok(())
69    }
70
71    /// Appends a slice of tokens in batch with automatic prefix cache matching.
72    pub fn append_tokens(
73        &mut self,
74        mut tokens: &[TokenId],
75        allocator: &mut BlockAllocator,
76    ) -> Result<(), CacheError> {
77        // 1. Fill any partial trailing block first
78        while !tokens.is_empty() && self.seq_len % self.block_size != 0 {
79            self.append_token(tokens[0], allocator)?;
80            tokens = &tokens[1..];
81        }
82
83        // 2. We are at a clean block boundary: attempt prefix cache lookups for full blocks
84        while tokens.len() >= self.block_size {
85            let chunk = &tokens[..self.block_size];
86            let parent_hash = self.prefix_hashes.last().copied();
87            let hash = compute_block_prefix_hash(parent_hash, chunk);
88
89            if let Some(shared_block_id) = allocator.find_prefix(hash) {
90                // Prefix Cache HIT! Reuse shared physical block without new allocation
91                self.physical_blocks.push(shared_block_id);
92                self.prefix_hashes.push(hash);
93                self.seq_len += self.block_size;
94            } else {
95                // Prefix Cache MISS: allocate new physical block and register it
96                let block_id = allocator.allocate()?;
97                {
98                    let block = allocator.get_block_mut(block_id)?;
99                    block.tokens.extend_from_slice(chunk);
100                    block.num_tokens = self.block_size;
101                }
102                allocator.register_prefix(hash, block_id);
103                self.physical_blocks.push(block_id);
104                self.prefix_hashes.push(hash);
105                self.seq_len += self.block_size;
106            }
107
108            tokens = &tokens[self.block_size..];
109        }
110
111        // 3. Append any trailing remaining tokens (< block_size)
112        for &t in tokens {
113            self.append_token(t, allocator)?;
114        }
115
116        Ok(())
117    }
118
119    /// Speculative Decoding Rollback:
120    /// Instantly rewinds the sequence to `valid_token_count` tokens.
121    /// Trailing unneeded blocks are freed, and partial boundary blocks undergo
122    /// Copy-on-Write if they were shared.
123    pub fn rollback(
124        &mut self,
125        valid_token_count: usize,
126        allocator: &mut BlockAllocator,
127    ) -> Result<usize, CacheError> {
128        if valid_token_count > self.seq_len {
129            return Err(CacheError::InvalidRollback {
130                target_len: valid_token_count,
131                current_len: self.seq_len,
132            });
133        }
134
135        let tokens_discarded = self.seq_len - valid_token_count;
136        if tokens_discarded == 0 {
137            return Ok(0);
138        }
139
140        // Calculate how many blocks should remain
141        let required_blocks = valid_token_count.div_ceil(self.block_size);
142
143        // Free trailing physical blocks that are no longer needed
144        while self.physical_blocks.len() > required_blocks {
145            let block_id = self.physical_blocks.pop().unwrap();
146            allocator.free(block_id)?;
147            if self.prefix_hashes.len() > self.physical_blocks.len() {
148                self.prefix_hashes.pop();
149            }
150        }
151
152        // Adjust the last block's token count if necessary
153        if let Some(&last_block_id) = self.physical_blocks.last() {
154            let tokens_in_last =
155                if valid_token_count % self.block_size == 0 && valid_token_count > 0 {
156                    self.block_size
157                } else {
158                    valid_token_count % self.block_size
159                };
160
161            // If last block was full and had registered prefix hash, but is now truncated:
162            if tokens_in_last < self.block_size
163                && self.prefix_hashes.len() == self.physical_blocks.len()
164            {
165                self.prefix_hashes.pop();
166            }
167
168            let last_idx = self.physical_blocks.len() - 1;
169            // Copy-on-Write: If the partial block is shared, clone it before truncating
170            let block_to_truncate = if allocator.get_block(last_block_id)?.ref_count > 1 {
171                let new_block_id = allocator.clone_block(last_block_id)?;
172                allocator.free(last_block_id)?;
173                self.physical_blocks[last_idx] = new_block_id;
174                new_block_id
175            } else {
176                last_block_id
177            };
178
179            let last_block = allocator.get_block_mut(block_to_truncate)?;
180            last_block.num_tokens = tokens_in_last;
181            last_block.tokens.truncate(tokens_in_last);
182            last_block.prefix_hash = None;
183        }
184
185        self.seq_len = valid_token_count;
186        Ok(tokens_discarded)
187    }
188
189    /// Translates a logical token position (0..seq_len) to its physical (block_id, offset) coordinates.
190    pub fn translate_logical_offset(
191        &self,
192        logical_index: usize,
193    ) -> Result<(PhysicalBlockId, usize), CacheError> {
194        if logical_index >= self.seq_len {
195            return Err(CacheError::IndexOutOfBounds {
196                index: logical_index,
197                length: self.seq_len,
198            });
199        }
200
201        let block_idx = logical_index / self.block_size;
202        let offset = logical_index % self.block_size;
203        Ok((self.physical_blocks[block_idx], offset))
204    }
205
206    /// Cleans up and frees all physical blocks allocated to this sequence.
207    pub fn free_all(&mut self, allocator: &mut BlockAllocator) -> Result<(), CacheError> {
208        for &block_id in &self.physical_blocks {
209            allocator.free(block_id)?;
210        }
211        self.physical_blocks.clear();
212        self.prefix_hashes.clear();
213        self.seq_len = 0;
214        Ok(())
215    }
216}
217
218#[cfg(test)]
219mod tests {
220    use super::*;
221
222    #[test]
223    fn test_prefix_caching_sharing() {
224        let block_size = 4;
225        let mut allocator = BlockAllocator::new(10, block_size);
226        let mut table1 = BlockTable::new(block_size);
227        let mut table2 = BlockTable::new(block_size);
228
229        let system_prompt = vec![101, 102, 103, 104]; // exactly 1 block
230
231        // First sequence populates the block
232        table1
233            .append_tokens(&system_prompt, &mut allocator)
234            .unwrap();
235        assert_eq!(allocator.num_free_blocks(), 9);
236        assert_eq!(allocator.num_prefix_entries(), 1);
237
238        // Second sequence with identical prompt should HIT prefix cache and allocate ZERO new blocks!
239        table2
240            .append_tokens(&system_prompt, &mut allocator)
241            .unwrap();
242        assert_eq!(allocator.num_free_blocks(), 9); // Still 9 free blocks!
243        assert_eq!(table1.physical_blocks[0], table2.physical_blocks[0]); // Shared physical block!
244        assert_eq!(
245            allocator
246                .get_block(table1.physical_blocks[0])
247                .unwrap()
248                .ref_count,
249            2
250        );
251
252        // Freeing table1 leaves block alive for table2
253        table1.free_all(&mut allocator).unwrap();
254        assert_eq!(allocator.num_free_blocks(), 9);
255        assert_eq!(
256            allocator
257                .get_block(table2.physical_blocks[0])
258                .unwrap()
259                .ref_count,
260            1
261        );
262
263        table2.free_all(&mut allocator).unwrap();
264        assert_eq!(allocator.num_free_blocks(), 10);
265    }
266
267    #[test]
268    fn test_copy_on_write() {
269        let block_size = 4;
270        let mut allocator = BlockAllocator::new(10, block_size);
271        let mut table1 = BlockTable::new(block_size);
272        let mut table2 = BlockTable::new(block_size);
273
274        let prompt = vec![1, 2, 3, 4];
275        table1.append_tokens(&prompt, &mut allocator).unwrap();
276        table2.append_tokens(&prompt, &mut allocator).unwrap();
277
278        // Both share block 0
279        let shared_id = table1.physical_blocks[0];
280        assert_eq!(table2.physical_blocks[0], shared_id);
281
282        // Now table2 appends a new token -> it will allocate block 1 for itself
283        table2.append_token(99, &mut allocator).unwrap();
284        assert_eq!(table2.seq_len, 5);
285        assert_eq!(table1.seq_len, 4);
286
287        // table2 rolls back to 3 tokens (which was inside the shared block)
288        table2.rollback(3, &mut allocator).unwrap();
289        // table2 should have performed Copy-on-Write on block 0!
290        assert_ne!(table1.physical_blocks[0], table2.physical_blocks[0]);
291        // Table 1 must still have its original 4 tokens
292        let block1 = allocator.get_block(table1.physical_blocks[0]).unwrap();
293        assert_eq!(block1.num_tokens, 4);
294        assert_eq!(block1.tokens, vec![1, 2, 3, 4]);
295
296        // Table 2 must have only 3 tokens
297        let block2 = allocator.get_block(table2.physical_blocks[0]).unwrap();
298        assert_eq!(block2.num_tokens, 3);
299        assert_eq!(block2.tokens, vec![1, 2, 3]);
300    }
301}