1use {
20 super::Log,
21 crate::{error::LogError, name, retention, segment::Segment},
22 krabka_ids::Offset,
23 krabka_units::prelude::{ByteSize, ByteSizeExt as _},
24 krabka_verified::timestamp::first_timestamp_index,
25 std::{fs, sync::PoisonError, time::SystemTime},
26};
27
28#[derive(Clone, Copy)]
30enum Seek {
31 FirstCandidate,
34 FirstRetained,
37}
38
39fn largest_timestamp(segment: &Segment) -> i64 {
45 let max = segment.max_timestamp();
46 if max >= 0 {
47 return max;
48 }
49 segment.last_modified().map_or(0, retention::now_ms)
50}
51
52struct TimestampScanSettings {
54 scan_window: ByteSize,
55 limit: Option<ByteSize>,
56}
57
58#[derive(Clone, Copy)]
61struct BestSegment<'a> {
62 timestamp: i64,
63 offset: Offset,
64 segment: &'a Segment,
65}
66
67impl Log {
68 pub fn legacy_offsets_before(
80 &self,
81 timestamp: i64,
82 max_num_offsets: usize,
83 ) -> Result<Vec<Offset>, LogError> {
84 let segments: Vec<&Segment> = self.segments.iter().chain(self.active.as_ref()).collect();
85 let log_start = self.log_start_offset();
86 let mut offset_times = Vec::with_capacity(segments.len() + 1);
87 for segment in &segments {
88 let modified =
89 fs::metadata(name::log_path(&self.dir, segment.base_offset().0))?.modified()?;
90 offset_times.push((
91 segment.base_offset().max(log_start),
92 retention::now_ms(modified),
93 ));
94 }
95 if segments
96 .last()
97 .is_some_and(|segment| segment.size() > krabka_units::ByteSize::ZERO)
98 {
99 offset_times.push((self.log_end_offset(), retention::now_ms(SystemTime::now())));
100 }
101
102 let start = match timestamp {
103 -1 => offset_times.len().checked_sub(1),
104 -2 => (!offset_times.is_empty()).then_some(0),
105 _ => offset_times
106 .iter()
107 .rposition(|(_, modified)| *modified <= timestamp),
108 };
109 let Some(start) = start else {
110 return Ok(Vec::new());
111 };
112 Ok(offset_times
113 .iter()
114 .take(start + 1)
115 .rev()
116 .take(max_num_offsets)
117 .map(|(offset, _)| *offset)
118 .collect())
119 }
120
121 #[must_use]
135 pub fn offset_for_timestamp(&self, target_ts: i64) -> Option<(Offset, i64)> {
136 let scan_window = self
137 .config
138 .read()
139 .unwrap_or_else(PoisonError::into_inner)
140 .timestamp_scan_window;
141 self.scan_offset_for_timestamp(
143 target_ts,
144 scan_window,
145 None,
146 self.log_start_offset(),
147 Seek::FirstRetained,
148 )
149 .ok()
150 .flatten()
151 }
152
153 pub fn offset_for_timestamp_checked(
174 &self,
175 target_ts: i64,
176 ) -> Result<Option<(Offset, i64)>, LogError> {
177 self.offset_for_timestamp_checked_from(target_ts, self.log_start_offset())
178 }
179
180 pub fn offset_for_timestamp_checked_from(
192 &self,
193 target_ts: i64,
194 minimum: Offset,
195 ) -> Result<Option<(Offset, i64)>, LogError> {
196 let TimestampScanSettings { scan_window, limit } = self.timestamp_scan_settings();
197 self.scan_offset_for_timestamp(target_ts, scan_window, limit, minimum, Seek::FirstCandidate)
198 }
199
200 fn timestamp_scan_settings(&self) -> TimestampScanSettings {
202 let config = self.config.read().unwrap_or_else(PoisonError::into_inner);
203 TimestampScanSettings {
204 scan_window: config.timestamp_scan_window,
205 limit: config.max_decompressed_record,
206 }
207 }
208
209 fn scan_offset_for_timestamp(
213 &self,
214 target_ts: i64,
215 scan_window: ByteSize,
216 limit: Option<ByteSize>,
217 minimum: Offset,
218 seek: Seek,
219 ) -> Result<Option<(Offset, i64)>, LogError> {
220 let minimum = self.log_start_offset().max(minimum);
221 match seek {
222 Seek::FirstCandidate => {
223 let segments: Vec<&Segment> =
224 self.segments.iter().chain(self.active.as_ref()).collect();
225 let largest: Vec<i64> = segments.iter().map(|seg| largest_timestamp(seg)).collect();
226 let Some(candidate) = first_timestamp_index(&largest, target_ts) else {
227 return Ok(None);
228 };
229 let Some(segment) = segments.get(candidate) else {
230 return Ok(None);
231 };
232 segment.offset_for_timestamp_with_window_from(
233 target_ts,
234 scan_window,
235 limit,
236 minimum,
237 )
238 }
239 Seek::FirstRetained => {
240 for seg in &self.segments {
241 if seg.last_offset() >= minimum
246 && seg.max_timestamp() >= target_ts
247 && let Some(hit) = seg.offset_for_timestamp_with_window_from(
248 target_ts,
249 scan_window,
250 limit,
251 minimum,
252 )?
253 {
254 return Ok(Some(hit));
255 }
256 }
257 if let Some(active) = &self.active
258 && active.max_timestamp() >= target_ts
259 {
260 return active.offset_for_timestamp_with_window_from(
261 target_ts,
262 scan_window,
263 limit,
264 minimum,
265 );
266 }
267 Ok(None)
268 }
269 }
270 }
271
272 pub fn max_timestamp_offset_and_ts(&self) -> Result<Option<(Offset, i64)>, LogError> {
289 let TimestampScanSettings { scan_window, limit } = self.timestamp_scan_settings();
290 self.scan_max_timestamp(scan_window, limit)
291 }
292
293 fn scan_max_timestamp(
294 &self,
295 scan_window: ByteSize,
296 limit: Option<ByteSize>,
297 ) -> Result<Option<(Offset, i64)>, LogError> {
298 let mut best: Option<BestSegment<'_>> = None;
299 let candidates = self.segments.iter().chain(self.active.as_ref());
300 for seg in candidates {
301 if let Some((offset, ts)) =
305 seg.offset_of_max_timestamp_with_window(scan_window, None)?
306 && best.is_none_or(|best| ts > best.timestamp)
307 {
308 best = Some(BestSegment {
309 timestamp: ts,
310 offset,
311 segment: seg,
312 });
313 }
314 }
315 if let Some(BestSegment {
316 segment: winner, ..
317 }) = best
318 && limit.is_some()
319 {
320 winner.offset_of_max_timestamp_with_window(scan_window, limit)?;
321 }
322 Ok(best.map(|best| (best.offset, best.timestamp)))
323 }
324}
325
326#[cfg(test)]
327mod tests {
328 use {
329 super::*,
330 crate::{
331 config::LogConfig,
332 log::test_support::{
333 TempLog, configured_test_log, gzip_value, rolled_sample_log, test_log,
334 tiny_segments, ts_batch,
335 },
336 segment::Segment,
337 },
338 assert2::check,
339 krabka_protocol::records::RecordBatch,
340 krabka_units::prelude::{bytes, kibibytes},
341 tempfile::tempdir,
342 };
343
344 #[test]
351 fn the_max_timestamp_offset_comes_from_the_first_segment_holding_it() {
352 let dir = tempdir().unwrap();
353 let log = rolled_sample_log(dir.path());
354
355 let (offset, ts) = log
356 .max_timestamp_offset_and_ts()
357 .expect("no limit is set")
358 .expect("a log with records has a maximum");
359 let earliest = log
362 .segments
363 .iter()
364 .chain(log.active.as_ref())
365 .filter_map(Segment::offset_of_max_timestamp)
366 .filter(|(_, seg_ts)| *seg_ts == ts)
367 .map(|(seg_offset, _)| seg_offset)
368 .min()
369 .expect("some segment holds the maximum");
370 check!(
371 offset == earliest,
372 "got {offset:?}, earliest is {earliest:?}"
373 );
374 }
375
376 #[yare::parameterized(
377 before_first = { "before first", 50, Some((Offset(0), 100)) },
378 exact_sealed = { "exact sealed", 300, Some((Offset(2), 300)) },
379 between_records = { "between records", 350, Some((Offset(3), 400)) },
380 active_record = { "active record", 500, Some((Offset(4), 500)) },
381 after_last = { "after last", 600, None },
382 )]
383 fn log_offset_for_timestamp_across_segments(
384 name: &str,
385 target: i64,
386 want: Option<(Offset, i64)>,
387 ) {
388 let dir = tempdir().unwrap();
389 let config = tiny_segments();
390 let mut log = Log::open(dir.path(), config).unwrap();
391 for (_name, i, ts) in [
393 ("first", 0, 100),
394 ("second", 1, 200),
395 ("third", 2, 300),
396 ("fourth", 3, 400),
397 ("fifth", 4, 500),
398 ] {
399 let mut b = ts_batch(ts);
400 assert2::assert!(log.append(&mut b).unwrap().0 == Offset(i));
401 }
402 check!(
403 log.offset_for_timestamp(target) == want,
404 "case {name}: ts={target}"
405 );
406 log.close();
407 drop(dir);
408 }
409
410 #[derive(Debug, PartialEq, Eq)]
413 struct Answers {
414 list_offsets: Option<(Offset, i64)>,
415 bookkeeping: Option<(Offset, i64)>,
416 }
417
418 #[test]
429 fn a_list_offsets_seek_answers_from_the_first_candidate_segment_only() {
430 struct Case {
431 name: &'static str,
432 segments: &'static [&'static [i64]],
434 log_start: i64,
435 target: i64,
436 want: Answers,
437 }
438 let cases = [
439 Case {
440 name: "the first candidate holds the match",
441 segments: &[&[100, 500, 150, 160, 170], &[600]],
442 log_start: 0,
443 target: 400,
444 want: Answers {
445 list_offsets: Some((Offset(1), 500)),
446 bookkeeping: Some((Offset(1), 500)),
447 },
448 },
449 Case {
450 name: "a segment below the target is no candidate",
451 segments: &[&[100, 200], &[300, 600], &[700]],
452 log_start: 0,
453 target: 400,
454 want: Answers {
455 list_offsets: Some((Offset(3), 600)),
456 bookkeeping: Some((Offset(3), 600)),
457 },
458 },
459 Case {
460 name: "the first candidate's only match is below the log start",
461 segments: &[&[100, 500, 150, 160, 170], &[600]],
462 log_start: 2,
463 target: 400,
464 want: Answers {
465 list_offsets: None,
466 bookkeeping: Some((Offset(5), 600)),
467 },
468 },
469 Case {
470 name: "the first candidate is wholly below the log start",
471 segments: &[&[100, 500], &[150, 160], &[600]],
472 log_start: 2,
473 target: 400,
474 want: Answers {
475 list_offsets: None,
476 bookkeeping: Some((Offset(4), 600)),
477 },
478 },
479 Case {
480 name: "a segment with no record timestamp is a candidate by its file time",
481 segments: &[&[-1], &[600]],
482 log_start: 0,
483 target: 400,
484 want: Answers {
485 list_offsets: None,
486 bookkeeping: Some((Offset(1), 600)),
487 },
488 },
489 Case {
490 name: "the active segment is the first candidate",
491 segments: &[&[100, 200], &[150, 600]],
492 log_start: 0,
493 target: 400,
494 want: Answers {
495 list_offsets: Some((Offset(3), 600)),
496 bookkeeping: Some((Offset(3), 600)),
497 },
498 },
499 ];
500 let mut actual = Vec::new();
501 let mut expected = Vec::new();
502 for Case {
503 name,
504 segments,
505 log_start,
506 target,
507 want,
508 } in cases
509 {
510 let dir = tempdir().unwrap();
511 let mut log = Log::open(dir.path(), LogConfig::default()).unwrap();
512 for (index, timestamps) in segments.iter().enumerate() {
513 if index > 0 {
514 assert2::assert!(log.roll().unwrap());
515 }
516 for &ts in *timestamps {
517 log.append(&mut ts_batch(ts)).unwrap();
518 }
519 }
520 log.set_log_start_offset(Offset(log_start)).unwrap();
521 actual.push((name, Answers {
522 list_offsets: log.offset_for_timestamp_checked(target).unwrap(),
523 bookkeeping: log.offset_for_timestamp(target),
524 }));
525 expected.push((name, want));
526 log.close();
527 }
528 check!(actual == expected);
529 }
530
531 #[test]
532 fn reopened_log_scans_sealed_segments_with_unknown_max_timestamp() {
533 let dir = tempdir().unwrap();
534 let config = tiny_segments();
535 {
536 let mut log = Log::open(dir.path(), config.clone()).unwrap();
537 for timestamp in [100, 200, 300] {
538 log.append(&mut ts_batch(timestamp)).unwrap();
539 }
540 log.close();
541 }
542
543 let log = Log::open(dir.path(), config).unwrap();
544 assert2::assert!(log.offset_for_timestamp(150) == Some((Offset(1), 200)));
545 assert2::assert!(log.max_timestamp_offset_and_ts().unwrap() == Some((Offset(2), 300)));
546 log.close();
547 }
548
549 #[test]
550 fn configured_io_policy_reaches_reads_and_timestamp_scans() {
551 let TempLog { dir: _dir, mut log } = configured_test_log(LogConfig {
552 read_buffer_cap: bytes(1),
553 timestamp_scan_window: bytes(1),
554 ..LogConfig::default()
555 });
556 let mut batch = ts_batch(100);
557 log.append(&mut batch).unwrap();
558
559 assert2::assert!(
560 !log.read_raw(Offset(0), Offset(1), kibibytes(1))
561 .unwrap()
562 .bytes
563 .is_empty()
564 );
565 assert2::assert!(log.offset_for_timestamp(100) == Some((Offset(0), 100)));
566 }
567
568 #[test]
569 fn log_offset_for_timestamp_empty_log_is_none() {
570 let TempLog { dir, log } = test_log();
571 assert2::assert!(log.offset_for_timestamp(0) == None);
572 log.close();
573 drop(dir);
574 }
575
576 #[test]
579 fn log_max_timestamp_of_an_empty_log_is_none() {
580 let TempLog { dir, log } = test_log();
581 assert2::assert!(log.max_timestamp_offset_and_ts().unwrap() == None);
582 log.close();
583 drop(dir);
584 }
585
586 #[test]
587 fn log_max_timestamp_offset_and_ts_returns_pair() {
588 let dir = tempdir().unwrap();
589 let config = tiny_segments();
590 let mut log = Log::open(dir.path(), config).unwrap();
591 for ts in [100, 300, 200] {
592 let mut b = ts_batch(ts);
593 log.append(&mut b).unwrap();
594 }
595 assert2::assert!(log.max_timestamp_offset_and_ts().unwrap() == Some((Offset(1), 300)));
597 log.close();
598 drop(dir);
599 }
600
601 #[test]
602 fn legacy_offsets_before_semantics() {
603 let TempLog { dir: _dir, mut log } = test_log();
604 assert2::assert!(log.legacy_offsets_before(-1, 10).unwrap() == vec![Offset(0)]);
605 assert2::assert!(log.legacy_offsets_before(-2, 10).unwrap() == vec![Offset(0)]);
606 assert2::assert!(log.legacy_offsets_before(0, 10).unwrap().is_empty());
607
608 let mut b = ts_batch(100);
609 log.append(&mut b).unwrap();
610
611 let latest = log.legacy_offsets_before(-1, 10).unwrap();
613 assert2::assert!(latest == vec![Offset(1), Offset(0)]);
614
615 let earliest = log.legacy_offsets_before(-2, 10).unwrap();
617 assert2::assert!(earliest == vec![Offset(0)]);
618
619 assert2::assert!(log.legacy_offsets_before(0, 10).unwrap().is_empty());
621
622 let all = log.legacy_offsets_before(i64::MAX, 10).unwrap();
624 assert2::assert!(all == vec![Offset(1), Offset(0)]);
625 let capped = log.legacy_offsets_before(i64::MAX, 1).unwrap();
626 assert2::assert!(capped == vec![Offset(1)]);
627 }
628
629 fn gzip_batch(ts: i64, value_len: usize) -> RecordBatch {
631 let mut batch = ts_batch(ts);
632 gzip_value(&mut batch, value_len);
633 batch
634 }
635
636 fn answer(
639 result: Result<Option<(Offset, i64)>, LogError>,
640 ) -> Result<Option<(Offset, i64)>, ()> {
641 match result {
642 Ok(found) => Ok(found),
643 Err(LogError::RecordTooLarge { limit: 100, .. }) => Err(()),
644 Err(other) => panic!("unexpected error: {other}"),
645 }
646 }
647
648 #[test]
653 fn the_checked_lookups_hold_a_decompressed_batch_to_the_record_limit() {
654 let TempLog { dir: _dir, mut log } = configured_test_log(LogConfig {
655 max_decompressed_record: Some(bytes(100)),
656 ..tiny_segments()
657 });
658 for (ts, value_len) in [(100, 1_000), (300, 10), (200, 1_000)] {
659 log.append(&mut gzip_batch(ts, value_len)).unwrap();
660 }
661 check!(log.segments.len() == 2, "the third batch is the active one");
662
663 for (name, target, expected) in [
664 ("the match is oversized", 50, Err(())),
667 (
669 "an older oversized segment is skipped",
670 150,
671 Ok(Some((Offset(1), 300))),
672 ),
673 (
674 "a match in the small batch",
675 300,
676 Ok(Some((Offset(1), 300))),
677 ),
678 ("nothing that late", 301, Ok(None)),
679 ] {
680 check!(
681 answer(log.offset_for_timestamp_checked(target)) == expected,
682 "{name}: {target}"
683 );
684 }
685 check!(answer(log.max_timestamp_offset_and_ts()) == Ok(Some((Offset(1), 300))));
688
689 check!(log.offset_for_timestamp(50) == Some((Offset(0), 100)));
691
692 log.append(&mut gzip_batch(400, 1_000)).unwrap();
694 check!(answer(log.max_timestamp_offset_and_ts()) == Err(()));
695
696 for limit in [Some(bytes(1_008)), None] {
699 let mut config = log.config_snapshot();
700 config.max_decompressed_record = limit;
701 log.set_config(config);
702 check!(
703 answer(log.offset_for_timestamp_checked(50)) == Ok(Some((Offset(0), 100))),
704 "{limit:?}"
705 );
706 check!(
707 answer(log.max_timestamp_offset_and_ts()) == Ok(Some((Offset(3), 400))),
708 "{limit:?}"
709 );
710 }
711 log.close();
712 }
713
714 #[test]
717 fn the_checked_lookups_never_hold_an_uncompressed_batch_to_the_limit() {
718 let TempLog { dir: _dir, mut log } = configured_test_log(LogConfig {
719 max_decompressed_record: Some(bytes(100)),
720 ..LogConfig::default()
721 });
722 let mut batch = gzip_batch(100, 1_000);
723 batch.attributes = batch
724 .attributes
725 .with_compression(krabka_compression::CompressionType::None);
726 log.append(&mut batch).unwrap();
727
728 check!(answer(log.offset_for_timestamp_checked(100)) == Ok(Some((Offset(0), 100))));
729 check!(answer(log.max_timestamp_offset_and_ts()) == Ok(Some((Offset(0), 100))));
730 log.close();
731 }
732}