queue.rs 15.8 KB
Newer Older
1
2
3
4
use crate::infer::InferError;
use crate::infer::InferStreamResponse;
use crate::validation::ValidGenerateRequest;
use nohash_hasher::{BuildNoHashHasher, IntMap};
5
use std::collections::VecDeque;
6
use text_generation_client::{Batch, Request};
7
use tokio::sync::oneshot;
8
use tokio::time::Instant;
9
use tracing::{info_span, instrument, Span};
10
11
12
13
14
15
16

/// Queue entry
#[derive(Debug)]
pub(crate) struct Entry {
    /// Request
    pub request: ValidGenerateRequest,
    /// Response sender to communicate between the Infer struct and the batching_task
17
    pub response_tx: flume::Sender<Result<InferStreamResponse, InferError>>,
18
19
20
21
22
23
    /// Span that will live as long as entry
    pub span: Span,
    /// Temporary span used as a guard when logging inference, wait times...
    pub temp_span: Option<Span>,
    /// Instant when this entry was queued
    pub queue_time: Instant,
24
25
26
27
28
29
30
31
    /// Instant when this entry was added to a batch
    pub batch_time: Option<Instant>,
}

/// Request Queue
#[derive(Debug, Clone)]
pub(crate) struct Queue {
    /// Channel to communicate with the background queue task
32
    queue_sender: flume::Sender<QueueCommand>,
33
34
35
}

impl Queue {
36
    pub(crate) fn new(requires_padding: bool) -> Self {
37
        // Create channel
38
        let (queue_sender, queue_receiver) = flume::unbounded();
39
40

        // Launch background queue task
41
        tokio::spawn(queue_task(requires_padding, queue_receiver));
42
43
44
45
46

        Self { queue_sender }
    }

    /// Append an entry to the queue
47
    #[instrument(skip_all)]
48
49
50
    pub(crate) fn append(&self, entry: Entry) {
        // Send append command to the background task managing the state
        // Unwrap is safe here
51
        self.queue_sender
52
            .send(QueueCommand::Append(Box::new(entry), Span::current()))
53
            .unwrap();
54
55
56
    }

    // Get the next batch
57
    #[instrument(skip(self))]
58
59
60
    pub(crate) async fn next_batch(
        &self,
        min_size: Option<usize>,
61
        prefill_token_budget: u32,
62
        token_budget: u32,
63
64
65
66
67
68
69
70
    ) -> Option<NextBatch> {
        // Create response channel
        let (response_sender, response_receiver) = oneshot::channel();
        // Send next batch command to the background task managing the state
        // Unwrap is safe here
        self.queue_sender
            .send(QueueCommand::NextBatch {
                min_size,
71
                prefill_token_budget,
72
                token_budget,
73
                response_sender,
74
                span: Span::current(),
75
76
77
78
79
80
81
82
83
            })
            .unwrap();
        // Await on response channel
        // Unwrap is safe here
        response_receiver.await.unwrap()
    }
}

// Background task responsible of the queue state
84
85
async fn queue_task(requires_padding: bool, receiver: flume::Receiver<QueueCommand>) {
    let mut state = State::new(requires_padding);
86

87
    while let Ok(cmd) = receiver.recv_async().await {
88
        match cmd {
89
            QueueCommand::Append(entry, span) => {
90
                span.in_scope(|| state.append(*entry));
91
92
                metrics::increment_gauge!("tgi_queue_size", 1.0);
            }
93
94
            QueueCommand::NextBatch {
                min_size,
95
                prefill_token_budget,
96
                token_budget,
97
                response_sender,
98
99
                span,
            } => span.in_scope(|| {
100
                let next_batch = state.next_batch(min_size, prefill_token_budget, token_budget);
101
                response_sender.send(next_batch).unwrap();
102
                metrics::gauge!("tgi_queue_size", state.entries.len() as f64);
103
            }),
104
105
106
107
108
109
110
111
        }
    }
}

/// Queue State
#[derive(Debug)]
struct State {
    /// Queue entries organized in a Vec
112
    entries: VecDeque<(u64, Entry)>,
113
114
115
116
117
118

    /// Id of the next entry
    next_id: u64,

    /// Id of the next batch
    next_batch_id: u64,
119
120
121

    /// Whether the model is using padding
    requires_padding: bool,
122
123
124
}

impl State {
125
    fn new(requires_padding: bool) -> Self {
126
        Self {
127
            entries: VecDeque::with_capacity(128),
128
129
            next_id: 0,
            next_batch_id: 0,
130
            requires_padding,
131
132
133
134
        }
    }

