storage/ssd_layout/ssd_layout.cc
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #include "storage/ssd_layout/ssd_layout.h" | ||
| 2 | |||
| 3 | #include <algorithm> | ||
| 4 | #include <cmath> | ||
| 5 | #include <cstring> | ||
| 6 | #include <fstream> | ||
| 7 | #include <limits> | ||
| 8 | #include <random> | ||
| 9 | #include <sstream> | ||
| 10 | #include <stdexcept> | ||
| 11 | #include <unordered_map> | ||
| 12 | #include <unordered_set> | ||
| 13 | |||
| 14 | namespace ssd_layout { | ||
| 15 | namespace { | ||
| 16 | |||
| 17 | constexpr char kMagic[8] = {'R', 'S', 'L', 'A', 'Y', '0', '0', '1'}; | ||
| 18 | constexpr uint32_t kVersion = 1; | ||
| 19 | constexpr uint64_t kFnvOffset = 14695981039346656037ULL; | ||
| 20 | constexpr uint64_t kFnvPrime = 1099511628211ULL; | ||
| 21 | constexpr float kBalanceP = 0.5f; | ||
| 22 | constexpr int kMaxRefine = 8; | ||
| 23 | |||
| 24 | 18 | [[noreturn]] void Fail(const std::string& message) { | |
| 25 | 18 | throw std::invalid_argument(message); | |
| 26 | } | ||
| 27 | |||
| 28 | 66 | uint64_t Fnv(const void* data, size_t size, uint64_t hash = kFnvOffset) { | |
| 29 | 66 | const auto* bytes = static_cast<const unsigned char*>(data); | |
| 30 | 18762 | for (size_t i = 0; i < size; ++i) { | |
| 31 | 18696 | hash ^= bytes[i]; | |
| 32 | 18696 | hash *= kFnvPrime; | |
| 33 | } | ||
| 34 | 66 | return hash; | |
| 35 | } | ||
| 36 | |||
| 37 | template <typename T> | ||
| 38 | uint64_t FnvPod(const T& value, uint64_t hash) { | ||
| 39 | return Fnv(&value, sizeof(value), hash); | ||
| 40 | } | ||
| 41 | |||
| 42 | 168 | uint32_t SlotsPerPage(uint32_t page_size, uint32_t row_size) { | |
| 43 | 168 | if (page_size == 0 || row_size == 0 || row_size > page_size) { | |
| 44 | ✗ | Fail("SSD layout row must fit in one page"); | |
| 45 | } | ||
| 46 | 168 | return page_size / row_size; | |
| 47 | } | ||
| 48 | |||
| 49 | 24 | void CheckGraph(const Hypergraph& graph) { | |
| 50 | 24 | if (graph.vertex_count > std::numeric_limits<uint32_t>::max()) { | |
| 51 | ✗ | Fail("SSD layout vertex count exceeds uint32"); | |
| 52 | } | ||
| 53 | 48 | if (graph.xpins.empty() || graph.xpins.front() != 0 || | |
| 54 | 24 | graph.xpins.back() != graph.pins.size()) { | |
| 55 | ✗ | Fail("query log index is invalid"); | |
| 56 | } | ||
| 57 | 16474 | for (size_t i = 1; i < graph.xpins.size(); ++i) { | |
| 58 | 32900 | if (graph.xpins[i] < graph.xpins[i - 1] || | |
| 59 | 16450 | graph.xpins[i] > graph.pins.size()) { | |
| 60 | ✗ | Fail("query log edge range is invalid"); | |
| 61 | } | ||
| 62 | } | ||
| 63 | 524432 | for (uint32_t vertex : graph.pins) { | |
| 64 | 524410 | if (vertex >= graph.vertex_count) { | |
| 65 | 6 | Fail("query log vertex is out of range"); | |
| 66 | } | ||
| 67 | } | ||
| 68 | 22 | } | |
| 69 | |||
| 70 | 60 | void ReadAll(const std::string& path, std::vector<unsigned char>* out) { | |
| 71 | 60 | std::ifstream input(path, std::ios::binary); | |
| 72 | 60 | if (!input) { | |
| 73 | ✗ | Fail("cannot open " + path); | |
| 74 | } | ||
| 75 | 60 | input.seekg(0, std::ios::end); | |
| 76 | 60 | const auto size = input.tellg(); | |
| 77 | 60 | if (size < 0) { | |
| 78 | ✗ | Fail("cannot size " + path); | |
| 79 | } | ||
| 80 | 60 | input.seekg(0); | |
| 81 | 60 | out->resize(static_cast<size_t>(size)); | |
| 82 | 60 | if (!out->empty()) { | |
| 83 | 60 | input.read(reinterpret_cast<char*>(out->data()), size); | |
| 84 | 60 | if (!input) { | |
| 85 | ✗ | Fail("truncated read " + path); | |
| 86 | } | ||
| 87 | } | ||
| 88 | 60 | } | |
| 89 | |||
| 90 | struct Rows { | ||
| 91 | std::vector<uint64_t> keys; | ||
| 92 | std::vector<std::vector<Location>> copies; | ||
| 93 | }; | ||
| 94 | |||
| 95 | 22 | Rows RowsFromParts(const std::vector<uint64_t>& keys, | |
| 96 | const std::vector<std::vector<uint32_t>>& pages_of_vertex, | ||
| 97 | uint32_t row_size) { | ||
| 98 | 22 | Rows rows; | |
| 99 | 22 | rows.keys = keys; | |
| 100 | 22 | rows.copies.resize(keys.size()); | |
| 101 | 22 | std::vector<std::pair<uint64_t, uint32_t>> order; | |
| 102 | 22 | order.reserve(keys.size()); | |
| 103 | 524390 | for (uint32_t vertex = 0; vertex < keys.size(); ++vertex) { | |
| 104 | 524368 | order.push_back({keys[vertex], vertex}); | |
| 105 | } | ||
| 106 | 22 | std::sort(order.begin(), order.end()); | |
| 107 | 22 | std::vector<std::vector<uint32_t>> members(1); | |
| 108 | 524390 | for (uint32_t vertex = 0; vertex < pages_of_vertex.size(); ++vertex) { | |
| 109 | 1048744 | for (uint32_t page : pages_of_vertex[vertex]) { | |
| 110 | 524376 | if (page >= members.size()) { | |
| 111 | 38 | members.resize(page + 1); | |
| 112 | } | ||
| 113 | 524376 | members[page].push_back(vertex); | |
| 114 | } | ||
| 115 | } | ||
| 116 | 22 | std::vector<std::unordered_map<uint32_t, uint32_t>> offset(members.size()); | |
| 117 | 16448 | for (uint32_t page = 0; page < members.size(); ++page) { | |
| 118 | 16426 | auto& group = members[page]; | |
| 119 | 16426 | std::sort(group.begin(), group.end(), [&](uint32_t a, uint32_t b) { | |
| 120 | 1654876 | return keys[a] < keys[b]; | |
| 121 | }); | ||
| 122 | 16426 | group.erase(std::unique(group.begin(), group.end()), group.end()); | |
| 123 | 540802 | for (uint32_t slot = 0; slot < group.size(); ++slot) { | |
| 124 | 524376 | offset[page][group[slot]] = slot * row_size; | |
| 125 | } | ||
| 126 | } | ||
| 127 | 524390 | for (size_t row = 0; row < order.size(); ++row) { | |
| 128 | 524368 | const uint32_t vertex = order[row].second; | |
| 129 | 524368 | rows.keys[row] = order[row].first; | |
| 130 | 1048744 | for (uint32_t page : pages_of_vertex[vertex]) { | |
| 131 | 524376 | rows.copies[row].push_back(Location{page, offset[page].at(vertex)}); | |
| 132 | } | ||
| 133 | } | ||
| 134 | 44 | return rows; | |
| 135 | 22 | } | |
| 136 | |||
| 137 | Artifact | ||
| 138 | 148 | Finish(Strategy strategy, uint32_t page_size, uint32_t row_size, Rows rows) { | |
| 139 | 148 | if (strategy != Strategy::kPlain && strategy != Strategy::kBandana && | |
| 140 | strategy != Strategy::kMaxEmbed) { | ||
| 141 | 6 | Fail("unknown SSD layout strategy"); | |
| 142 | } | ||
| 143 | 146 | const uint32_t slots = SlotsPerPage(page_size, row_size); | |
| 144 | 146 | Artifact artifact; | |
| 145 | 146 | artifact.strategy = strategy; | |
| 146 | 146 | artifact.page_size = page_size; | |
| 147 | 146 | artifact.row_size = row_size; | |
| 148 | 146 | artifact.keys = std::move(rows.keys); | |
| 149 | 146 | artifact.copies = std::move(rows.copies); | |
| 150 | 146 | if (artifact.keys.size() != artifact.copies.size()) { | |
| 151 | ✗ | Fail("SSD layout key and copy counts differ"); | |
| 152 | } | ||
| 153 | 146 | std::unordered_set<uint64_t> seen_keys; | |
| 154 | 146 | std::unordered_set<uint64_t> seen_slots; | |
| 155 | 146 | uint32_t page_count = 0; | |
| 156 | 525202 | for (size_t i = 0; i < artifact.keys.size(); ++i) { | |
| 157 | 525056 | const uint64_t key = artifact.keys[i]; | |
| 158 | 525056 | if (i > 0 && key <= artifact.keys[i - 1]) { | |
| 159 | ✗ | Fail("SSD layout keys must be strictly increasing"); | |
| 160 | } | ||
| 161 | 525056 | if (key > kMaxKey || !seen_keys.insert(key).second) { | |
| 162 | ✗ | Fail("SSD layout key is duplicated or out of range"); | |
| 163 | } | ||
| 164 | 525056 | if (artifact.copies[i].empty()) { | |
| 165 | ✗ | Fail("SSD layout key has no page"); | |
| 166 | } | ||
| 167 | 1050288 | for (const Location& copy : artifact.copies[i]) { | |
| 168 | 525232 | if (copy.byte_offset / row_size >= slots || | |
| 169 | 525232 | copy.byte_offset % row_size != 0) { | |
| 170 | ✗ | Fail("SSD layout slot is outside its page"); | |
| 171 | } | ||
| 172 | 525232 | if (copy.page_id >= std::numeric_limits<uint32_t>::max()) { | |
| 173 | ✗ | Fail("SSD layout page id exceeds uint32 range"); | |
| 174 | } | ||
| 175 | 525232 | page_count = | |
| 176 | 525232 | std::max(page_count, static_cast<uint32_t>(copy.page_id + 1)); | |
| 177 | 525232 | const uint64_t slot = | |
| 178 | 525232 | (copy.page_id << 32) | static_cast<uint64_t>(copy.byte_offset); | |
| 179 | 525232 | if (!seen_slots.insert(slot).second) { | |
| 180 | ✗ | Fail("SSD layout slot is duplicated"); | |
| 181 | } | ||
| 182 | } | ||
| 183 | } | ||
| 184 | 146 | artifact.pages.resize(page_count); | |
| 185 | 525202 | for (size_t i = 0; i < artifact.keys.size(); ++i) { | |
| 186 | 1050288 | for (const Location& copy : artifact.copies[i]) { | |
| 187 | 1050464 | artifact.pages[copy.page_id].push_back( | |
| 188 | 525232 | {artifact.keys[i], copy.byte_offset}); | |
| 189 | } | ||
| 190 | } | ||
| 191 | 16838 | for (auto& page : artifact.pages) { | |
| 192 | 16692 | if (page.empty() || page.size() > slots) { | |
| 193 | ✗ | Fail("SSD layout page is empty or over capacity"); | |
| 194 | } | ||
| 195 | 16692 | std::sort(page.begin(), page.end()); | |
| 196 | } | ||
| 197 | 292 | return artifact; | |
| 198 | 146 | } | |
| 199 | |||
| 200 | 18 | std::vector<uint32_t> PartitionVertices(const Hypergraph& graph, uint32_t cap) { | |
| 201 | 18 | const uint64_t count = graph.vertex_count; | |
| 202 | 18 | std::vector<char> seen(count, 0); | |
| 203 | 524402 | for (uint32_t vertex : graph.pins) { | |
| 204 | 524384 | seen[vertex] = 1; | |
| 205 | } | ||
| 206 | 18 | std::vector<uint32_t> hot; | |
| 207 | 18 | std::vector<uint32_t> cold; | |
| 208 | 18 | hot.reserve(count); | |
| 209 | 524370 | for (uint32_t vertex = 0; vertex < count; ++vertex) { | |
| 210 | 524352 | (seen[vertex] ? hot : cold).push_back(vertex); | |
| 211 | } | ||
| 212 | 18 | std::mt19937 rng(1); | |
| 213 | 18 | std::shuffle(hot.begin(), hot.end(), rng); | |
| 214 | |||
| 215 | struct Edge { | ||
| 216 | uint64_t begin; | ||
| 217 | uint64_t end; | ||
| 218 | }; | ||
| 219 | 18 | std::vector<Edge> edges; | |
| 220 | 18 | uint64_t longest = 1; | |
| 221 | 16450 | for (uint64_t i = 0; i + 1 < graph.xpins.size(); ++i) { | |
| 222 | 16432 | const uint64_t begin = graph.xpins[i]; | |
| 223 | 16432 | const uint64_t end = graph.xpins[i + 1]; | |
| 224 | 16432 | if (end < begin || end > graph.pins.size()) { | |
| 225 | ✗ | Fail("query log edge range is invalid"); | |
| 226 | } | ||
| 227 | 16432 | if (end - begin >= 2) { | |
| 228 | 16432 | edges.push_back({begin, end}); | |
| 229 | 16432 | longest = std::max(longest, end - begin); | |
| 230 | } | ||
| 231 | } | ||
| 232 | 18 | if (edges.size() > std::numeric_limits<uint32_t>::max()) { | |
| 233 | ✗ | Fail("SSD layout edge count exceeds uint32"); | |
| 234 | } | ||
| 235 | 18 | std::vector<std::vector<uint32_t>> incident_edges(count); | |
| 236 | 16450 | for (uint32_t edge = 0; edge < edges.size(); ++edge) { | |
| 237 | 540816 | for (uint64_t pin = edges[edge].begin; pin < edges[edge].end; ++pin) { | |
| 238 | 524384 | incident_edges[graph.pins[pin]].push_back(edge); | |
| 239 | } | ||
| 240 | } | ||
| 241 | 18 | std::vector<float> table(longest + 2); | |
| 242 | 150 | for (int i = -1; i <= static_cast<int>(longest); ++i) { | |
| 243 | 132 | table[static_cast<size_t>(i + 1)] = std::pow(1.f - kBalanceP, i); | |
| 244 | } | ||
| 245 | 2949176 | const auto at = [&](int i) { return table[static_cast<size_t>(i + 1)]; }; | |
| 246 | |||
| 247 | 18 | std::vector<uint32_t> idx = std::move(hot); | |
| 248 | 18 | std::vector<uint32_t> part(count, 0); | |
| 249 | 18 | std::vector<char> side(count, 0); | |
| 250 | 18 | std::vector<float> gain(count, 0); | |
| 251 | 18 | std::vector<uint32_t> span_epoch(count, 0); | |
| 252 | 18 | std::vector<uint32_t> edge_epoch(edges.size(), 0); | |
| 253 | 18 | uint32_t next_epoch = 1; | |
| 254 | 18 | uint32_t next_part = 0; | |
| 255 | |||
| 256 | // ponytail: adjacency costs O(vertices + pins) memory. Stream subgraphs if | ||
| 257 | // traces outgrow RAM. | ||
| 258 | 16396 | const auto refine = [&](size_t begin, size_t mid, size_t end) { | |
| 259 | 16396 | if (next_epoch == 0) { | |
| 260 | ✗ | std::fill(span_epoch.begin(), span_epoch.end(), 0); | |
| 261 | ✗ | std::fill(edge_epoch.begin(), edge_epoch.end(), 0); | |
| 262 | ✗ | next_epoch = 1; | |
| 263 | } | ||
| 264 | 16396 | const uint32_t epoch = next_epoch++; | |
| 265 | 3424296 | for (size_t i = begin; i < mid; ++i) { | |
| 266 | 3407900 | side[idx[i]] = 0; | |
| 267 | 3407900 | span_epoch[idx[i]] = epoch; | |
| 268 | } | ||
| 269 | 3424296 | for (size_t i = mid; i < end; ++i) { | |
| 270 | 3407900 | side[idx[i]] = 1; | |
| 271 | 3407900 | span_epoch[idx[i]] = epoch; | |
| 272 | } | ||
| 273 | 16396 | std::vector<uint32_t> relevant_edges; | |
| 274 | 6832196 | for (size_t i = begin; i < end; ++i) { | |
| 275 | 13631628 | for (uint32_t edge : incident_edges[idx[i]]) { | |
| 276 | 6815828 | if (edge_epoch[edge] != epoch) { | |
| 277 | 214570 | edge_epoch[edge] = epoch; | |
| 278 | 214570 | relevant_edges.push_back(edge); | |
| 279 | } | ||
| 280 | } | ||
| 281 | } | ||
| 282 | 16396 | std::sort(relevant_edges.begin(), relevant_edges.end()); | |
| 283 | 31558 | for (int iter = 0; iter < kMaxRefine; ++iter) { | |
| 284 | 23535264 | for (size_t i = begin; i < end; ++i) { | |
| 285 | 23504184 | gain[idx[i]] = 0.f; | |
| 286 | } | ||
| 287 | 768374 | for (uint32_t edge_id : relevant_edges) { | |
| 288 | 737294 | const Edge& edge = edges[edge_id]; | |
| 289 | 737294 | int left = 0; | |
| 290 | 737294 | int right = 0; | |
| 291 | 24329442 | for (uint64_t pin = edge.begin; pin < edge.end; ++pin) { | |
| 292 | 23592148 | const uint32_t vertex = graph.pins[pin]; | |
| 293 | 23592148 | if (span_epoch[vertex] != epoch) { | |
| 294 | 87936 | continue; | |
| 295 | } | ||
| 296 | 23504212 | ++(side[vertex] == 0 ? left : right); | |
| 297 | } | ||
| 298 | 737294 | if (left + right < 2) { | |
| 299 | ✗ | continue; | |
| 300 | } | ||
| 301 | 737294 | const float move_right = -(at(right) - at(left - 1)); | |
| 302 | 737294 | const float move_left = -(at(left) - at(right - 1)); | |
| 303 | 24329442 | for (uint64_t pin = edge.begin; pin < edge.end; ++pin) { | |
| 304 | 23592148 | const uint32_t vertex = graph.pins[pin]; | |
| 305 | 23592148 | if (span_epoch[vertex] == epoch) { | |
| 306 | 23504212 | gain[vertex] += side[vertex] == 0 ? move_right : move_left; | |
| 307 | } | ||
| 308 | } | ||
| 309 | } | ||
| 310 | 31080 | std::sort(idx.begin() + static_cast<std::ptrdiff_t>(begin), | |
| 311 | 31080 | idx.begin() + static_cast<std::ptrdiff_t>(mid), | |
| 312 | 118218516 | [&](uint32_t a, uint32_t b) { return gain[a] > gain[b]; }); | |
| 313 | 31080 | std::sort(idx.begin() + static_cast<std::ptrdiff_t>(mid), | |
| 314 | 31080 | idx.begin() + static_cast<std::ptrdiff_t>(end), | |
| 315 | 117755798 | [&](uint32_t a, uint32_t b) { return gain[a] > gain[b]; }); | |
| 316 | 31080 | bool moved = false; | |
| 317 | 881168 | for (size_t i = begin; i < mid; ++i) { | |
| 318 | 879968 | const size_t other = mid + (i - begin); | |
| 319 | 879968 | if (other >= end) { | |
| 320 | ✗ | break; | |
| 321 | } | ||
| 322 | 879968 | if (gain[idx[i]] + gain[idx[other]] <= 0.f) { | |
| 323 | 29880 | break; | |
| 324 | } | ||
| 325 | 850088 | std::swap(idx[i], idx[other]); | |
| 326 | 850088 | side[idx[i]] = 0; | |
| 327 | 850088 | side[idx[other]] = 1; | |
| 328 | 850088 | moved = true; | |
| 329 | } | ||
| 330 | 31080 | if (!moved) { | |
| 331 | 15918 | return; | |
| 332 | } | ||
| 333 | } | ||
| 334 | 16396 | }; | |
| 335 | |||
| 336 | const auto divide = | ||
| 337 | 32810 | [&](auto&& self, size_t begin, size_t end, uint32_t limit) -> void { | |
| 338 | 32810 | if (end - begin <= limit) { | |
| 339 | 16414 | const uint32_t id = next_part++; | |
| 340 | 540766 | for (size_t i = begin; i < end; ++i) { | |
| 341 | 524352 | part[idx[i]] = id; | |
| 342 | } | ||
| 343 | 16414 | return; | |
| 344 | } | ||
| 345 | 16396 | size_t mid = begin + ((end - begin) / (2 * limit)) * limit; | |
| 346 | 16396 | if (end - begin < static_cast<size_t>(2) * limit) { | |
| 347 | ✗ | mid = begin + (end - begin) / 2; | |
| 348 | } | ||
| 349 | 16396 | refine(begin, mid, end); | |
| 350 | 16396 | self(self, begin, mid, limit); | |
| 351 | 16396 | self(self, mid, end, limit); | |
| 352 | 18 | }; | |
| 353 | 18 | if (!idx.empty()) { | |
| 354 | 18 | divide(divide, 0, idx.size(), cap); | |
| 355 | } | ||
| 356 | 18 | uint32_t filled = cap; | |
| 357 | 18 | for (uint32_t vertex : cold) { | |
| 358 | ✗ | if (filled == cap) { | |
| 359 | ✗ | ++next_part; | |
| 360 | ✗ | filled = 0; | |
| 361 | } | ||
| 362 | ✗ | part[vertex] = next_part - 1; | |
| 363 | ✗ | ++filled; | |
| 364 | } | ||
| 365 | 36 | return part; | |
| 366 | 18 | } | |
| 367 | |||
| 368 | std::vector<uint32_t> | ||
| 369 | 4 | PrimaryPages(const Artifact& artifact, const std::vector<uint64_t>& keys) { | |
| 370 | 4 | std::unordered_map<uint64_t, uint32_t> page_of_key; | |
| 371 | 4 | page_of_key.reserve(artifact.keys.size()); | |
| 372 | 20 | for (size_t i = 0; i < artifact.keys.size(); ++i) { | |
| 373 | 16 | page_of_key.emplace( | |
| 374 | 16 | artifact.keys[i], | |
| 375 | 32 | static_cast<uint32_t>(artifact.copies[i].at(0).page_id)); | |
| 376 | } | ||
| 377 | 4 | std::vector<uint32_t> pages(keys.size()); | |
| 378 | 20 | for (size_t vertex = 0; vertex < keys.size(); ++vertex) { | |
| 379 | 16 | const auto found = page_of_key.find(keys[vertex]); | |
| 380 | 16 | if (found == page_of_key.end()) { | |
| 381 | ✗ | Fail("replication key is missing from the partitioned layout"); | |
| 382 | } | ||
| 383 | 16 | pages[vertex] = found->second; | |
| 384 | } | ||
| 385 | 8 | return pages; | |
| 386 | 4 | } | |
| 387 | |||
| 388 | 1542 | void AppendPod(std::vector<unsigned char>* out, const void* data, size_t size) { | |
| 389 | 1542 | const auto* bytes = static_cast<const unsigned char*>(data); | |
| 390 | 1542 | out->insert(out->end(), bytes, bytes + size); | |
| 391 | 1542 | } | |
| 392 | |||
| 393 | template <typename T> | ||
| 394 | 1510 | void Append(std::vector<unsigned char>* out, const T& value) { | |
| 395 | 1510 | AppendPod(out, &value, sizeof(value)); | |
| 396 | 1510 | } | |
| 397 | |||
| 398 | template <typename T> | ||
| 399 | 1554 | T ReadAt(const std::vector<unsigned char>& bytes, size_t* offset) { | |
| 400 | 1554 | if (*offset + sizeof(T) > bytes.size()) { | |
| 401 | ✗ | Fail("truncated SSD layout artifact"); | |
| 402 | } | ||
| 403 | T value; | ||
| 404 | 1554 | std::memcpy(&value, bytes.data() + *offset, sizeof(value)); | |
| 405 | 1554 | *offset += sizeof(value); | |
| 406 | 1554 | return value; | |
| 407 | } | ||
| 408 | |||
| 409 | } // namespace | ||
| 410 | |||
| 411 | 34 | Strategy ParseStrategy(const std::string& name) { | |
| 412 | 34 | if (name == "plain") { | |
| 413 | 2 | return Strategy::kPlain; | |
| 414 | } | ||
| 415 | 32 | if (name == "bandana") { | |
| 416 | 22 | return Strategy::kBandana; | |
| 417 | } | ||
| 418 | 10 | if (name == "maxembed") { | |
| 419 | 8 | return Strategy::kMaxEmbed; | |
| 420 | } | ||
| 421 | 2 | Fail("unknown SSD layout strategy: " + name); | |
| 422 | } | ||
| 423 | |||
| 424 | ✗ | const char* StrategyName(Strategy strategy) { | |
| 425 | ✗ | switch (strategy) { | |
| 426 | ✗ | case Strategy::kPlain: | |
| 427 | ✗ | return "plain"; | |
| 428 | ✗ | case Strategy::kBandana: | |
| 429 | ✗ | return "bandana"; | |
| 430 | ✗ | case Strategy::kMaxEmbed: | |
| 431 | ✗ | return "maxembed"; | |
| 432 | } | ||
| 433 | ✗ | return "unknown"; | |
| 434 | } | ||
| 435 | |||
| 436 | 26 | Hypergraph ReadQueryLog(const std::string& path, bool binary) { | |
| 437 | 26 | std::vector<unsigned char> bytes; | |
| 438 | 26 | ReadAll(path, &bytes); | |
| 439 | 26 | Hypergraph graph; | |
| 440 | 26 | if (binary) { | |
| 441 | 4 | size_t offset = 0; | |
| 442 | 8 | const auto need = [&](size_t count, size_t width) { | |
| 443 | 16 | if (offset > bytes.size() || | |
| 444 | 8 | (width != 0 && count > (bytes.size() - offset) / width)) { | |
| 445 | ✗ | Fail("truncated binary query log"); | |
| 446 | } | ||
| 447 | 8 | }; | |
| 448 | 4 | need(2, sizeof(uint64_t)); | |
| 449 | 4 | uint64_t queries = 0; | |
| 450 | 4 | uint64_t vertices = 0; | |
| 451 | 4 | std::memcpy(&queries, bytes.data() + offset, sizeof(queries)); | |
| 452 | 4 | offset += sizeof(queries); | |
| 453 | 4 | std::memcpy(&vertices, bytes.data() + offset, sizeof(vertices)); | |
| 454 | 4 | offset += sizeof(vertices); | |
| 455 | 4 | if (queries > std::numeric_limits<uint32_t>::max()) { | |
| 456 | 6 | Fail("query log query count exceeds uint32 range"); | |
| 457 | } | ||
| 458 | 2 | graph.vertex_count = vertices; | |
| 459 | 2 | graph.xpins.resize(queries + 1); | |
| 460 | 2 | need(queries + 1, sizeof(uint64_t)); | |
| 461 | 6 | std::memcpy(graph.xpins.data(), | |
| 462 | 2 | bytes.data() + offset, | |
| 463 | 2 | (queries + 1) * sizeof(uint64_t)); | |
| 464 | 2 | offset += (queries + 1) * sizeof(uint64_t); | |
| 465 | 2 | if (graph.xpins.empty() || graph.xpins.front() != 0) { | |
| 466 | ✗ | Fail("binary query log index must start at zero"); | |
| 467 | } | ||
| 468 | 8 | for (size_t i = 1; i < graph.xpins.size(); ++i) { | |
| 469 | 6 | if (graph.xpins[i] < graph.xpins[i - 1]) { | |
| 470 | ✗ | Fail("binary query log index is not monotonic"); | |
| 471 | } | ||
| 472 | } | ||
| 473 | 2 | graph.pins.resize(graph.xpins.back()); | |
| 474 | 2 | need(graph.pins.size(), sizeof(uint32_t)); | |
| 475 | 2 | if (!graph.pins.empty()) { | |
| 476 | 2 | std::memcpy(graph.pins.data(), | |
| 477 | 2 | bytes.data() + offset, | |
| 478 | 2 | graph.pins.size() * sizeof(uint32_t)); | |
| 479 | } | ||
| 480 | 2 | return graph; | |
| 481 | } | ||
| 482 | |||
| 483 | 22 | std::ifstream input(path); | |
| 484 | 22 | if (!input) { | |
| 485 | ✗ | Fail("cannot open " + path); | |
| 486 | } | ||
| 487 | 22 | std::string line; | |
| 488 | 22 | if (!std::getline(input, line)) { | |
| 489 | ✗ | Fail("text query log header is invalid"); | |
| 490 | } | ||
| 491 | 22 | std::istringstream header(line); | |
| 492 | 22 | uint64_t starting = 0; | |
| 493 | 22 | uint64_t vertices = 0; | |
| 494 | 22 | uint64_t queries = 0; | |
| 495 | 22 | uint64_t declared_pins = 0; | |
| 496 | 22 | if (!(header >> starting >> vertices >> queries >> declared_pins)) { | |
| 497 | ✗ | Fail("text query log header is invalid"); | |
| 498 | } | ||
| 499 | 22 | if (queries > std::numeric_limits<uint32_t>::max()) { | |
| 500 | 6 | Fail("query log query count exceeds uint32 range"); | |
| 501 | } | ||
| 502 | 20 | graph.vertex_count = vertices; | |
| 503 | 20 | graph.xpins.resize(queries + 1); | |
| 504 | 20 | graph.pins.reserve(declared_pins); | |
| 505 | 20 | graph.xpins[0] = 0; | |
| 506 | 78 | for (uint64_t query = 0; query < queries; ++query) { | |
| 507 | 58 | if (!std::getline(input, line)) { | |
| 508 | ✗ | Fail("text query log is missing a query"); | |
| 509 | } | ||
| 510 | 58 | std::istringstream row(line); | |
| 511 | 58 | std::unordered_set<uint32_t> unique; | |
| 512 | 58 | uint64_t value = 0; | |
| 513 | 174 | while (row >> value) { | |
| 514 | 116 | if (value < starting || value - starting >= vertices) { | |
| 515 | ✗ | Fail("text query log vertex is out of range"); | |
| 516 | } | ||
| 517 | 116 | const auto vertex = static_cast<uint32_t>(value - starting); | |
| 518 | 116 | if (unique.insert(vertex).second) { | |
| 519 | 116 | graph.pins.push_back(vertex); | |
| 520 | } | ||
| 521 | } | ||
| 522 | 58 | graph.xpins[query + 1] = graph.pins.size(); | |
| 523 | 58 | } | |
| 524 | 20 | if (graph.pins.size() > declared_pins) { | |
| 525 | ✗ | Fail("text query log is longer than its header"); | |
| 526 | } | ||
| 527 | 20 | return graph; | |
| 528 | 36 | } | |
| 529 | |||
| 530 | std::vector<uint64_t> | ||
| 531 | 16 | ReadKeyMap(const std::string& path, uint64_t vertex_count) { | |
| 532 | 16 | std::vector<uint64_t> keys(vertex_count); | |
| 533 | 16 | if (path.empty()) { | |
| 534 | 524360 | for (uint64_t vertex = 0; vertex < vertex_count; ++vertex) { | |
| 535 | 524344 | keys[vertex] = vertex; | |
| 536 | } | ||
| 537 | 16 | return keys; | |
| 538 | } | ||
| 539 | ✗ | std::ifstream input(path); | |
| 540 | ✗ | if (!input) { | |
| 541 | ✗ | Fail("cannot open key map " + path); | |
| 542 | } | ||
| 543 | ✗ | for (uint64_t vertex = 0; vertex < vertex_count; ++vertex) { | |
| 544 | ✗ | if (!(input >> keys[vertex]) || keys[vertex] > kMaxKey) { | |
| 545 | ✗ | Fail("key map is short or out of range"); | |
| 546 | } | ||
| 547 | } | ||
| 548 | ✗ | std::unordered_set<uint64_t> unique(keys.begin(), keys.end()); | |
| 549 | ✗ | if (unique.size() != keys.size()) { | |
| 550 | ✗ | Fail("key map contains a duplicate key"); | |
| 551 | } | ||
| 552 | ✗ | return keys; | |
| 553 | ✗ | } | |
| 554 | |||
| 555 | 18 | Artifact Partition(const Hypergraph& graph, | |
| 556 | const std::vector<uint64_t>& keys, | ||
| 557 | uint32_t page_size, | ||
| 558 | uint32_t row_size) { | ||
| 559 | 18 | CheckGraph(graph); | |
| 560 | 18 | if (keys.size() != graph.vertex_count) { | |
| 561 | ✗ | Fail("key map size does not match the query log"); | |
| 562 | } | ||
| 563 | 18 | const uint32_t cap = SlotsPerPage(page_size, row_size); | |
| 564 | 18 | const std::vector<uint32_t> part = PartitionVertices(graph, cap); | |
| 565 | 18 | std::vector<std::vector<uint32_t>> pages(keys.size()); | |
| 566 | 524370 | for (uint32_t vertex = 0; vertex < keys.size(); ++vertex) { | |
| 567 | 524352 | pages[vertex].push_back(part[vertex]); | |
| 568 | } | ||
| 569 | return Finish(Strategy::kBandana, | ||
| 570 | page_size, | ||
| 571 | row_size, | ||
| 572 | 54 | RowsFromParts(keys, pages, row_size)); | |
| 573 | 18 | } | |
| 574 | |||
| 575 | 8 | Artifact Replicate(const Artifact& partitioned, | |
| 576 | const Hypergraph& graph, | ||
| 577 | const std::vector<uint64_t>& keys, | ||
| 578 | double rep_ratio) { | ||
| 579 | 8 | if (!std::isfinite(rep_ratio) || rep_ratio < 0.0) { | |
| 580 | 6 | Fail("replication ratio must be finite and non-negative"); | |
| 581 | } | ||
| 582 | 6 | CheckGraph(graph); | |
| 583 | 8 | if (keys.size() != graph.vertex_count || | |
| 584 | 4 | partitioned.keys.size() != keys.size()) { | |
| 585 | ✗ | Fail("replication inputs do not describe the same vertices"); | |
| 586 | } | ||
| 587 | 4 | auto pages = std::vector<std::vector<uint32_t>>(keys.size()); | |
| 588 | 4 | const std::vector<uint32_t> primary = PrimaryPages(partitioned, keys); | |
| 589 | 4 | uint32_t page_count = 0; | |
| 590 | 20 | for (uint32_t page : primary) { | |
| 591 | 16 | page_count = std::max(page_count, page + 1); | |
| 592 | } | ||
| 593 | 20 | for (uint32_t vertex = 0; vertex < keys.size(); ++vertex) { | |
| 594 | 16 | pages[vertex].push_back(primary[vertex]); | |
| 595 | } | ||
| 596 | 4 | if (rep_ratio == 0.0 || keys.empty()) { | |
| 597 | return Finish(Strategy::kMaxEmbed, | ||
| 598 | ✗ | partitioned.page_size, | |
| 599 | ✗ | partitioned.row_size, | |
| 600 | ✗ | RowsFromParts(keys, pages, partitioned.row_size)); | |
| 601 | } | ||
| 602 | |||
| 603 | const uint32_t cap = | ||
| 604 | 4 | SlotsPerPage(partitioned.page_size, partitioned.row_size); | |
| 605 | const long double requested = | ||
| 606 | 4 | static_cast<long double>(rep_ratio) * keys.size(); | |
| 607 | 4 | if (requested > std::numeric_limits<uint64_t>::max()) { | |
| 608 | ✗ | Fail("replication ratio is too large"); | |
| 609 | } | ||
| 610 | 4 | const uint64_t extra = static_cast<uint64_t>(std::ceil(requested)); | |
| 611 | 4 | const uint64_t replica_pages = | |
| 612 | 4 | extra / cap + static_cast<uint64_t>(extra % cap != 0); | |
| 613 | 4 | std::vector<uint64_t> score(keys.size(), 0); | |
| 614 | 4 | std::vector<std::vector<uint32_t>> edges; | |
| 615 | 16 | for (uint64_t edge = 0; edge + 1 < graph.xpins.size(); ++edge) { | |
| 616 | std::vector<uint32_t> vertices( | ||
| 617 | 12 | graph.pins.begin() + static_cast<std::ptrdiff_t>(graph.xpins[edge]), | |
| 618 | 12 | graph.pins.begin() + | |
| 619 | 24 | static_cast<std::ptrdiff_t>(graph.xpins[edge + 1])); | |
| 620 | 12 | std::sort(vertices.begin(), vertices.end()); | |
| 621 | 24 | vertices.erase( | |
| 622 | 24 | std::unique(vertices.begin(), vertices.end()), vertices.end()); | |
| 623 | 12 | if (vertices.size() < 2) { | |
| 624 | ✗ | continue; | |
| 625 | } | ||
| 626 | 12 | std::unordered_set<uint32_t> parts; | |
| 627 | 36 | for (uint32_t vertex : vertices) { | |
| 628 | 24 | parts.insert(primary[vertex]); | |
| 629 | } | ||
| 630 | 12 | if (parts.size() > 1) { | |
| 631 | 12 | for (uint32_t vertex : vertices) { | |
| 632 | 8 | score[vertex] += parts.size() - 1; | |
| 633 | } | ||
| 634 | } | ||
| 635 | 12 | edges.push_back(std::move(vertices)); | |
| 636 | 12 | } | |
| 637 | 4 | std::vector<uint32_t> ranked(keys.size()); | |
| 638 | 20 | for (uint32_t vertex = 0; vertex < ranked.size(); ++vertex) { | |
| 639 | 16 | ranked[vertex] = vertex; | |
| 640 | } | ||
| 641 | 4 | std::sort(ranked.begin(), ranked.end(), [&](uint32_t a, uint32_t b) { | |
| 642 | 24 | return score[a] > score[b] || (score[a] == score[b] && a < b); | |
| 643 | }); | ||
| 644 | 4 | std::vector<std::vector<uint32_t>> node_edges(keys.size()); | |
| 645 | 16 | for (uint32_t edge = 0; edge < edges.size(); ++edge) { | |
| 646 | 36 | for (uint32_t vertex : edges[edge]) { | |
| 647 | 24 | node_edges[vertex].push_back(edge); | |
| 648 | } | ||
| 649 | } | ||
| 650 | 4 | uint64_t remaining = extra; | |
| 651 | 8 | for (uint64_t replica = 0; | |
| 652 | 8 | replica < replica_pages && replica < ranked.size() && remaining >= 2; | |
| 653 | ++replica) { | ||
| 654 | 4 | const uint32_t center = ranked[replica]; | |
| 655 | 4 | std::unordered_map<uint32_t, uint32_t> neighbor_count; | |
| 656 | 12 | for (uint32_t edge : node_edges[center]) { | |
| 657 | 24 | for (uint32_t vertex : edges[edge]) { | |
| 658 | 16 | if (primary[vertex] != primary[center]) { | |
| 659 | 4 | ++neighbor_count[vertex]; | |
| 660 | } | ||
| 661 | } | ||
| 662 | } | ||
| 663 | 4 | std::vector<std::pair<uint32_t, uint32_t>> neighbors; | |
| 664 | 4 | neighbors.reserve(neighbor_count.size()); | |
| 665 | 8 | for (const auto& item : neighbor_count) { | |
| 666 | 4 | neighbors.push_back({item.second, item.first}); | |
| 667 | } | ||
| 668 | 4 | std::sort( | |
| 669 | ✗ | neighbors.begin(), neighbors.end(), [](const auto& a, const auto& b) { | |
| 670 | ✗ | return a.first > b.first || | |
| 671 | ✗ | (a.first == b.first && a.second < b.second); | |
| 672 | }); | ||
| 673 | 4 | std::vector<uint32_t> chosen{center}; | |
| 674 | 8 | for (const auto& neighbor : neighbors) { | |
| 675 | 4 | if (chosen.size() == std::min<uint64_t>(cap, remaining)) { | |
| 676 | ✗ | break; | |
| 677 | } | ||
| 678 | 4 | chosen.push_back(neighbor.second); | |
| 679 | } | ||
| 680 | 4 | if (chosen.size() < 2) { | |
| 681 | ✗ | continue; | |
| 682 | } | ||
| 683 | 4 | const uint32_t page = page_count++; | |
| 684 | 12 | for (uint32_t vertex : chosen) { | |
| 685 | 8 | pages[vertex].push_back(page); | |
| 686 | } | ||
| 687 | 4 | remaining -= chosen.size(); | |
| 688 | 4 | } | |
| 689 | return Finish(Strategy::kMaxEmbed, | ||
| 690 | 4 | partitioned.page_size, | |
| 691 | 4 | partitioned.row_size, | |
| 692 | 8 | RowsFromParts(keys, pages, partitioned.row_size)); | |
| 693 | 4 | } | |
| 694 | |||
| 695 | 4 | Artifact Shrink(const Artifact& replicated, double rep_ratio) { | |
| 696 | 4 | if (!std::isfinite(rep_ratio) || rep_ratio < 0.0) { | |
| 697 | 6 | Fail("shrink ratio must be finite and non-negative"); | |
| 698 | } | ||
| 699 | const long double requested = | ||
| 700 | 2 | static_cast<long double>(replicated.keys.size()) * | |
| 701 | 2 | (1.0L + static_cast<long double>(rep_ratio)); | |
| 702 | 2 | if (requested > std::numeric_limits<uint64_t>::max()) { | |
| 703 | ✗ | Fail("shrink ratio is too large"); | |
| 704 | } | ||
| 705 | 2 | const uint64_t target = std::max<uint64_t>( | |
| 706 | 2 | replicated.keys.size(), static_cast<uint64_t>(std::ceil(requested))); | |
| 707 | 2 | std::vector<char> primary(replicated.pages.size(), 0); | |
| 708 | 2 | uint64_t copies = 0; | |
| 709 | 10 | for (const auto& row : replicated.copies) { | |
| 710 | 8 | copies += row.size(); | |
| 711 | 8 | if (!row.empty() && row.front().page_id < primary.size()) { | |
| 712 | 8 | primary[row.front().page_id] = 1; | |
| 713 | } | ||
| 714 | } | ||
| 715 | 2 | std::vector<char> drop(replicated.pages.size(), 0); | |
| 716 | 6 | for (uint32_t page = static_cast<uint32_t>(drop.size()); | |
| 717 | 6 | page > 0 && copies > target; | |
| 718 | --page) { | ||
| 719 | 4 | if (primary[page - 1]) { | |
| 720 | ✗ | continue; | |
| 721 | } | ||
| 722 | 4 | copies -= replicated.pages[page - 1].size(); | |
| 723 | 4 | drop[page - 1] = 1; | |
| 724 | } | ||
| 725 | 2 | std::vector<uint32_t> remap(drop.size(), 0); | |
| 726 | 2 | uint32_t kept = 0; | |
| 727 | 10 | for (size_t page = 0; page < drop.size(); ++page) { | |
| 728 | 8 | if (!drop[page]) { | |
| 729 | 4 | remap[page] = kept++; | |
| 730 | } | ||
| 731 | } | ||
| 732 | 2 | Rows rows; | |
| 733 | 2 | rows.keys = replicated.keys; | |
| 734 | 2 | rows.copies.resize(replicated.copies.size()); | |
| 735 | 10 | for (size_t i = 0; i < replicated.copies.size(); ++i) { | |
| 736 | 24 | for (const Location& copy : replicated.copies[i]) { | |
| 737 | 16 | if (!drop[copy.page_id]) { | |
| 738 | 8 | rows.copies[i].push_back( | |
| 739 | 8 | Location{remap[copy.page_id], copy.byte_offset}); | |
| 740 | } | ||
| 741 | } | ||
| 742 | } | ||
| 743 | 2 | return Finish(replicated.strategy, | |
| 744 | 2 | replicated.page_size, | |
| 745 | 2 | replicated.row_size, | |
| 746 | 4 | std::move(rows)); | |
| 747 | 2 | } | |
| 748 | |||
| 749 | 30 | Artifact Normalize(Artifact artifact) { | |
| 750 | 30 | Rows rows; | |
| 751 | 30 | rows.keys = std::move(artifact.keys); | |
| 752 | 30 | rows.copies = std::move(artifact.copies); | |
| 753 | return Finish(artifact.strategy, | ||
| 754 | artifact.page_size, | ||
| 755 | artifact.row_size, | ||
| 756 | 60 | std::move(rows)); | |
| 757 | 30 | } | |
| 758 | |||
| 759 | 32 | void SaveArtifact(const Artifact& artifact, const std::string& path) { | |
| 760 | 32 | CheckArtifact(artifact, artifact.strategy, artifact.row_size); | |
| 761 | 32 | std::vector<unsigned char> bytes; | |
| 762 | 32 | AppendPod(&bytes, kMagic, sizeof(kMagic)); | |
| 763 | 32 | Append<uint32_t>(&bytes, kVersion); | |
| 764 | 32 | Append<uint32_t>(&bytes, static_cast<uint32_t>(artifact.strategy)); | |
| 765 | 32 | Append<uint32_t>(&bytes, artifact.page_size); | |
| 766 | 32 | Append<uint32_t>(&bytes, artifact.row_size); | |
| 767 | 32 | Append<uint64_t>(&bytes, artifact.keys.size()); | |
| 768 | 32 | Append<uint64_t>(&bytes, artifact.pages.size()); | |
| 769 | 32 | uint64_t copy_count = 0; | |
| 770 | 206 | for (const auto& row : artifact.copies) { | |
| 771 | 174 | copy_count += row.size(); | |
| 772 | } | ||
| 773 | 32 | Append<uint64_t>(&bytes, copy_count); | |
| 774 | 206 | for (size_t i = 0; i < artifact.keys.size(); ++i) { | |
| 775 | 174 | Append<uint64_t>(&bytes, artifact.keys[i]); | |
| 776 | 174 | Append<uint32_t>(&bytes, static_cast<uint32_t>(artifact.copies[i].size())); | |
| 777 | 384 | for (const Location& copy : artifact.copies[i]) { | |
| 778 | 210 | Append<uint64_t>(&bytes, copy.page_id); | |
| 779 | 210 | Append<uint32_t>(&bytes, copy.byte_offset); | |
| 780 | } | ||
| 781 | } | ||
| 782 | 98 | for (const auto& page : artifact.pages) { | |
| 783 | 66 | Append<uint32_t>(&bytes, static_cast<uint32_t>(page.size())); | |
| 784 | 276 | for (const auto& item : page) { | |
| 785 | 210 | Append<uint64_t>(&bytes, item.first); | |
| 786 | 210 | Append<uint32_t>(&bytes, item.second); | |
| 787 | } | ||
| 788 | } | ||
| 789 | 32 | Append<uint64_t>(&bytes, Fnv(bytes.data(), bytes.size())); | |
| 790 | 32 | std::ofstream output(path, std::ios::binary | std::ios::trunc); | |
| 791 | 32 | if (!output.write(reinterpret_cast<const char*>(bytes.data()), | |
| 792 | 32 | static_cast<std::streamsize>(bytes.size()))) { | |
| 793 | ✗ | Fail("cannot write " + path); | |
| 794 | } | ||
| 795 | 32 | } | |
| 796 | |||
| 797 | 34 | Artifact LoadArtifact(const std::string& path) { | |
| 798 | 34 | std::vector<unsigned char> bytes; | |
| 799 | 34 | ReadAll(path, &bytes); | |
| 800 | 34 | if (bytes.size() < sizeof(kMagic) + sizeof(uint64_t)) { | |
| 801 | ✗ | Fail("truncated SSD layout artifact"); | |
| 802 | } | ||
| 803 | 34 | const uint64_t stored = [&] { | |
| 804 | 34 | uint64_t value = 0; | |
| 805 | 34 | std::memcpy( | |
| 806 | 34 | &value, bytes.data() + bytes.size() - sizeof(value), sizeof(value)); | |
| 807 | 34 | return value; | |
| 808 | 34 | }(); | |
| 809 | 34 | if (Fnv(bytes.data(), bytes.size() - sizeof(stored)) != stored) { | |
| 810 | 6 | Fail("SSD layout checksum mismatch"); | |
| 811 | } | ||
| 812 | 32 | size_t offset = 0; | |
| 813 | char magic[8]; | ||
| 814 | 32 | std::memcpy(magic, bytes.data(), sizeof(magic)); | |
| 815 | 32 | offset += sizeof(magic); | |
| 816 | 64 | if (std::memcmp(magic, kMagic, sizeof(magic)) != 0 || | |
| 817 | 32 | ReadAt<uint32_t>(bytes, &offset) != kVersion) { | |
| 818 | ✗ | Fail("unsupported SSD layout artifact"); | |
| 819 | } | ||
| 820 | 32 | Artifact artifact; | |
| 821 | 32 | artifact.checksum = stored; | |
| 822 | 32 | artifact.strategy = static_cast<Strategy>(ReadAt<uint32_t>(bytes, &offset)); | |
| 823 | 32 | artifact.page_size = ReadAt<uint32_t>(bytes, &offset); | |
| 824 | 32 | artifact.row_size = ReadAt<uint32_t>(bytes, &offset); | |
| 825 | 32 | const uint64_t key_count = ReadAt<uint64_t>(bytes, &offset); | |
| 826 | 32 | const uint64_t page_count = ReadAt<uint64_t>(bytes, &offset); | |
| 827 | 32 | const uint64_t copy_count = ReadAt<uint64_t>(bytes, &offset); | |
| 828 | 32 | artifact.keys.reserve(key_count); | |
| 829 | 32 | artifact.copies.reserve(key_count); | |
| 830 | 32 | uint64_t seen_copies = 0; | |
| 831 | 210 | for (uint64_t i = 0; i < key_count; ++i) { | |
| 832 | 178 | artifact.keys.push_back(ReadAt<uint64_t>(bytes, &offset)); | |
| 833 | 178 | const uint32_t count = ReadAt<uint32_t>(bytes, &offset); | |
| 834 | 178 | std::vector<Location> copies(count); | |
| 835 | 404 | for (uint32_t copy = 0; copy < count; ++copy) { | |
| 836 | 226 | copies[copy].page_id = ReadAt<uint64_t>(bytes, &offset); | |
| 837 | 226 | copies[copy].byte_offset = ReadAt<uint32_t>(bytes, &offset); | |
| 838 | } | ||
| 839 | 178 | seen_copies += count; | |
| 840 | 178 | artifact.copies.push_back(std::move(copies)); | |
| 841 | 178 | } | |
| 842 | 32 | artifact.pages.resize(page_count); | |
| 843 | 102 | for (uint64_t page = 0; page < page_count; ++page) { | |
| 844 | 70 | const uint32_t count = ReadAt<uint32_t>(bytes, &offset); | |
| 845 | 70 | artifact.pages[page].resize(count); | |
| 846 | 296 | for (uint32_t item = 0; item < count; ++item) { | |
| 847 | 226 | artifact.pages[page][item].first = ReadAt<uint64_t>(bytes, &offset); | |
| 848 | 226 | artifact.pages[page][item].second = ReadAt<uint32_t>(bytes, &offset); | |
| 849 | } | ||
| 850 | } | ||
| 851 | 32 | if (seen_copies != copy_count || offset + sizeof(uint64_t) != bytes.size()) { | |
| 852 | ✗ | Fail("SSD layout artifact has trailing or mismatched records"); | |
| 853 | } | ||
| 854 | 32 | Rows rows; | |
| 855 | 32 | rows.keys = artifact.keys; | |
| 856 | 32 | rows.copies = artifact.copies; | |
| 857 | Artifact checked = Finish( | ||
| 858 | artifact.strategy, | ||
| 859 | artifact.page_size, | ||
| 860 | artifact.row_size, | ||
| 861 | 32 | std::move(rows)); | |
| 862 | 32 | if (checked.pages != artifact.pages) { | |
| 863 | ✗ | Fail("SSD layout page index does not match key placement"); | |
| 864 | } | ||
| 865 | 32 | checked.checksum = stored; | |
| 866 | 64 | return checked; | |
| 867 | 34 | } | |
| 868 | |||
| 869 | 64 | void CheckArtifact( | |
| 870 | const Artifact& artifact, Strategy expected, uint32_t expected_row_size) { | ||
| 871 | 64 | if (artifact.strategy != expected || artifact.row_size != expected_row_size) { | |
| 872 | 6 | Fail("SSD layout strategy or row size mismatch"); | |
| 873 | } | ||
| 874 | 62 | Rows rows; | |
| 875 | 62 | rows.keys = artifact.keys; | |
| 876 | 62 | rows.copies = artifact.copies; | |
| 877 | const Artifact checked = | ||
| 878 | 62 | Finish(expected, artifact.page_size, expected_row_size, std::move(rows)); | |
| 879 | 62 | if (checked.pages != artifact.pages) { | |
| 880 | ✗ | Fail("SSD layout page index does not match key placement"); | |
| 881 | } | ||
| 882 | 62 | } | |
| 883 | |||
| 884 | } // namespace ssd_layout | ||
| 885 |