Skip to main content

spec_stream_engine/
scheduler.rs

1use crate::error::EngineError;
2use crate::model::ModelEngine;
3use crate::pipeline::SpeculativeConfig;
4use crate::stream::GenerationEvent;
5use spec_stream_cache::PagedKvCacheManager;
6use spec_stream_core::{DraftProposal, Logits, SpeculativeMetrics, SpeculativeVerifier, TokenId};
7use std::collections::VecDeque;
8use std::sync::atomic::{AtomicUsize, Ordering};
9use std::sync::{Arc, Mutex as StdMutex};
10use tokio::sync::{mpsc, Mutex as AsyncMutex};
11use tokio::time::Instant;
12
13/// An incoming inference request submitted to the batch scheduler.
14pub struct QueuedRequest {
15    pub sequence_id: u64,
16    pub prompt: Vec<TokenId>,
17    pub config: SpeculativeConfig,
18    pub sender: mpsc::Sender<GenerationEvent>,
19    pub priority: usize,
20    pub created_at: Instant,
21}
22
23impl QueuedRequest {
24    pub fn new(
25        sequence_id: u64,
26        prompt: Vec<TokenId>,
27        config: SpeculativeConfig,
28        sender: mpsc::Sender<GenerationEvent>,
29    ) -> Self {
30        Self {
31            sequence_id,
32            prompt,
33            config,
34            sender,
35            priority: 0,
36            created_at: Instant::now(),
37        }
38    }
39}
40
41/// An active in-flight sequence currently participating in iteration-level batching.
42struct ActiveSequence {
43    sequence_id: u64,
44    current_prefix: Vec<TokenId>,
45    total_generated: usize,
46    config: SpeculativeConfig,
47    current_k: usize,
48    ema_acceptance: Option<f32>,
49    metrics: SpeculativeMetrics,
50    sender: mpsc::Sender<GenerationEvent>,
51}
52
53/// Real-time operational statistics of the continuous batch scheduler.
54#[derive(Debug, Clone, Default)]
55pub struct SchedulerStats {
56    pub active_sequences: usize,
57    pub queued_requests: usize,
58    pub completed_sequences: usize,
59    pub total_tokens_emitted: usize,
60    pub total_batch_steps: usize,
61}
62
63/// High-throughput continuous batch scheduler executing iteration-level speculative inference.
64/// Dynamically pools multiple concurrent requests into unified forward passes.
65pub struct ContinuousBatchScheduler<D: ModelEngine, T: ModelEngine> {
66    draft_model: Arc<AsyncMutex<D>>,
67    target_model: Arc<AsyncMutex<T>>,
68    cache_manager: Arc<PagedKvCacheManager>,
69    queue: Arc<StdMutex<VecDeque<QueuedRequest>>>,
70    active: Arc<StdMutex<Vec<ActiveSequence>>>,
71    max_batch_size: usize,
72    completed_counter: Arc<AtomicUsize>,
73    tokens_emitted_counter: Arc<AtomicUsize>,
74    batch_steps_counter: Arc<AtomicUsize>,
75}
76
77impl<D: ModelEngine + 'static, T: ModelEngine + 'static> ContinuousBatchScheduler<D, T> {
78    pub fn new(
79        draft_model: D,
80        target_model: T,
81        cache_manager: Arc<PagedKvCacheManager>,
82        max_batch_size: usize,
83    ) -> Self {
84        Self {
85            draft_model: Arc::new(AsyncMutex::new(draft_model)),
86            target_model: Arc::new(AsyncMutex::new(target_model)),
87            cache_manager,
88            queue: Arc::new(StdMutex::new(VecDeque::new())),
89            active: Arc::new(StdMutex::new(Vec::new())),
90            max_batch_size: max_batch_size.max(1),
91            completed_counter: Arc::new(AtomicUsize::new(0)),
92            tokens_emitted_counter: Arc::new(AtomicUsize::new(0)),
93            batch_steps_counter: Arc::new(AtomicUsize::new(0)),
94        }
95    }
96
97    /// Enqueues an inference request for continuous batch processing.
98    pub fn submit(&self, request: QueuedRequest) -> Result<(), EngineError> {
99        let mut queue = self.queue.lock().unwrap();
100        queue.push_back(request);
101        Ok(())
102    }
103
104    /// Number of requests currently waiting in the arrival queue.
105    pub fn queue_len(&self) -> usize {
106        self.queue.lock().unwrap().len()
107    }
108
109    /// Number of requests currently active in the generation batch.
110    pub fn active_len(&self) -> usize {
111        self.active.lock().unwrap().len()
112    }
113
114    /// Retrieves current scheduler telemetry.
115    pub fn stats(&self) -> SchedulerStats {
116        SchedulerStats {
117            active_sequences: self.active.lock().unwrap().len(),
118            queued_requests: self.queue.lock().unwrap().len(),
119            completed_sequences: self.completed_counter.load(Ordering::Relaxed),
120            total_tokens_emitted: self.tokens_emitted_counter.load(Ordering::Relaxed),
121            total_batch_steps: self.batch_steps_counter.load(Ordering::Relaxed),
122        }
123    }
124
125    /// Executes one iteration of continuous batching across all currently scheduled sequences.
126    /// Returns the total number of committed tokens produced across all sequences in this iteration.
127    pub async fn step_iteration(&self) -> Result<usize, EngineError> {
128        self.batch_steps_counter.fetch_add(1, Ordering::Relaxed);
129
130        // 1. Admission Control: Promote queued requests up to max_batch_size
131        {
132            let mut active = self.active.lock().unwrap();
133            let mut queue = self.queue.lock().unwrap();
134
135            while active.len() < self.max_batch_size && !queue.is_empty() {
136                // Check if the cache has sufficient blocks
137                if self.cache_manager.free_blocks() < 2 {
138                    break;
139                }
140
141                if let Some(req) = queue.pop_front() {
142                    self.cache_manager.create_sequence(req.sequence_id);
143                    let _ = self
144                        .cache_manager
145                        .append_tokens(req.sequence_id, &req.prompt);
146
147                    let initial_k = req.config.k_draft_tokens;
148                    active.push(ActiveSequence {
149                        sequence_id: req.sequence_id,
150                        current_prefix: req.prompt,
151                        total_generated: 0,
152                        config: req.config,
153                        current_k: initial_k,
154                        ema_acceptance: None,
155                        metrics: SpeculativeMetrics::new(),
156                        sender: req.sender,
157                    });
158                }
159            }
160        }
161
162        let num_active = self.active.lock().unwrap().len();
163        if num_active == 0 {
164            return Ok(0);
165        }
166
167        // 2. Draft Proposals Phase (per sequence)
168        struct SeqProposal {
169            seq_idx: usize,
170            last_token: TokenId,
171            proposal: DraftProposal,
172        }
173
174        let mut proposals = Vec::with_capacity(num_active);
175        {
176            let active = self.active.lock().unwrap();
177            for (idx, seq) in active.iter().enumerate() {
178                if let Some(&last_t) = seq.current_prefix.last() {
179                    proposals.push(SeqProposal {
180                        seq_idx: idx,
181                        last_token: last_t,
182                        proposal: DraftProposal::new(),
183                    });
184                }
185            }
186        }
187
188        // Generate draft tokens
189        for p in &mut proposals {
190            let k = self.active.lock().unwrap()[p.seq_idx].current_k;
191            let mut draft_token = p.last_token;
192
193            for _ in 0..k {
194                let logits = {
195                    let mut draft_guard = self.draft_model.lock().await;
196                    draft_guard.forward_token(draft_token).await?
197                };
198
199                let next_id = match logits.argmax() {
200                    Ok(id) => id,
201                    Err(_) => break,
202                };
203
204                let prob = logits
205                    .softmax()
206                    .ok()
207                    .and_then(|probs| probs.get(next_id as usize).copied())
208                    .unwrap_or(0.85);
209
210                p.proposal.push(next_id, prob);
211                draft_token = next_id;
212            }
213        }
214
215        // 3. Target Model Batch Forward Pass & Verification
216        let mut total_tokens_this_step = 0;
217        let mut finished_indices = Vec::new();
218
219        for p in proposals {
220            if p.proposal.is_empty() {
221                continue;
222            }
223
224            let proposed_ids = p.proposal.token_ids();
225            let seq_id = self.active.lock().unwrap()[p.seq_idx].sequence_id;
226            let _ = self.cache_manager.append_tokens(seq_id, &proposed_ids);
227
228            let mut target_inputs = Vec::with_capacity(proposed_ids.len() + 1);
229            target_inputs.push(p.last_token);
230            target_inputs.extend_from_slice(&proposed_ids);
231
232            let target_logits: Vec<Logits> = {
233                let mut target_guard = self.target_model.lock().await;
234                target_guard.forward_batch(&target_inputs).await?
235            };
236
237            let verifier = {
238                let active = self.active.lock().unwrap();
239                SpeculativeVerifier::new(active[p.seq_idx].config.strategy)
240            };
241
242            let verif_result = match verifier.verify(&p.proposal, &target_logits) {
243                Ok(r) => r,
244                Err(e) => {
245                    tracing::error!("Scheduler verification error: {:?}", e);
246                    continue;
247                }
248            };
249
250            // 4. KV-Cache Rollback & Commit in O(1)
251            let mut active = self.active.lock().unwrap();
252            let seq = &mut active[p.seq_idx];
253
254            let valid_tokens_to_keep = seq.current_prefix.len() + verif_result.accepted_count;
255            let _ = self
256                .cache_manager
257                .rollback_sequence(seq.sequence_id, valid_tokens_to_keep);
258            let _ = self
259                .cache_manager
260                .append_tokens(seq.sequence_id, &[verif_result.emitted_target_token]);
261
262            seq.metrics.record_cycle(
263                p.proposal.len(),
264                verif_result.accepted_count,
265                verif_result.total_tokens_produced,
266            );
267
268            // Emit accepted draft tokens
269            for &tok in &verif_result.accepted_tokens {
270                seq.current_prefix.push(tok);
271                seq.total_generated += 1;
272                total_tokens_this_step += 1;
273                let _ = seq.sender.try_send(GenerationEvent::Token {
274                    token_id: tok,
275                    is_draft: true,
276                });
277            }
278
279            // Emit target token
280            seq.current_prefix.push(verif_result.emitted_target_token);
281            seq.total_generated += 1;
282            total_tokens_this_step += 1;
283            let _ = seq.sender.try_send(GenerationEvent::Token {
284                token_id: verif_result.emitted_target_token,
285                is_draft: false,
286            });
287
288            // Adaptive K update
289            let acc_rate = verif_result.accepted_count as f32 / p.proposal.len().max(1) as f32;
290            let ema = match seq.ema_acceptance {
291                Some(prev) => 0.5 * acc_rate + 0.5 * prev,
292                None => acc_rate,
293            };
294            seq.ema_acceptance = Some(ema);
295
296            if seq.config.adaptive_k {
297                if ema >= 0.75 && seq.current_k < seq.config.max_k {
298                    seq.current_k += 1;
299                } else if ema <= 0.35 && seq.current_k > seq.config.min_k {
300                    seq.current_k -= 1;
301                }
302            }
303
304            // Check termination conditions
305            let eos_reached = seq.config.eos_token_id == Some(verif_result.emitted_target_token);
306            let max_reached = seq.total_generated >= seq.config.max_new_tokens;
307
308            if eos_reached || max_reached {
309                let reason = if eos_reached { "EOS" } else { "MaxTokens" };
310                let _ = seq.sender.try_send(GenerationEvent::Finished {
311                    total_tokens: seq.total_generated,
312                    reason: reason.into(),
313                });
314                finished_indices.push(p.seq_idx);
315            }
316        }
317
318        self.tokens_emitted_counter
319            .fetch_add(total_tokens_this_step, Ordering::Relaxed);
320
321        // 5. Retire finished sequences and cleanup their cache
322        if !finished_indices.is_empty() {
323            finished_indices.sort_unstable_by(|a, b| b.cmp(a)); // remove in reverse order
324            let mut active = self.active.lock().unwrap();
325            for idx in finished_indices {
326                let finished_seq = active.swap_remove(idx);
327                let _ = self.cache_manager.remove_sequence(finished_seq.sequence_id);
328                self.completed_counter.fetch_add(1, Ordering::Relaxed);
329            }
330        }
331
332        Ok(total_tokens_this_step)
333    }
334}
335
336#[cfg(test)]
337mod tests {
338    use super::*;
339    use crate::model::SyntheticModel;
340
341    #[tokio::test]
342    async fn test_continuous_batch_scheduler() {
343        let vocab_size = 50;
344        let draft = SyntheticModel::new("draft", vocab_size, 0.8, 42);
345        let target = SyntheticModel::new("target", vocab_size, 0.95, 1337);
346        let cache = Arc::new(PagedKvCacheManager::with_defaults(64));
347
348        let scheduler = ContinuousBatchScheduler::new(draft, target, cache, 4);
349
350        let (tx1, mut rx1) = mpsc::channel(32);
351        let (tx2, mut rx2) = mpsc::channel(32);
352
353        let config1 = SpeculativeConfig {
354            max_new_tokens: 6,
355            ..Default::default()
356        };
357        let config2 = SpeculativeConfig {
358            max_new_tokens: 8,
359            ..Default::default()
360        };
361
362        scheduler
363            .submit(QueuedRequest::new(101, vec![1, 2], config1, tx1))
364            .unwrap();
365        scheduler
366            .submit(QueuedRequest::new(102, vec![3, 4], config2, tx2))
367            .unwrap();
368
369        assert_eq!(scheduler.queue_len(), 2);
370        assert_eq!(scheduler.active_len(), 0);
371
372        // Run iterations until both complete
373        let mut iterations = 0;
374        while scheduler.active_len() > 0 || scheduler.queue_len() > 0 {
375            let tokens = scheduler.step_iteration().await.unwrap();
376            iterations += 1;
377            if iterations > 20 {
378                break;
379            }
380            if tokens == 0 && scheduler.active_len() == 0 {
381                break;
382            }
383        }
384
385        let stats = scheduler.stats();
386        assert_eq!(stats.completed_sequences, 2);
387        assert!(stats.total_tokens_emitted >= 14);
388
389        // Drain channels
390        let mut tokens_req1 = 0;
391        while let Ok(event) = rx1.try_recv() {
392            if let GenerationEvent::Token { .. } = event {
393                tokens_req1 += 1;
394            }
395        }
396        assert!(tokens_req1 >= 6);
397
398        let mut tokens_req2 = 0;
399        while let Ok(event) = rx2.try_recv() {
400            if let GenerationEvent::Token { .. } = event {
401                tokens_req2 += 1;
402            }
403        }
404        assert!(tokens_req2 >= 8);
405    }
406}