    /// Append an entry to the queue
135
136
137
138
139
140
    fn append(&mut self, mut entry: Entry) {
        // Create a span that will live as long as the entry is in the queue waiting to be batched
        let queue_span = info_span!(parent: &entry.span, "queued");
        entry.temp_span = Some(queue_span);

        // Push entry in the queue
141
        self.entries.push_back((self.next_id, entry));
142
143
144
145
        self.next_id += 1;
    }

    // Get the next batch
146
147
148
149
150
151
    fn next_batch(
        &mut self,
        min_size: Option<usize>,
        prefill_token_budget: u32,
        token_budget: u32,
    ) -> Option<NextBatch> {
152
153
154
155
156
157
158
159
160
161
162
        if self.entries.is_empty() {
            return None;
        }

        // Check if we have enough entries
        if let Some(min_size) = min_size {
            if self.entries.len() < min_size {
                return None;
            }
        }

163
        // Create span for this batch to add context to inference calls
164
        let next_batch_span = info_span!(parent: None, "batch", batch_size = tracing::field::Empty);
165
166
        next_batch_span.follows_from(&Span::current());

167
        let mut batch_requests = Vec::with_capacity(self.entries.len());
168
        let mut batch_entries =
169
            IntMap::with_capacity_and_hasher(self.entries.len(), BuildNoHashHasher::default());
170

171
172
173
174
175
        let mut max_input_length = 0;
        let mut prefill_tokens: u32 = 0;
        let mut decode_tokens: u32 = 0;

        // Pop entries starting from the front of the queue
176
177
178
179
180
181
182
183
        while let Some((id, mut entry)) = self.entries.pop_front() {
            // Filter entries where the response receiver was dropped (== entries where the request
            // was dropped by the client)
            if entry.response_tx.is_disconnected() {
                metrics::increment_counter!("tgi_request_failure", "err" => "dropped");
                continue;
            }

184
185
186
187
188
189
190
191
192
193
194
            if self.requires_padding {
                // We pad to max input length in the Python shards
                // We need to take these padding tokens into the equation
                max_input_length = max_input_length.max(entry.request.input_length);
                prefill_tokens = (batch_requests.len() + 1) as u32 * max_input_length
            } else {
                prefill_tokens += entry.request.input_length;
            }

            decode_tokens += entry.request.stopping_parameters.max_new_tokens;

195
196
197
            if prefill_tokens > prefill_token_budget
                || (prefill_tokens + decode_tokens) > token_budget
            {
198
199
200
201
202
203
                // Entry is over budget
                // Add it back to the front
                self.entries.push_front((id, entry));
                break;
            }

204
205
206
207
208
209
210
211
212
213
            // Create a new span to link the batch back to this entry
            let entry_batch_span = info_span!(parent: &entry.span, "infer");
            // Add relationships
            next_batch_span.follows_from(&entry_batch_span);
            entry_batch_span.follows_from(&next_batch_span);
            // Update entry
            entry.temp_span = Some(entry_batch_span);

            batch_requests.push(Request {
                id,
214
                prefill_logprobs: entry.request.decoder_input_details,
215
216
217
218
                inputs: entry.request.inputs.clone(),
                truncate: entry.request.truncate,
                parameters: Some(entry.request.parameters.clone()),
                stopping_parameters: Some(entry.request.stopping_parameters.clone()),
219
            });
220
221
222
223
224
225
            // Set batch_time
            entry.batch_time = Some(Instant::now());
            // Insert in batch_entries IntMap
            batch_entries.insert(id, entry);
        }

226
        // Empty batch
227
228
229
230
        if batch_requests.is_empty() {
            return None;
        }

231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
        // Check if our batch is big enough
        if let Some(min_size) = min_size {
            // Batch is too small
            if batch_requests.len() < min_size {
                // Add back entries to the queue in the correct order
                for r in batch_requests.into_iter().rev() {
                    let id = r.id;
                    let entry = batch_entries.remove(&id).unwrap();
                    self.entries.push_front((id, entry));
                }

                return None;
            }
        }

        // Final batch size
247
248
        let size = batch_requests.len() as u32;
        next_batch_span.record("batch_size", size);
249
250
251
252

        let batch = Batch {
            id: self.next_batch_id,
            requests: batch_requests,
253
            size,
254
            max_tokens: (prefill_tokens + decode_tokens),
255
256
257
258
        };
        // Increment batch id
        self.next_batch_id += 1;

259
        metrics::histogram!("tgi_batch_next_size", batch.size as f64);
260

261
        Some((batch_entries, batch, next_batch_span))
262
263
264
    }
}

