LCOV - code coverage report
Current view: top level - libs/tenant_size_model/src - calculation.rs (source / functions) Coverage Total Hit
Test: 32f4a56327bc9da697706839ed4836b2a00a408f.info Lines: 98.4 % 122 120
Test Date: 2024-02-07 07:37:29 Functions: 80.0 % 5 4

            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         1814 : #[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           92 :     pub fn calculate(&self) -> SizeResult {
      46           92 :         // Build adjacency list. 'child_list' is indexed by segment id. Each entry
      47           92 :         // contains a list of all child segments of the segment.
      48           92 :         let mut roots: Vec<usize> = Vec::new();
      49           92 :         let mut child_list: Vec<Vec<usize>> = Vec::new();
      50           92 :         child_list.resize(self.segments.len(), Vec::new());
      51              : 
      52          439 :         for (seg_id, seg) in self.segments.iter().enumerate() {
      53          439 :             if let Some(parent_id) = seg.parent {
      54          350 :                 child_list[parent_id].push(seg_id);
      55          350 :             } else {
      56           89 :                 roots.push(seg_id);
      57           89 :             }
      58              :         }
      59              : 
      60           92 :         let mut segment_results = Vec::new();
      61           92 :         segment_results.resize(
      62           92 :             self.segments.len(),
      63           92 :             SegmentSizeResult {
      64           92 :                 method: SegmentMethod::Skipped,
      65           92 :                 accum_size: 0,
      66           92 :             },
      67           92 :         );
      68           92 : 
      69           92 :         let mut total_size = 0;
      70          181 :         for root in roots {
      71           89 :             if let Some(selected) = self.size_here(root, &child_list).non_incremental {
      72           89 :                 StorageModel::fill_selected_sizes(&selected, &mut segment_results);
      73           89 :                 total_size += selected.accum_size;
      74           89 :             } else {
      75            0 :                 // Couldn't find any way to get this root. Error?
      76            0 :             }
      77              :         }
      78              : 
      79           92 :         SizeResult {
      80           92 :             total_size,
      81           92 :             segments: segment_results,
      82           92 :         }
      83           92 :     }
      84              : 
      85          439 :     fn fill_selected_sizes(selected: &SegmentSize, result: &mut Vec<SegmentSizeResult>) {
      86          439 :         result[selected.seg_id] = SegmentSizeResult {
      87          439 :             method: selected.method,
      88          439 :             accum_size: selected.accum_size,
      89          439 :         };
      90              :         // recurse to children
      91          439 :         for child in selected.children.iter() {
      92          350 :             StorageModel::fill_selected_sizes(child, result);
      93          350 :         }
      94          439 :     }
      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          439 :     fn size_here(&self, seg_id: usize, child_list: &Vec<Vec<usize>>) -> SizeAlternatives {
     106          439 :         let seg = &self.segments[seg_id];
     107          439 :         // First figure out the best way to get each child
     108          439 :         let mut children = Vec::new();
     109          439 :         for child_id in &child_list[seg_id] {
     110          350 :             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          439 :         let snapshot_later = if !seg.needed {
     116          168 :             let mut snapshot_later = SegmentSize {
     117          168 :                 seg_id,
     118          168 :                 method: SegmentMethod::Skipped,
     119          168 :                 accum_size: 0,
     120          168 :                 children: Vec::new(),
     121          168 :             };
     122          168 : 
     123          168 :             let mut possible = true;
     124          176 :             for child in children.iter() {
     125          176 :                 if let Some(non_incremental) = &child.non_incremental {
     126          120 :                     snapshot_later.accum_size += non_incremental.accum_size;
     127          120 :                     snapshot_later.children.push(non_incremental.clone())
     128              :                 } else {
     129           56 :                     possible = false;
     130           56 :                     break;
     131              :                 }
     132              :             }
     133          168 :             if possible {
     134          112 :                 Some(snapshot_later)
     135              :             } else {
     136           56 :                 None
     137              :             }
     138              :         } else {
     139          271 :             None
     140              :         };
     141              : 
     142              :         // Method 2. Get a snapshot here. This assumed to be possible, if the 'size' of
     143              :         // this Segment was given.
     144          439 :         let snapshot_here = if !seg.needed || seg.parent.is_none() {
     145          225 :             if let Some(snapshot_size) = seg.size {
     146          189 :                 let mut snapshot_here = SegmentSize {
     147          189 :                     seg_id,
     148          189 :                     method: SegmentMethod::SnapshotHere,
     149          189 :                     accum_size: snapshot_size,
     150          189 :                     children: Vec::new(),
     151          189 :                 };
     152          211 :                 for child in children.iter() {
     153          211 :                     snapshot_here.accum_size += child.incremental.accum_size;
     154          211 :                     snapshot_here.children.push(child.incremental.clone())
     155              :                 }
     156          189 :                 Some(snapshot_here)
     157              :             } else {
     158           36 :                 None
     159              :             }
     160              :         } else {
     161          214 :             None
     162              :         };
     163              : 
     164              :         // Method 3. Use WAL to get here from parent
     165          439 :         let wal_here = {
     166          439 :             let mut wal_here = SegmentSize {
     167          439 :                 seg_id,
     168          439 :                 method: SegmentMethod::Wal,
     169          439 :                 accum_size: if let Some(parent_id) = seg.parent {
     170          350 :                     seg.lsn - self.segments[parent_id].lsn
     171              :                 } else {
     172           89 :                     0
     173              :                 },
     174          439 :                 children: Vec::new(),
     175              :             };
     176          789 :             for child in children {
     177          350 :                 wal_here.accum_size += child.incremental.accum_size;
     178          350 :                 wal_here.children.push(child.incremental)
     179              :             }
     180          439 :             wal_here
     181          439 :         };
     182          439 : 
     183          439 :         // If the parent is not available, what's the cheapest method involving
     184          439 :         // a snapshot here or later?
     185          439 :         let mut cheapest_non_incremental: Option<SegmentSize> = None;
     186          439 :         if let Some(snapshot_here) = snapshot_here {
     187          189 :             cheapest_non_incremental = Some(snapshot_here);
     188          250 :         }
     189          439 :         if let Some(snapshot_later) = snapshot_later {
     190              :             // Use <=, to prefer skipping if the size is equal
     191          112 :             if let Some(parent) = &cheapest_non_incremental {
     192           76 :                 if snapshot_later.accum_size <= parent.accum_size {
     193           68 :                     cheapest_non_incremental = Some(snapshot_later);
     194           68 :                 }
     195           36 :             } else {
     196           36 :                 cheapest_non_incremental = Some(snapshot_later);
     197           36 :             }
     198          327 :         }
     199              : 
     200              :         // And what's the cheapest method, if the parent is available?
     201          439 :         let cheapest_incremental = if let Some(cheapest_non_incremental) = &cheapest_non_incremental
     202              :         {
     203              :             // Is it cheaper to use a snapshot here or later, anyway?
     204              :             // Use <, to prefer Wal over snapshot if the cost is the same
     205          225 :             if wal_here.accum_size < cheapest_non_incremental.accum_size {
     206          183 :                 wal_here
     207              :             } else {
     208           42 :                 cheapest_non_incremental.clone()
     209              :             }
     210              :         } else {
     211          214 :             wal_here
     212              :         };
     213              : 
     214          439 :         SizeAlternatives {
     215          439 :             incremental: cheapest_incremental,
     216          439 :             non_incremental: cheapest_non_incremental,
     217          439 :         }
     218          439 :     }
     219              : }
        

Generated by: LCOV version 2.1-beta