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