265
type NextBatch = (IntMap<u64, Entry>, Batch, Span);
266
267
268

#[derive(Debug)]
enum QueueCommand {
269
    Append(Box<Entry>, Span),
270
271
    NextBatch {
        min_size: Option<usize>,
272
        prefill_token_budget: u32,
273
        token_budget: u32,
274
        response_sender: oneshot::Sender<Option<NextBatch>>,
275
        span: Span,
276
277
278
279
280
281
282
    },
}

#[cfg(test)]
mod tests {
    use super::*;
    use text_generation_client::{NextTokenChooserParameters, StoppingCriteriaParameters};
283
    use tracing::info_span;
284

285
286
287
288
289
    fn default_entry() -> (
        Entry,
        flume::Receiver<Result<InferStreamResponse, InferError>>,
    ) {
        let (response_tx, receiver_tx) = flume::unbounded();
290

291
        let entry = Entry {
292
293
            request: ValidGenerateRequest {
                inputs: "".to_string(),
294
                input_length: 0,
295
                truncate: 0,
296
                decoder_input_details: false,
297
298
299
300
                parameters: NextTokenChooserParameters {
                    temperature: 0.0,
                    top_k: 0,
                    top_p: 0.0,
301
                    typical_p: 0.0,
302
303
304
                    do_sample: false,
                    seed: 0,
                    repetition_penalty: 0.0,
305
                    watermark: false,
306
307
                },
                stopping_parameters: StoppingCriteriaParameters {
308
                    ignore_eos_token: false,
309
                    max_new_tokens: 1,
310
311
312
313
                    stop_sequences: vec![],
                },
            },
            response_tx,
314
315
316
            span: info_span!("entry"),
            temp_span: None,
            queue_time: Instant::now(),
317
            batch_time: None,
318
319
        };
        (entry, receiver_tx)
320
321
322
323
    }

    #[test]
    fn test_append() {
324
        let mut state = State::new(false);
325
        let (entry, _guard) = default_entry();
326
327
328
329
330
331
332
333

        assert_eq!(state.next_id, 0);
        assert_eq!(state.entries.len(), 0);

        state.append(entry);

        assert_eq!(state.next_id, 1);
        assert_eq!(state.entries.len(), 1);
334
        let (id, _) = state.entries.remove(0).unwrap();
335
336
337
338
339
        assert_eq!(id, 0);
    }

    #[test]
    fn test_next_batch_empty() {
340
        let mut state = State::new(false);
341

342
343
        assert!(state.next_batch(None, 1, 1).is_none());
        assert!(state.next_batch(Some(1), 1, 1).is_none());
344
345
346
347
    }

    #[test]
    fn test_next_batch_min_size() {
348
        let mut state = State::new(false);
349
350
351
352
        let (entry1, _guard1) = default_entry();
        let (entry2, _guard2) = default_entry();
        state.append(entry1);
        state.append(entry2);
353

354
        let (entries, batch, _) = state.next_batch(None, 2, 2).unwrap();
355
356
357
358
359
360
361
362
363
364
365
366
        assert_eq!(entries.len(), 2);
        assert!(entries.contains_key(&0));
        assert!(entries.contains_key(&1));
        assert!(entries.get(&0).unwrap().batch_time.is_some());
        assert!(entries.get(&1).unwrap().batch_time.is_some());
        assert_eq!(batch.id, 0);
        assert_eq!(batch.size, 2);

        assert_eq!(state.next_id, 2);
        assert_eq!(state.entries.len(), 0);
        assert_eq!(state.next_batch_id, 1);

367
368
        let (entry3, _guard3) = default_entry();
        state.append(entry3);
369

370
        assert!(state.next_batch(Some(2), 2, 2).is_none());
371
372
373

        assert_eq!(state.next_id, 3);
        assert_eq!(state.entries.len(), 1);
374
        let (id, _) = state.entries.remove(0).unwrap();
375
376
377
378
        assert_eq!(id, 2);
    }

