Skip to main content

buoyant_kernel/crc/
file_size_histogram.rs

1//! [`FileSizeHistogram`] tracks the distribution of file sizes across predefined bins.
2//!
3//! Used in CRC (version checksum) files to record the size distribution of active files in a
4//! table version. Supports incremental updates via [`insert`](FileSizeHistogram::insert) and
5//! [`remove`](FileSizeHistogram::remove), and delta merging via
6//! [`try_apply_delta`](FileSizeHistogram::try_apply_delta).
7//!
8//! [FileSizeHistogram]: https://github.com/delta-io/delta/blob/master/PROTOCOL.md#file-size-histogram-schema
9
10use serde::{Deserialize, Serialize};
11
12use crate::utils::require;
13use crate::{DeltaResult, Error};
14
15const KB: i64 = 1024;
16const MB: i64 = KB * 1024;
17const GB: i64 = MB * 1024;
18
19/// Default bin boundaries for file size categorization, matching Delta Kernel Java.
20///
21/// 95 boundaries covering:
22/// - 0 and powers of 2 from 8KB to 4MB
23/// - 4MB steps from 8MB to 40MB
24/// - 8MB steps from 48MB to 120MB
25/// - 4MB steps from 124MB to 144MB (fine granularity around 128MB target file size)
26/// - 16MB steps from 160MB to 576MB
27/// - 64MB steps from 640MB to 1408MB
28/// - 128MB steps from 1536MB to 2GB
29/// - 256MB steps from 2304MB to 4GB
30/// - Powers of 2 from 8GB to 256GB
31#[rustfmt::skip]
32const DEFAULT_BIN_BOUNDARIES: [i64; 95] = [
33    0,
34    // Powers of 2 from 8KB to 4MB
35    8 * KB, 16 * KB, 32 * KB, 64 * KB, 128 * KB, 256 * KB, 512 * KB,
36    MB, 2 * MB, 4 * MB,
37    // 4MB steps from 8MB to 40MB
38    8 * MB, 12 * MB, 16 * MB, 20 * MB, 24 * MB, 28 * MB, 32 * MB, 36 * MB, 40 * MB,
39    // 8MB steps from 48MB to 120MB
40    48 * MB, 56 * MB, 64 * MB, 72 * MB, 80 * MB, 88 * MB, 96 * MB, 104 * MB, 112 * MB, 120 * MB,
41    // 4MB steps from 124MB to 144MB
42    124 * MB, 128 * MB, 132 * MB, 136 * MB, 140 * MB, 144 * MB,
43    // 16MB steps from 160MB to 576MB
44    160 * MB, 176 * MB, 192 * MB, 208 * MB, 224 * MB, 240 * MB, 256 * MB, 272 * MB,
45    288 * MB, 304 * MB, 320 * MB, 336 * MB, 352 * MB, 368 * MB, 384 * MB, 400 * MB,
46    416 * MB, 432 * MB, 448 * MB, 464 * MB, 480 * MB, 496 * MB, 512 * MB, 528 * MB,
47    544 * MB, 560 * MB, 576 * MB,
48    // 64MB steps from 640MB to 1408MB
49    640 * MB, 704 * MB, 768 * MB, 832 * MB, 896 * MB, 960 * MB, 1024 * MB, 1088 * MB,
50    1152 * MB, 1216 * MB, 1280 * MB, 1344 * MB, 1408 * MB,
51    // 128MB steps from 1536MB to 2GB
52    1536 * MB, 1664 * MB, 1792 * MB, 1920 * MB, 2048 * MB,
53    // 256MB steps from 2304MB to 4GB
54    2304 * MB, 2560 * MB, 2816 * MB, 3072 * MB, 3328 * MB, 3584 * MB, 3840 * MB, 4096 * MB,
55    // Powers of 2 from 8GB to 256GB
56    8 * GB, 16 * GB, 32 * GB, 64 * GB, 128 * GB, 256 * GB,
57];
58
59/// Tracks the distribution of file sizes across predefined bins.
60///
61/// Each bin `i` covers the range `[sorted_bin_boundaries[i], sorted_bin_boundaries[i+1])`,
62/// with the last bin extending to infinity. The histogram records both the count of files
63/// and the total bytes in each bin.
64///
65/// See the [Delta protocol spec] for the full schema definition.
66///
67/// [Delta protocol spec]: https://github.com/delta-io/delta/blob/master/PROTOCOL.md#file-size-histogram-schema
68#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
69#[serde(rename_all = "camelCase")]
70pub struct FileSizeHistogram {
71    /// A sorted array of bin boundaries where each element represents the start of a bin
72    /// (inclusive) and the next element represents the end of the bin (exclusive). The first
73    /// element must be 0.
74    pub(crate) sorted_bin_boundaries: Vec<i64>,
75    /// Count of files in each bin. Length must match `sorted_bin_boundaries`.
76    pub(crate) file_counts: Vec<i64>,
77    /// Total bytes of files in each bin. Length must match `sorted_bin_boundaries`.
78    pub(crate) total_bytes: Vec<i64>,
79}
80
81impl FileSizeHistogram {
82    /// Returns the sorted bin boundaries defining the histogram ranges.
83    ///
84    /// Each element represents the inclusive lower bound of a bin. The bin covers
85    /// `[sorted_bin_boundaries[i], sorted_bin_boundaries[i+1])`, with the last bin
86    /// extending to infinity. The first element is always 0.
87    pub fn sorted_bin_boundaries(&self) -> &[i64] {
88        &self.sorted_bin_boundaries
89    }
90
91    /// Returns the file count for each bin.
92    ///
93    /// Each element is the number of files whose size falls within the corresponding
94    /// bin's range. Length matches [`sorted_bin_boundaries()`](Self::sorted_bin_boundaries).
95    pub fn file_counts(&self) -> &[i64] {
96        &self.file_counts
97    }
98
99    /// Returns the total bytes for each bin.
100    ///
101    /// Each element is the sum of file sizes within the corresponding bin's range.
102    /// Length matches [`sorted_bin_boundaries()`](Self::sorted_bin_boundaries).
103    pub fn total_bytes(&self) -> &[i64] {
104        &self.total_bytes
105    }
106
107    /// Creates a new histogram with the given arrays, after validation.
108    ///
109    /// Validates that:
110    /// - All arrays have the same length (>= 2)
111    /// - The first boundary is 0
112    /// - Boundaries are sorted in ascending order
113    pub(crate) fn try_new(
114        sorted_bin_boundaries: Vec<i64>,
115        file_counts: Vec<i64>,
116        total_bytes: Vec<i64>,
117    ) -> DeltaResult<Self> {
118        require!(
119            sorted_bin_boundaries.len() >= 2,
120            Error::internal_error(format!(
121                "sorted_bin_boundaries must have at least 2 elements, got {}",
122                sorted_bin_boundaries.len()
123            ))
124        );
125        require!(
126            sorted_bin_boundaries[0] == 0,
127            Error::internal_error(format!(
128                "First boundary must be 0, got {}",
129                sorted_bin_boundaries[0]
130            ))
131        );
132        require!(
133            sorted_bin_boundaries.len() == file_counts.len()
134                && sorted_bin_boundaries.len() == total_bytes.len(),
135            Error::internal_error(format!(
136                "All arrays must have the same length: boundaries={}, file_counts={}, total_bytes={}",
137                sorted_bin_boundaries.len(),
138                file_counts.len(),
139                total_bytes.len()
140            ))
141        );
142        require!(
143            sorted_bin_boundaries.windows(2).all(|w| w[0] < w[1]),
144            Error::internal_error(
145                "sorted_bin_boundaries must be sorted in strictly ascending order"
146            )
147        );
148        Ok(Self {
149            sorted_bin_boundaries,
150            file_counts,
151            total_bytes,
152        })
153    }
154
155    /// Creates an empty histogram with the given bin boundaries and zero counts/bytes.
156    ///
157    /// Used when a previous CRC has non-default boundaries and we need to build delta
158    /// histograms that match, so that `try_apply_delta` succeeds during merge.
159    pub(crate) fn create_empty_with_boundaries(
160        sorted_bin_boundaries: Vec<i64>,
161    ) -> DeltaResult<Self> {
162        let len = sorted_bin_boundaries.len();
163        Self::try_new(sorted_bin_boundaries, vec![0; len], vec![0; len])
164    }
165
166    /// Creates a default histogram with the standard 95 bin boundaries and zero counts.
167    ///
168    /// Uses the same bin boundaries as Delta Kernel Java for cross-implementation compatibility.
169    pub(crate) fn create_default() -> Self {
170        let len = DEFAULT_BIN_BOUNDARIES.len();
171        Self {
172            sorted_bin_boundaries: DEFAULT_BIN_BOUNDARIES.to_vec(),
173            file_counts: vec![0; len],
174            total_bytes: vec![0; len],
175        }
176    }
177
178    /// Returns the bin index for the given file size via binary search.
179    ///
180    /// The bin index is the largest `i` such that `sorted_bin_boundaries[i] <= file_size`.
181    /// Files larger than the maximum boundary are placed in the last bin.
182    fn get_bin_index(&self, file_size: i64) -> usize {
183        debug_assert!(file_size >= 0);
184        match self.sorted_bin_boundaries.binary_search(&file_size) {
185            Ok(idx) => idx,
186            // binary_search returns Err(insertion_point) where insertion_point is where the
187            // value would be inserted. We want the bin before that. Since boundaries[0] = 0
188            // and file_size >= 0, insertion_point >= 1, so subtraction is safe.
189            Err(insertion_point) => insertion_point - 1,
190        }
191    }
192
193    /// Adds a file of the given size to the histogram, incrementing the appropriate bin's
194    /// file count and total bytes.
195    pub(crate) fn insert(&mut self, file_size: i64) -> DeltaResult<()> {
196        require!(
197            file_size >= 0,
198            Error::internal_error(format!("File size must be non-negative, got {}", file_size))
199        );
200        let idx = self.get_bin_index(file_size);
201        self.file_counts[idx] += 1;
202        self.total_bytes[idx] += file_size;
203        Ok(())
204    }
205
206    /// Removes a file of the given size from the histogram, decrementing the appropriate bin's
207    /// file count by 1 and total bytes by `file_size`.
208    ///
209    /// Does not validate that the bin remains non-negative, since this is used to build delta
210    /// histograms where removes may exceed adds in a given bin.
211    pub(crate) fn remove(&mut self, file_size: i64) -> DeltaResult<()> {
212        require!(
213            file_size >= 0,
214            Error::internal_error(format!("File size must be non-negative, got {}", file_size))
215        );
216        let idx = self.get_bin_index(file_size);
217        self.file_counts[idx] -= 1;
218        self.total_bytes[idx] -= file_size;
219        Ok(())
220    }
221
222    /// Applies a delta histogram element-wise to this histogram. Both must have the same bin
223    /// boundaries.
224    ///
225    /// The delta may contain negative values (more files removed than added in a bin).
226    /// Returns a new histogram whose file counts and total bytes are the sum of the two inputs.
227    /// Returns an error if any resulting bin would have negative file counts or total bytes.
228    pub(crate) fn try_apply_delta(
229        &self,
230        delta: &FileSizeHistogram,
231    ) -> DeltaResult<FileSizeHistogram> {
232        require!(
233            self.sorted_bin_boundaries == delta.sorted_bin_boundaries,
234            Error::internal_error("Cannot add histograms with different bin boundaries")
235        );
236        let len = self.sorted_bin_boundaries.len();
237        let mut file_counts = Vec::with_capacity(len);
238        let mut total_bytes = Vec::with_capacity(len);
239        for i in 0..len {
240            let count = self.file_counts[i] + delta.file_counts[i];
241            let bytes = self.total_bytes[i] + delta.total_bytes[i];
242            require!(
243                count >= 0 && bytes >= 0,
244                Error::internal_error(format!(
245                    "Merge would result in negative counts or bytes at bin {}",
246                    i
247                ))
248            );
249            file_counts.push(count);
250            total_bytes.push(bytes);
251        }
252        Ok(FileSizeHistogram {
253            sorted_bin_boundaries: self.sorted_bin_boundaries.clone(),
254            file_counts,
255            total_bytes,
256        })
257    }
258
259    /// Checks that all bins have non-negative file counts and total bytes.
260    ///
261    /// Returns `Ok(self)` if valid, or an error indicating the first bin that is negative.
262    /// Used to validate a delta histogram before using it as an absolute histogram (e.g. for
263    /// version zero where the delta represents the full table state).
264    pub(crate) fn check_non_negative(self) -> DeltaResult<Self> {
265        for i in 0..self.sorted_bin_boundaries.len() {
266            require!(
267                self.file_counts[i] >= 0 && self.total_bytes[i] >= 0,
268                Error::internal_error(format!(
269                    "Histogram has negative counts or bytes at bin {}",
270                    i
271                ))
272            );
273        }
274        Ok(self)
275    }
276}
277
278#[cfg(test)]
279mod tests {
280    use rstest::rstest;
281    use test_utils::assert_result_error_with_message;
282
283    use super::*;
284
285    // ===== Construction =====
286
287    #[test]
288    fn create_default_has_95_bins_starting_at_zero() {
289        let hist = FileSizeHistogram::create_default();
290        assert_eq!(hist.sorted_bin_boundaries.len(), 95);
291        assert_eq!(hist.file_counts.len(), 95);
292        assert_eq!(hist.total_bytes.len(), 95);
293        assert_eq!(hist.sorted_bin_boundaries[0], 0);
294        assert!(hist.file_counts.iter().all(|&c| c == 0));
295        assert!(hist.total_bytes.iter().all(|&b| b == 0));
296    }
297
298    #[test]
299    fn create_empty_with_boundaries_produces_zeroed_histogram() {
300        let hist = FileSizeHistogram::create_empty_with_boundaries(vec![0, 100, 1000]).unwrap();
301        assert_eq!(hist.sorted_bin_boundaries, vec![0, 100, 1000]);
302        assert_eq!(hist.file_counts, vec![0, 0, 0]);
303        assert_eq!(hist.total_bytes, vec![0, 0, 0]);
304    }
305
306    #[test]
307    fn try_new_valid_histogram() {
308        let hist = FileSizeHistogram::try_new(vec![0, 100], vec![5, 3], vec![200, 900]).unwrap();
309        assert_eq!(hist.sorted_bin_boundaries, vec![0, 100]);
310        assert_eq!(hist.file_counts, vec![5, 3]);
311        assert_eq!(hist.total_bytes, vec![200, 900]);
312    }
313
314    #[rstest]
315    #[case::empty_boundaries(vec![], vec![], vec![], "at least 2 elements")]
316    #[case::single_boundary(vec![0], vec![0], vec![0], "at least 2 elements")]
317    #[case::nonzero_first_boundary(vec![1, 100], vec![0, 0], vec![0, 0], "First boundary must be 0")]
318    #[case::mismatched_array_lengths(vec![0, 100], vec![0], vec![0, 0], "same length")]
319    #[case::unsorted_boundaries(vec![0, 200, 100], vec![0, 0, 0], vec![0, 0, 0], "strictly ascending")]
320    #[case::duplicate_boundaries(vec![0, 100, 100], vec![0, 0, 0], vec![0, 0, 0], "strictly ascending")]
321    fn try_new_rejects_invalid_inputs(
322        #[case] boundaries: Vec<i64>,
323        #[case] file_counts: Vec<i64>,
324        #[case] total_bytes: Vec<i64>,
325        #[case] expected_msg: &str,
326    ) {
327        assert_result_error_with_message(
328            FileSizeHistogram::try_new(boundaries, file_counts, total_bytes),
329            expected_msg,
330        );
331    }
332
333    // ===== Binary search =====
334
335    #[test]
336    fn get_bin_index_exact_boundary_match() {
337        let hist = FileSizeHistogram::try_new(vec![0, 100, 200], vec![0; 3], vec![0; 3]).unwrap();
338        assert_eq!(hist.get_bin_index(0), 0);
339        assert_eq!(hist.get_bin_index(100), 1);
340        assert_eq!(hist.get_bin_index(200), 2);
341    }
342
343    #[test]
344    fn get_bin_index_between_boundaries() {
345        let hist = FileSizeHistogram::try_new(vec![0, 100, 200], vec![0; 3], vec![0; 3]).unwrap();
346        assert_eq!(hist.get_bin_index(50), 0);
347        assert_eq!(hist.get_bin_index(99), 0);
348        assert_eq!(hist.get_bin_index(150), 1);
349        assert_eq!(hist.get_bin_index(199), 1);
350    }
351
352    #[test]
353    fn get_bin_index_beyond_max_boundary_returns_last_bin() {
354        let hist = FileSizeHistogram::try_new(vec![0, 100, 200], vec![0; 3], vec![0; 3]).unwrap();
355        assert_eq!(hist.get_bin_index(999), 2);
356        assert_eq!(hist.get_bin_index(i64::MAX), 2);
357    }
358
359    // ===== Insert / Remove =====
360
361    #[test]
362    fn insert_increments_count_and_bytes() {
363        let mut hist =
364            FileSizeHistogram::try_new(vec![0, 100, 200], vec![0; 3], vec![0; 3]).unwrap();
365        hist.insert(50).unwrap();
366        hist.insert(75).unwrap();
367        hist.insert(150).unwrap();
368        assert_eq!(hist.file_counts, vec![2, 1, 0]);
369        assert_eq!(hist.total_bytes, vec![125, 150, 0]);
370    }
371
372    #[test]
373    fn insert_negative_size_returns_error() {
374        let mut hist = FileSizeHistogram::create_default();
375        assert_result_error_with_message(hist.insert(-1), "non-negative");
376    }
377
378    #[test]
379    fn remove_decrements_count_and_bytes() {
380        let mut hist =
381            FileSizeHistogram::try_new(vec![0, 100, 200], vec![2, 1, 0], vec![125, 150, 0])
382                .unwrap();
383        hist.remove(50).unwrap();
384        assert_eq!(hist.file_counts, vec![1, 1, 0]);
385        assert_eq!(hist.total_bytes, vec![75, 150, 0]);
386    }
387
388    #[test]
389    fn remove_allows_negative_bin_values() {
390        let mut hist = FileSizeHistogram::try_new(vec![0, 100], vec![0, 0], vec![0, 0]).unwrap();
391        hist.remove(50).unwrap();
392        assert_eq!(hist.file_counts, vec![-1, 0]);
393        assert_eq!(hist.total_bytes, vec![-50, 0]);
394    }
395
396    #[test]
397    fn remove_negative_size_returns_error() {
398        let mut hist = FileSizeHistogram::create_default();
399        assert_result_error_with_message(hist.remove(-1), "non-negative");
400    }
401
402    // ===== try_apply_delta =====
403
404    #[test]
405    fn try_apply_delta_combines_counts_and_bytes() {
406        let base = FileSizeHistogram::try_new(vec![0, 100], vec![2, 3], vec![50, 400]).unwrap();
407        let delta = FileSizeHistogram::try_new(vec![0, 100], vec![1, 4], vec![30, 600]).unwrap();
408        let result = base.try_apply_delta(&delta).unwrap();
409        assert_eq!(result.file_counts, vec![3, 7]);
410        assert_eq!(result.total_bytes, vec![80, 1000]);
411        assert_eq!(result.sorted_bin_boundaries, vec![0, 100]);
412    }
413
414    #[test]
415    fn try_apply_delta_with_negative_delta_succeeds() {
416        let base = FileSizeHistogram::try_new(vec![0, 100], vec![5, 8], vec![200, 900]).unwrap();
417        let delta =
418            FileSizeHistogram::try_new(vec![0, 100], vec![-2, -3], vec![-50, -400]).unwrap();
419        let result = base.try_apply_delta(&delta).unwrap();
420        assert_eq!(result.file_counts, vec![3, 5]);
421        assert_eq!(result.total_bytes, vec![150, 500]);
422    }
423
424    #[test]
425    fn try_apply_delta_mismatched_boundaries_returns_error() {
426        let a = FileSizeHistogram::try_new(vec![0, 100], vec![0; 2], vec![0; 2]).unwrap();
427        let b = FileSizeHistogram::try_new(vec![0, 200], vec![0; 2], vec![0; 2]).unwrap();
428        assert_result_error_with_message(a.try_apply_delta(&b), "different bin boundaries");
429    }
430
431    #[test]
432    fn try_apply_delta_rejects_negative_result_counts() {
433        let base = FileSizeHistogram::try_new(vec![0, 100], vec![1, 0], vec![50, 0]).unwrap();
434        let delta = FileSizeHistogram::try_new(vec![0, 100], vec![-2, 0], vec![-50, 0]).unwrap();
435        assert_result_error_with_message(base.try_apply_delta(&delta), "negative counts or bytes");
436    }
437
438    #[test]
439    fn try_apply_delta_rejects_negative_result_bytes() {
440        let base = FileSizeHistogram::try_new(vec![0, 100], vec![2, 0], vec![50, 0]).unwrap();
441        let delta = FileSizeHistogram::try_new(vec![0, 100], vec![-1, 0], vec![-100, 0]).unwrap();
442        assert_result_error_with_message(base.try_apply_delta(&delta), "negative counts or bytes");
443    }
444
445    // ===== Serde =====
446
447    #[test]
448    fn serde_round_trip_default_histogram() {
449        let hist = FileSizeHistogram::create_default();
450        let json = serde_json::to_string(&hist).unwrap();
451        let deserialized: FileSizeHistogram = serde_json::from_str(&json).unwrap();
452        assert_eq!(hist, deserialized);
453    }
454
455    #[test]
456    fn serde_round_trip_populated_histogram() {
457        let mut hist = FileSizeHistogram::create_default();
458        hist.insert(500).unwrap();
459        hist.insert(10_000_000).unwrap();
460        let json = serde_json::to_string(&hist).unwrap();
461        let deserialized: FileSizeHistogram = serde_json::from_str(&json).unwrap();
462        assert_eq!(hist, deserialized);
463    }
464
465    #[test]
466    fn serde_uses_camel_case_field_names() {
467        let hist = FileSizeHistogram::try_new(vec![0, 100], vec![1, 2], vec![10, 200]).unwrap();
468        let json_value = serde_json::to_value(&hist).unwrap();
469        assert!(json_value.get("sortedBinBoundaries").is_some());
470        assert!(json_value.get("fileCounts").is_some());
471        assert!(json_value.get("totalBytes").is_some());
472        // Snake case should NOT be present
473        assert!(json_value.get("sorted_bin_boundaries").is_none());
474        assert!(json_value.get("file_counts").is_none());
475        assert!(json_value.get("total_bytes").is_none());
476    }
477
478    #[test]
479    fn serde_deserialize_from_crc_json_format() {
480        let json = r#"{
481            "sortedBinBoundaries": [0, 8192, 16384],
482            "fileCounts": [10, 0, 0],
483            "totalBytes": [5259, 0, 0]
484        }"#;
485        let hist: FileSizeHistogram = serde_json::from_str(json).unwrap();
486        assert_eq!(hist.sorted_bin_boundaries, vec![0, 8192, 16384]);
487        assert_eq!(hist.file_counts, vec![10, 0, 0]);
488        assert_eq!(hist.total_bytes, vec![5259, 0, 0]);
489    }
490}