LCOV - code coverage report
Current view: top level - libs/tenant_size_model/src - calculation.rs (source / functions) Coverage Total Hit
Test: 5fe7fa8d483b39476409aee736d6d5e32728bfac.info Lines: 98.3 % 119 117
Test Date: 2025-03-12 16:10:49 Functions: 100.0 % 3 3

            Line data    Source code
       1              : use crate::{SegmentMethod, SegmentSizeResult, SizeResult, StorageModel};
       2              : 
       3              : //
       4              : //                 *-g--*---D--->
       5              : //                /
       6              : //               /
       7              : //              /                 *---b----*-B--->
       8              : //             /                 /
       9              : //            /                 /
      10              : //      -----*--e---*-----f----* C
      11              : //           E                  \
      12              : //                               \
      13              : //                                *--a---*---A-->
      14              : //
      15              : // If A and B need to be retained, is it cheaper to store
      16              : // snapshot at C+a+b, or snapshots at A and B ?
      17              : //
      18              : // If D also needs to be retained, which is cheaper:
      19              : //
      20              : // 1. E+g+e+f+a+b
      21              : // 2. D+C+a+b
      22              : // 3. D+A+B
      23              : 
      24              : /// `Segment` which has had its size calculated.
      25              : #[derive(Clone, Debug)]
      26              : struct SegmentSize {
      27              :     method: SegmentMethod,
      28              : 
      29              :     // calculated size of this subtree, using this method
      30              :     accum_size: u64,
      31              : 
      32              :     seg_id: usize,
      33              :     children: Vec<SegmentSize>,
      34              : }
      35              : 
      36              : struct SizeAlternatives {
      37              :     /// cheapest alternative if parent is available.
      38              :     incremental: SegmentSize,
      39              : 
      40              :     /// cheapest alternative if parent node is not available
      41              :     non_incremental: Option<SegmentSize>,
      42              : }
      43              : 
      44              : impl StorageModel {
      45           14 :     pub fn calculate(&self) -> SizeResult {
      46           14 :         // Build adjacency list. 'child_list' is indexed by segment id. Each entry
      47           14 :         // contains a list of all child segments of the segment.
      48           14 :         let mut roots: Vec<usize> = Vec::new();
      49           14 :         let mut child_list: Vec<Vec<usize>> = Vec::new();
      50           14 :         child_list.resize(self.segments.len(), Vec::new());
      51              : 
      52          113 :         for (seg_id, seg) in self.segments.iter().enumerate() {
      53          113 :             if let Some(parent_id) = seg.parent {
      54           99 :                 child_list[parent_id].push(seg_id);
      55           99 :             } else {
      56           14 :                 roots.push(seg_id);
      57           14 :             }
      58              :         }
      59              : 
      60           14 :         let mut segment_results = Vec::new();
      61           14 :         segment_results.resize(
      62           14 :             self.segments.len(),
      63           14 :             SegmentSizeResult {
      64           14 :                 method: SegmentMethod::Skipped,
      65           14 :                 accum_size: 0,
      66           14 :             },
      67           14 :         );
      68           14 : 
      69           14 :         let mut total_size = 0;
      70           28 :         for root in roots {
      71           14 :             if let Some(selected) = self.size_here(root, &child_list).non_incremental {
      72           14 :                 StorageModel::fill_selected_sizes(&selected, &mut segment_results);
      73           14 :                 total_size += selected.accum_size;
      74           14 :             } else {
      75            0 :                 // Couldn't find any way to get this root. Error?
      76            0 :             }
      77              :         }
      78              : 
      79           14 :         SizeResult {
      80           14 :             total_size,
      81           14 :             segments: segment_results,
      82           14 :         }
      83           14 :     }
      84              : 
      85          113 :     fn fill_selected_sizes(selected: &SegmentSize, result: &mut Vec<SegmentSizeResult>) {
      86          113 :         result[selected.seg_id] = SegmentSizeResult {
      87          113 :             method: selected.method,
      88          113 :             accum_size: selected.accum_size,
      89          113 :         };
      90              :         // recurse to children
      91          113 :         for child in selected.children.iter() {
      92           99 :             StorageModel::fill_selected_sizes(child, result);
      93           99 :         }
      94          113 :     }
      95              : 
      96              :     //
      97              :     // This is the core of the sizing calculation.
      98              :     //
      99              :     // This is a recursive function, that for each Segment calculates the best way
     100              :     // to reach all the Segments that are marked as needed in this subtree, under two
     101              :     // different conditions:
     102              :     // a) when the parent of this segment is available (as a snaphot or through WAL), and
     103              :     // b) when the parent of this segment is not available.
     104              :     //
     105          113 :     fn size_here(&self, seg_id: usize, child_list: &Vec<Vec<usize>>) -> SizeAlternatives {
     106          113 :         let seg = &self.segments[seg_id];
     107          113 :         // First figure out the best way to get each child
     108          113 :         let mut children = Vec::new();
     109          113 :         for child_id in &child_list[seg_id] {
     110           99 :             children.push(self.size_here(*child_id, child_list))
     111              :         }
     112              : 
     113              :         // Method 1. If this node is not needed, we can skip it as long as we
     114              :         // take snapshots later in each sub-tree
     115          113 :         let snapshot_later = if !seg.needed {
     116           80 :             let mut snapshot_later = SegmentSize {
     117           80 :                 seg_id,
     118           80 :                 method: SegmentMethod::Skipped,
     119           80 :                 accum_size: 0,
     120           80 :                 children: Vec::new(),
     121           80 :             };
     122           80 : 
     123           80 :             let mut possible = true;
     124           84 :             for child in children.iter() {
     125           84 :                 if let Some(non_incremental) = &child.non_incremental {
     126           58 :                     snapshot_later.accum_size += non_incremental.accum_size;
     127           58 :                     snapshot_later.children.push(non_incremental.clone())
     128              :                 } else {
     129           26 :                     possible = false;
     130           26 :                     break;
     131              :                 }
     132              :             }
     133           80 :             if possible { Some(snapshot_later) } else { None }
     134              :         } else {
     135           33 :             None
     136              :         };
     137              : 
     138              :         // Method 2. Get a snapshot here. This assumed to be possible, if the 'size' of
     139              :         // this Segment was given.
     140          113 :         let snapshot_here = if !seg.needed || seg.parent.is_none() {
     141           80 :             if let Some(snapshot_size) = seg.size {
     142           64 :                 let mut snapshot_here = SegmentSize {
     143           64 :                     seg_id,
     144           64 :                     method: SegmentMethod::SnapshotHere,
     145           64 :                     accum_size: snapshot_size,
     146           64 :                     children: Vec::new(),
     147           64 :                 };
     148           75 :                 for child in children.iter() {
     149           75 :                     snapshot_here.accum_size += child.incremental.accum_size;
     150           75 :                     snapshot_here.children.push(child.incremental.clone())
     151              :                 }
     152           64 :                 Some(snapshot_here)
     153              :             } else {
     154           16 :                 None
     155              :             }
     156              :         } else {
     157           33 :             None
     158              :         };
     159              : 
     160              :         // Method 3. Use WAL to get here from parent
     161          113 :         let wal_here = {
     162          113 :             let mut wal_here = SegmentSize {
     163          113 :                 seg_id,
     164          113 :                 method: SegmentMethod::Wal,
     165          113 :                 accum_size: if let Some(parent_id) = seg.parent {
     166           99 :                     seg.lsn - self.segments[parent_id].lsn
     167              :                 } else {
     168           14 :                     0
     169              :                 },
     170          113 :                 children: Vec::new(),
     171              :             };
     172          212 :             for child in children {
     173           99 :                 wal_here.accum_size += child.incremental.accum_size;
     174           99 :                 wal_here.children.push(child.incremental)
     175              :             }
     176          113 :             wal_here
     177          113 :         };
     178          113 : 
     179          113 :         // If the parent is not available, what's the cheapest method involving
     180          113 :         // a snapshot here or later?
     181          113 :         let mut cheapest_non_incremental: Option<SegmentSize> = None;
     182          113 :         if let Some(snapshot_here) = snapshot_here {
     183           64 :             cheapest_non_incremental = Some(snapshot_here);
     184           64 :         }
     185          113 :         if let Some(snapshot_later) = snapshot_later {
     186              :             // Use <=, to prefer skipping if the size is equal
     187           54 :             if let Some(parent) = &cheapest_non_incremental {
     188           38 :                 if snapshot_later.accum_size <= parent.accum_size {
     189           34 :                     cheapest_non_incremental = Some(snapshot_later);
     190           34 :                 }
     191           16 :             } else {
     192           16 :                 cheapest_non_incremental = Some(snapshot_later);
     193           16 :             }
     194           59 :         }
     195              : 
     196              :         // And what's the cheapest method, if the parent is available?
     197          113 :         let cheapest_incremental = if let Some(cheapest_non_incremental) = &cheapest_non_incremental
     198              :         {
     199              :             // Is it cheaper to use a snapshot here or later, anyway?
     200              :             // Use <, to prefer Wal over snapshot if the cost is the same
     201           80 :             if wal_here.accum_size < cheapest_non_incremental.accum_size {
     202           53 :                 wal_here
     203              :             } else {
     204           27 :                 cheapest_non_incremental.clone()
     205              :             }
     206              :         } else {
     207           33 :             wal_here
     208              :         };
     209              : 
     210          113 :         SizeAlternatives {
     211          113 :             incremental: cheapest_incremental,
     212          113 :             non_incremental: cheapest_non_incremental,
     213          113 :         }
     214          113 :     }
     215              : }
        

Generated by: LCOV version 2.1-beta