    #[test]
379
380
    fn test_next_batch_token_budget() {
        let mut state = State::new(false);
381
382
383
384
        let (entry1, _guard1) = default_entry();
        let (entry2, _guard2) = default_entry();
        state.append(entry1);
        state.append(entry2);
385

386
        let (entries, batch, _) = state.next_batch(None, 1, 1).unwrap();
387
388
389
390
391
392
393
394
395
        assert_eq!(entries.len(), 1);
        assert!(entries.contains_key(&0));
        assert_eq!(batch.id, 0);
        assert_eq!(batch.size, 1);

        assert_eq!(state.next_id, 2);
        assert_eq!(state.entries.len(), 1);
        assert_eq!(state.next_batch_id, 1);

396
397
        let (entry3, _guard3) = default_entry();
        state.append(entry3);
398

399
        let (entries, batch, _) = state.next_batch(None, 3, 3).unwrap();
400
401
402
403
404
405
406
407
408
409
410
411
412
        assert_eq!(entries.len(), 2);
        assert!(entries.contains_key(&1));
        assert!(entries.contains_key(&2));
        assert_eq!(batch.id, 1);
        assert_eq!(batch.size, 2);

        assert_eq!(state.next_id, 3);
        assert_eq!(state.entries.len(), 0);
        assert_eq!(state.next_batch_id, 2);
    }

    #[tokio::test]
    async fn test_queue_append() {
413
        let queue = Queue::new(false);
414
415
        let (entry, _guard) = default_entry();
        queue.append(entry);
416
417
418
419
    }

    #[tokio::test]
    async fn test_queue_next_batch_empty() {
420
        let queue = Queue::new(false);
421

422
423
        assert!(queue.next_batch(None, 1, 1).await.is_none());
        assert!(queue.next_batch(Some(1), 1, 1).await.is_none());
424
425
426
427
    }

    #[tokio::test]
    async fn test_queue_next_batch_min_size() {
428
        let queue = Queue::new(false);
429
430
431
432
        let (entry1, _guard1) = default_entry();
        let (entry2, _guard2) = default_entry();
        queue.append(entry1);
        queue.append(entry2);
433

434
        let (entries, batch, _) = queue.next_batch(None, 2, 2).await.unwrap();
435
436
437
438
439
440
441
442
        assert_eq!(entries.len(), 2);
        assert!(entries.contains_key(&0));
        assert!(entries.contains_key(&1));
        assert!(entries.get(&0).unwrap().batch_time.is_some());
        assert!(entries.get(&1).unwrap().batch_time.is_some());
        assert_eq!(batch.id, 0);
        assert_eq!(batch.size, 2);

443
444
        let (entry3, _guard3) = default_entry();
        queue.append(entry3);
445

446
        // Not enough requests pending
447
        assert!(queue.next_batch(Some(2), 2, 2).await.is_none());
448
        // Not enough token budget
449
        assert!(queue.next_batch(Some(1), 0, 0).await.is_none());
450
        // Ok
451
        let (entries2, batch2, _) = queue.next_batch(Some(1), 2, 2).await.unwrap();
452
453
454
455
456
        assert_eq!(entries2.len(), 1);
        assert!(entries2.contains_key(&2));
        assert!(entries2.get(&2).unwrap().batch_time.is_some());
        assert_eq!(batch2.id, 1);
        assert_eq!(batch2.size, 1);
457
458
459
    }

    #[tokio::test]
460
461
    async fn test_queue_next_batch_token_budget() {
        let queue = Queue::new(false);
462
463
464
465
        let (entry1, _guard1) = default_entry();
        let (entry2, _guard2) = default_entry();
        queue.append(entry1);
        queue.append(entry2);
466

467
        let (entries, batch, _) = queue.next_batch(None, 1, 1).await.unwrap();
468
469
470
471
472
        assert_eq!(entries.len(), 1);
        assert!(entries.contains_key(&0));
        assert_eq!(batch.id, 0);
        assert_eq!(batch.size, 1);

473
474
        let (entry3, _guard3) = default_entry();
        queue.append(entry3);
475

476
        let (entries, batch, _) = queue.next_batch(None, 3, 3).await.unwrap();
477
478
479
480
481
482
        assert_eq!(entries.len(), 2);
        assert!(entries.contains_key(&1));
        assert!(entries.contains_key(&2));
        assert_eq!(batch.id, 1);
        assert_eq!(batch.size, 2);
    }
483
484
485

    #[tokio::test]
    async fn test_queue_next_batch_dropped_receiver() {
486
        let queue = Queue::new(false);
487
488
489
        let (entry, _) = default_entry();
        queue.append(entry);

490
        assert!(queue.next_batch(None, 1, 1).await.is_none());
491
    }
492
}