| 1 | // SPDX-License-Identifier: GPL-3.0-or-later |
| 2 | |
| 3 | #ifndef NETDATA_ND_SD_JOURNAL_SAMPLING_H |
| 4 | #define NETDATA_ND_SD_JOURNAL_SAMPLING_H |
| 5 | |
| 6 | // ---------------------------------------------------------------------------- |
| 7 | // sampling support |
| 8 | |
| 9 | static __always_inline |
| 10 | void sampling_query_init(LOGS_QUERY_STATUS *lqs, FACETS *facets) |
| 11 | { |
| 12 | if (!lqs->rq.sampling) |
| 13 | return; |
| 14 | |
| 15 | if (!lqs->rq.slice) { |
| 16 | // the user is doing a full data query |
| 17 | // disable sampling |
| 18 | lqs->rq.sampling = 0; |
| 19 | return; |
| 20 | } |
| 21 | |
| 22 | if (lqs->rq.data_only) { |
| 23 | // the user is doing a data query |
| 24 | // disable sampling |
| 25 | lqs->rq.sampling = 0; |
| 26 | return; |
| 27 | } |
| 28 | |
| 29 | if (!lqs->c.files_matched) { |
| 30 | // no files have been matched |
| 31 | // disable sampling |
| 32 | lqs->rq.sampling = 0; |
| 33 | return; |
| 34 | } |
| 35 | |
| 36 | lqs->c.samples.slots = facets_histogram_slots(facets); |
| 37 | if (lqs->c.samples.slots < 2) |
| 38 | lqs->c.samples.slots = 2; |
| 39 | if (lqs->c.samples.slots > ND_SD_JOURNAL_SAMPLING_SLOTS) |
| 40 | lqs->c.samples.slots = ND_SD_JOURNAL_SAMPLING_SLOTS; |
| 41 | |
| 42 | if (!lqs->rq.after_ut || !lqs->rq.before_ut || lqs->rq.after_ut >= lqs->rq.before_ut) { |
| 43 | // we don't have enough information for sampling |
| 44 | lqs->rq.sampling = 0; |
| 45 | return; |
| 46 | } |
| 47 | |
| 48 | usec_t delta = lqs->rq.before_ut - lqs->rq.after_ut; |
| 49 | usec_t step = delta / facets_histogram_slots(facets) - 1; |
| 50 | if (step < 1) |
| 51 | step = 1; |
| 52 | |
| 53 | lqs->c.samples_per_time_slot.start_ut = lqs->rq.after_ut; |
| 54 | lqs->c.samples_per_time_slot.end_ut = lqs->rq.before_ut; |
| 55 | lqs->c.samples_per_time_slot.step_ut = step; |
| 56 | |
| 57 | // the minimum number of rows to enable sampling |
| 58 | lqs->c.samples.enable_after_samples = lqs->rq.sampling / 2; |
| 59 | |
| 60 | size_t files_matched = lqs->c.files_matched; |
| 61 | if (!files_matched) |
| 62 | files_matched = 1; |
| 63 | |
| 64 | // the minimum number of rows per file to enable sampling |
| 65 | lqs->c.samples_per_file.enable_after_samples = (lqs->rq.sampling / 4) / files_matched; |
| 66 | if (lqs->c.samples_per_file.enable_after_samples < lqs->rq.entries) |
| 67 | lqs->c.samples_per_file.enable_after_samples = lqs->rq.entries; |
| 68 | |
| 69 | // the minimum number of rows per time slot to enable sampling |
| 70 | lqs->c.samples_per_time_slot.enable_after_samples = (lqs->rq.sampling / 4) / lqs->c.samples.slots; |
| 71 | if (lqs->c.samples_per_time_slot.enable_after_samples < lqs->rq.entries) |
| 72 | lqs->c.samples_per_time_slot.enable_after_samples = lqs->rq.entries; |
| 73 | } |
| 74 | |
| 75 | static __always_inline |
| 76 | void sampling_file_init(LOGS_QUERY_STATUS *lqs, struct nd_journal_file *jf __maybe_unused) |
| 77 | { |
| 78 | lqs->c.samples_per_file.sampled = 0; |
| 79 | lqs->c.samples_per_file.unsampled = 0; |
| 80 | lqs->c.samples_per_file.estimated = 0; |
| 81 | lqs->c.samples_per_file.every = 0; |
| 82 | lqs->c.samples_per_file.skipped = 0; |
| 83 | lqs->c.samples_per_file.recalibrate = 0; |
| 84 | } |
| 85 | |
| 86 | static __always_inline |
| 87 | size_t sampling_file_lines_scanned_so_far(LOGS_QUERY_STATUS *lqs) |
| 88 | { |
| 89 | size_t sampled = lqs->c.samples_per_file.sampled + lqs->c.samples_per_file.unsampled; |
| 90 | if (!sampled) |
| 91 | sampled = 1; |
| 92 | return sampled; |
| 93 | } |
| 94 | |
| 95 | static __always_inline |
| 96 | void sampling_running_file_query_overlapping_timeframe_ut( |
| 97 | LOGS_QUERY_STATUS *lqs, |
| 98 | struct nd_journal_file *jf, |
| 99 | FACETS_ANCHOR_DIRECTION direction, |
| 100 | usec_t msg_ut, |
| 101 | usec_t *after_ut, |
| 102 | usec_t *before_ut) |
| 103 | { |
| 104 | // find the overlap of the query and file timeframes |
| 105 | // taking into account the first message we encountered |
| 106 | |
| 107 | usec_t oldest_ut, newest_ut; |
| 108 | if (direction == FACETS_ANCHOR_DIRECTION_FORWARD) { |
| 109 | // the first message we know (oldest) |
| 110 | oldest_ut = lqs->c.query_file.first_msg_ut ? lqs->c.query_file.first_msg_ut : jf->msg_first_ut; |
| 111 | if (!oldest_ut) |
| 112 | oldest_ut = lqs->c.query_file.start_ut; |
| 113 | |
| 114 | if (jf->msg_last_ut) |
| 115 | newest_ut = MIN(lqs->c.query_file.stop_ut, jf->msg_last_ut); |
| 116 | else if (jf->file_last_modified_ut) |
| 117 | newest_ut = MIN(lqs->c.query_file.stop_ut, jf->file_last_modified_ut); |
| 118 | else |
| 119 | newest_ut = lqs->c.query_file.stop_ut; |
| 120 | |
| 121 | if (msg_ut < oldest_ut) |
| 122 | oldest_ut = msg_ut - 1; |
| 123 | } else /* BACKWARD */ { |
| 124 | // the latest message we know (newest) |
| 125 | newest_ut = lqs->c.query_file.first_msg_ut ? lqs->c.query_file.first_msg_ut : jf->msg_last_ut; |
| 126 | if (!newest_ut) |
| 127 | newest_ut = lqs->c.query_file.start_ut; |
| 128 | |
| 129 | if (jf->msg_first_ut) |
| 130 | oldest_ut = MAX(lqs->c.query_file.stop_ut, jf->msg_first_ut); |
| 131 | else |
| 132 | oldest_ut = lqs->c.query_file.stop_ut; |
| 133 | |
| 134 | if (newest_ut < msg_ut) |
| 135 | newest_ut = msg_ut + 1; |
| 136 | } |
| 137 | |
| 138 | *after_ut = oldest_ut; |
| 139 | *before_ut = newest_ut; |
| 140 | } |
| 141 | |
| 142 | static __always_inline |
| 143 | double sampling_running_file_query_progress_by_time( |
| 144 | LOGS_QUERY_STATUS *lqs, |
| 145 | struct nd_journal_file *jf, |
| 146 | FACETS_ANCHOR_DIRECTION direction, |
| 147 | usec_t msg_ut) |
| 148 | { |
| 149 | usec_t after_ut, before_ut, elapsed_ut; |
| 150 | sampling_running_file_query_overlapping_timeframe_ut(lqs, jf, direction, msg_ut, &after_ut, &before_ut); |
| 151 | |
| 152 | if (direction == FACETS_ANCHOR_DIRECTION_FORWARD) |
| 153 | elapsed_ut = msg_ut - after_ut; |
| 154 | else |
| 155 | elapsed_ut = before_ut - msg_ut; |
| 156 | |
| 157 | usec_t total_ut = before_ut - after_ut; |
| 158 | double progress = (double)elapsed_ut / (double)total_ut; |
| 159 | |
| 160 | return progress; |
| 161 | } |
| 162 | |
| 163 | static __always_inline |
| 164 | usec_t sampling_running_file_query_remaining_time( |
| 165 | LOGS_QUERY_STATUS *lqs, |
| 166 | struct nd_journal_file *jf, |
| 167 | FACETS_ANCHOR_DIRECTION direction, |
| 168 | usec_t msg_ut, |
| 169 | usec_t *total_time_ut, |
| 170 | usec_t *remaining_start_ut, |
| 171 | usec_t *remaining_end_ut) |
| 172 | { |
| 173 | usec_t after_ut, before_ut; |
| 174 | sampling_running_file_query_overlapping_timeframe_ut(lqs, jf, direction, msg_ut, &after_ut, &before_ut); |
| 175 | |
| 176 | // since we have a timestamp in msg_ut |
| 177 | // this timestamp can extend the overlap |
| 178 | if (msg_ut <= after_ut) |
| 179 | after_ut = msg_ut - 1; |
| 180 | |
| 181 | if (msg_ut >= before_ut) |
| 182 | before_ut = msg_ut + 1; |
| 183 | |
| 184 | // return the remaining duration |
| 185 | usec_t remaining_from_ut, remaining_to_ut; |
| 186 | if (direction == FACETS_ANCHOR_DIRECTION_FORWARD) { |
| 187 | remaining_from_ut = msg_ut; |
| 188 | remaining_to_ut = before_ut; |
| 189 | } else { |
| 190 | remaining_from_ut = after_ut; |
| 191 | remaining_to_ut = msg_ut; |
| 192 | } |
| 193 | |
| 194 | usec_t remaining_ut = remaining_to_ut - remaining_from_ut; |
| 195 | |
| 196 | if (total_time_ut) |
| 197 | *total_time_ut = (before_ut > after_ut) ? before_ut - after_ut : 1; |
| 198 | |
| 199 | if (remaining_start_ut) |
| 200 | *remaining_start_ut = remaining_from_ut; |
| 201 | |
| 202 | if (remaining_end_ut) |
| 203 | *remaining_end_ut = remaining_to_ut; |
| 204 | |
| 205 | return remaining_ut; |
| 206 | } |
| 207 | |
| 208 | static __always_inline |
| 209 | size_t sampling_running_file_query_estimate_remaining_lines_by_time( |
| 210 | LOGS_QUERY_STATUS *lqs, |
| 211 | struct nd_journal_file *jf, |
| 212 | FACETS_ANCHOR_DIRECTION direction, |
| 213 | usec_t msg_ut) |
| 214 | { |
| 215 | size_t scanned_lines = sampling_file_lines_scanned_so_far(lqs); |
| 216 | |
| 217 | // Calculate the proportion of time covered |
| 218 | usec_t total_time_ut, remaining_start_ut, remaining_end_ut; |
| 219 | usec_t remaining_time_ut = sampling_running_file_query_remaining_time( |
| 220 | lqs, jf, direction, msg_ut, &total_time_ut, &remaining_start_ut, &remaining_end_ut); |
| 221 | if (total_time_ut == 0) |
| 222 | total_time_ut = 1; |
| 223 | |
| 224 | double proportion_by_time = (double)(total_time_ut - remaining_time_ut) / (double)total_time_ut; |
| 225 | |
| 226 | if (proportion_by_time == 0 || proportion_by_time > 1.0 || !isfinite(proportion_by_time)) |
| 227 | proportion_by_time = 1.0; |
| 228 | |
| 229 | // Estimate the total number of lines in the file |
| 230 | size_t expected_matching_logs_by_time = (size_t)((double)scanned_lines / proportion_by_time); |
| 231 | |
| 232 | if (jf->messages_in_file && expected_matching_logs_by_time > jf->messages_in_file) |
| 233 | expected_matching_logs_by_time = jf->messages_in_file; |
| 234 | |
| 235 | // Calculate the estimated number of remaining lines |
| 236 | size_t remaining_logs_by_time = expected_matching_logs_by_time - scanned_lines; |
| 237 | if (remaining_logs_by_time < 1) |
| 238 | remaining_logs_by_time = 1; |
| 239 | |
| 240 | // nd_log(NDLS_COLLECTORS, NDLP_INFO, |
| 241 | // "JOURNAL ESTIMATION: '%s' " |
| 242 | // "scanned_lines=%zu [sampled=%zu, unsampled=%zu, estimated=%zu], " |
| 243 | // "file [%"PRIu64" - %"PRIu64", duration %"PRId64", known lines in file %zu], " |
| 244 | // "query [%"PRIu64" - %"PRIu64", duration %"PRId64"], " |
| 245 | // "first message read from the file at %"PRIu64", current message at %"PRIu64", " |
| 246 | // "proportion of time %.2f %%, " |
| 247 | // "expected total lines in file %zu, " |
| 248 | // "remaining lines %zu, " |
| 249 | // "remaining time %"PRIu64" [%"PRIu64" - %"PRIu64", duration %"PRId64"]" |
| 250 | // , jf->filename |
| 251 | // , scanned_lines, fqs->samples_per_file.sampled, fqs->samples_per_file.unsampled, fqs->samples_per_file.estimated |
| 252 | // , jf->msg_first_ut, jf->msg_last_ut, jf->msg_last_ut - jf->msg_first_ut, jf->messages_in_file |
| 253 | // , fqs->query_file.start_ut, fqs->query_file.stop_ut, fqs->query_file.stop_ut - fqs->query_file.start_ut |
| 254 | // , fqs->query_file.first_msg_ut, msg_ut |
| 255 | // , proportion_by_time * 100.0 |
| 256 | // , expected_matching_logs_by_time |
| 257 | // , remaining_logs_by_time |
| 258 | // , remaining_time_ut, remaining_start_ut, remaining_end_ut, remaining_end_ut - remaining_start_ut |
| 259 | // ); |
| 260 | |
| 261 | return remaining_logs_by_time; |
| 262 | } |
| 263 | |
| 264 | static __always_inline |
| 265 | size_t sampling_running_file_query_estimate_remaining_lines( |
| 266 | NsdJournal *j __maybe_unused, |
| 267 | LOGS_QUERY_STATUS *lqs, |
| 268 | struct nd_journal_file *jf, |
| 269 | FACETS_ANCHOR_DIRECTION direction, |
| 270 | usec_t msg_ut) |
| 271 | { |
| 272 | size_t remaining_logs_by_seqnum = 0; |
| 273 | |
| 274 | #ifdef HAVE_SD_JOURNAL_GET_SEQNUM |
| 275 | size_t expected_matching_logs_by_seqnum = 0; |
| 276 | double proportion_by_seqnum = 0.0; |
| 277 | uint64_t current_msg_seqnum; |
| 278 | NsdId128 current_msg_writer; |
| 279 | if (!lqs->c.query_file.first_msg_seqnum || nsd_journal_get_seqnum(j, ¤t_msg_seqnum, ¤t_msg_writer) < 0) { |
| 280 | lqs->c.query_file.first_msg_seqnum = 0; |
| 281 | lqs->c.query_file.first_msg_writer = NSD_ID128_NULL; |
| 282 | } else if (jf->messages_in_file) { |
| 283 | size_t scanned_lines = sampling_file_lines_scanned_so_far(lqs); |
| 284 | |
| 285 | double proportion_of_all_lines_so_far; |
| 286 | if (direction == FACETS_ANCHOR_DIRECTION_FORWARD) |
| 287 | proportion_of_all_lines_so_far = (double)scanned_lines / (double)(current_msg_seqnum - jf->first_seqnum); |
| 288 | else |
| 289 | proportion_of_all_lines_so_far = (double)scanned_lines / (double)(jf->last_seqnum - current_msg_seqnum); |
| 290 | |
| 291 | if (proportion_of_all_lines_so_far > 1.0) |
| 292 | proportion_of_all_lines_so_far = 1.0; |
| 293 | |
| 294 | expected_matching_logs_by_seqnum = (size_t)(proportion_of_all_lines_so_far * (double)jf->messages_in_file); |
| 295 | |
| 296 | proportion_by_seqnum = (double)scanned_lines / (double)expected_matching_logs_by_seqnum; |
| 297 | |
| 298 | if (proportion_by_seqnum == 0 || proportion_by_seqnum > 1.0 || !isfinite(proportion_by_seqnum)) |
| 299 | proportion_by_seqnum = 1.0; |
| 300 | |
| 301 | remaining_logs_by_seqnum = expected_matching_logs_by_seqnum - scanned_lines; |
| 302 | if (!remaining_logs_by_seqnum) |
| 303 | remaining_logs_by_seqnum = 1; |
| 304 | } |
| 305 | #endif |
| 306 | |
| 307 | if (remaining_logs_by_seqnum) |
| 308 | return remaining_logs_by_seqnum; |
| 309 | |
| 310 | return sampling_running_file_query_estimate_remaining_lines_by_time(lqs, jf, direction, msg_ut); |
| 311 | } |
| 312 | |
| 313 | static __always_inline |
| 314 | void sampling_decide_file_sampling_every( |
| 315 | NsdJournal *j, |
| 316 | LOGS_QUERY_STATUS *lqs, |
| 317 | struct nd_journal_file *jf, |
| 318 | FACETS_ANCHOR_DIRECTION direction, |
| 319 | usec_t msg_ut) |
| 320 | { |
| 321 | size_t files_matched = lqs->c.files_matched; |
| 322 | if (!files_matched) |
| 323 | files_matched = 1; |
| 324 | |
| 325 | size_t remaining_lines = sampling_running_file_query_estimate_remaining_lines(j, lqs, jf, direction, msg_ut); |
| 326 | size_t wanted_samples = (lqs->rq.sampling / 2) / files_matched; |
| 327 | if (!wanted_samples) |
| 328 | wanted_samples = 1; |
| 329 | |
| 330 | lqs->c.samples_per_file.every = remaining_lines / wanted_samples; |
| 331 | |
| 332 | if (lqs->c.samples_per_file.every < 1) |
| 333 | lqs->c.samples_per_file.every = 1; |
| 334 | } |
| 335 | |
| 336 | typedef enum { |
| 337 | SAMPLING_STOP_AND_ESTIMATE = -1, |
| 338 | SAMPLING_FULL = 0, |
| 339 | SAMPLING_SKIP_FIELDS = 1, |
| 340 | } sampling_t; |
| 341 | |
| 342 | static __always_inline |
| 343 | sampling_t is_row_in_sample( |
| 344 | NsdJournal *j, |
| 345 | LOGS_QUERY_STATUS *lqs, |
| 346 | struct nd_journal_file *jf, |
| 347 | usec_t msg_ut, |
| 348 | FACETS_ANCHOR_DIRECTION direction, |
| 349 | bool candidate_to_keep) |
| 350 | { |
| 351 | if (!lqs->rq.sampling || candidate_to_keep) |
| 352 | return SAMPLING_FULL; |
| 353 | |
| 354 | if (unlikely(msg_ut < lqs->c.samples_per_time_slot.start_ut)) |
| 355 | msg_ut = lqs->c.samples_per_time_slot.start_ut; |
| 356 | if (unlikely(msg_ut > lqs->c.samples_per_time_slot.end_ut)) |
| 357 | msg_ut = lqs->c.samples_per_time_slot.end_ut; |
| 358 | |
| 359 | size_t slot = (msg_ut - lqs->c.samples_per_time_slot.start_ut) / lqs->c.samples_per_time_slot.step_ut; |
| 360 | if (slot >= lqs->c.samples.slots) |
| 361 | slot = lqs->c.samples.slots - 1; |
| 362 | |
| 363 | bool should_sample = false; |
| 364 | |
| 365 | if (lqs->c.samples.sampled < lqs->c.samples.enable_after_samples || |
| 366 | lqs->c.samples_per_file.sampled < lqs->c.samples_per_file.enable_after_samples || |
| 367 | lqs->c.samples_per_time_slot.sampled[slot] < lqs->c.samples_per_time_slot.enable_after_samples) |
| 368 | should_sample = true; |
| 369 | |
| 370 | else if (lqs->c.samples_per_file.recalibrate >= ND_SD_JOURNAL_SAMPLING_RECALIBRATE || !lqs->c.samples_per_file.every) { |
| 371 | // this is the first to be unsampled for this file |
| 372 | sampling_decide_file_sampling_every(j, lqs, jf, direction, msg_ut); |
| 373 | lqs->c.samples_per_file.recalibrate = 0; |
| 374 | should_sample = true; |
| 375 | } else { |
| 376 | // we sample 1 every fqs->samples_per_file.every |
| 377 | if (lqs->c.samples_per_file.skipped >= lqs->c.samples_per_file.every) { |
| 378 | lqs->c.samples_per_file.skipped = 0; |
| 379 | should_sample = true; |
| 380 | } else |
| 381 | lqs->c.samples_per_file.skipped++; |
| 382 | } |
| 383 | |
| 384 | if (should_sample) { |
| 385 | lqs->c.samples.sampled++; |
| 386 | lqs->c.samples_per_file.sampled++; |
| 387 | lqs->c.samples_per_time_slot.sampled[slot]++; |
| 388 | |
| 389 | return SAMPLING_FULL; |
| 390 | } |
| 391 | |
| 392 | lqs->c.samples_per_file.recalibrate++; |
| 393 | |
| 394 | lqs->c.samples.unsampled++; |
| 395 | lqs->c.samples_per_file.unsampled++; |
| 396 | lqs->c.samples_per_time_slot.unsampled[slot]++; |
| 397 | |
| 398 | if (lqs->c.samples_per_file.unsampled > lqs->c.samples_per_file.sampled) { |
| 399 | double progress_by_time = sampling_running_file_query_progress_by_time(lqs, jf, direction, msg_ut); |
| 400 | |
| 401 | if (progress_by_time > ND_SD_JOURNAL_ENABLE_ESTIMATIONS_FILE_PERCENTAGE) |
| 402 | return SAMPLING_STOP_AND_ESTIMATE; |
| 403 | } |
| 404 | |
| 405 | return SAMPLING_SKIP_FIELDS; |
| 406 | } |
| 407 | |
| 408 | static __always_inline |
| 409 | void sampling_update_running_query_file_estimates( |
| 410 | FACETS *facets, |
| 411 | NsdJournal *j, |
| 412 | LOGS_QUERY_STATUS *lqs, |
| 413 | struct nd_journal_file *jf, |
| 414 | usec_t msg_ut, |
| 415 | FACETS_ANCHOR_DIRECTION direction) |
| 416 | { |
| 417 | usec_t total_time_ut, remaining_start_ut, remaining_end_ut; |
| 418 | sampling_running_file_query_remaining_time( |
| 419 | lqs, jf, direction, msg_ut, &total_time_ut, &remaining_start_ut, &remaining_end_ut); |
| 420 | size_t remaining_lines = sampling_running_file_query_estimate_remaining_lines(j, lqs, jf, direction, msg_ut); |
| 421 | facets_update_estimations(facets, remaining_start_ut, remaining_end_ut, remaining_lines); |
| 422 | lqs->c.samples.estimated += remaining_lines; |
| 423 | lqs->c.samples_per_file.estimated += remaining_lines; |
| 424 | } |
| 425 | |
| 426 | #endif //NETDATA_ND_SD_JOURNAL_SAMPLING_H |