From 52e4ddcd83b3b64bcf97fdfcfa1120c87b7b3eb4 Mon Sep 17 00:00:00 2001 From: George Hazan Date: Sun, 14 Jun 2020 13:55:06 +0300 Subject: fixes #2450 (Update libmdbx to 0.8.1) --- libs/libmdbx/src/test/ttl.cc | 224 ++++++++++++++++++++++++++++++------------- 1 file changed, 157 insertions(+), 67 deletions(-) (limited to 'libs/libmdbx/src/test/ttl.cc') diff --git a/libs/libmdbx/src/test/ttl.cc b/libs/libmdbx/src/test/ttl.cc index 92e99b82f6..e3927d9cd4 100644 --- a/libs/libmdbx/src/test/ttl.cc +++ b/libs/libmdbx/src/test/ttl.cc @@ -16,18 +16,99 @@ #include #include -static unsigned edge2window(uint64_t edge, unsigned window_max) { - const double rnd = u64_to_double1(bleach64(edge)); - const unsigned window = window_max - std::lrint(std::pow(window_max, rnd)); - return window; -} +/* LY: тест "эмуляцией time-to-live": + * - организуется "скользящее окно", которое двигается вперед вдоль + * числовой оси каждую транзакцию. + * - по переднему краю "скользящего окна" записи добавляются в таблицу, + * а по заднему удаляются. + * - количество добавляемых/удаляемых записей псевдослучайно зависит + * от номера транзакции, но с экспоненциальным распределением. + * - размер "скользящего окна" также псевдослучайно зависит от номера + * транзакции с "отрицательным" экспоненциальным распределением + * MAX_WIDTH - exp(rnd(N)), при уменьшении окна сдвигается задний + * край и удаляются записи позади него. + * + * Таким образом имитируется поведение таблицы с TTL: записи стохастически + * добавляются и удаляются, но изредка происходит массивное удаление. + */ -static unsigned edge2count(uint64_t edge, unsigned count_max) { +unsigned testcase_ttl::edge2count(uint64_t edge) { const double rnd = u64_to_double1(prng64_map1_white(edge)); - const unsigned count = std::lrint(std::pow(count_max, rnd)); + const unsigned count = std::lrint(std::pow(sliding.max_step_size, rnd)); + // average value: (X - 1) / ln(X), where X = sliding.max_step_size return count; } +unsigned testcase_ttl::edge2window(uint64_t edge) { + const double rnd = u64_to_double1(bleach64(edge)); + const unsigned size = sliding.max_window_size - + std::lrint(std::pow(sliding.max_window_size, rnd)); + // average value: Y - (Y - 1) / ln(Y), where Y = sliding.max_window_size + return size; +} + +static inline double estimate(const double x, const double y) { + /* среднее кол-во операций N = X' * Y', где X' и Y' средние значения + * размера окна и кол-ва добавляемых за один шаг записей: + * X' = (X - 1) / ln(X), где X = sliding.max_step_size + * Y' = Y - (Y - 1) / ln(Y), где Y = sliding.max_window_size */ + return (x - 1) / std::log(x) * (y - (y - 1) / std::log(y)); +} + +bool testcase_ttl::setup() { + const unsigned window_top_lower = + 7 /* нижний предел для верхней границы диапазона, в котором будет + стохастически колебаться размер окна */ + ; + const unsigned count_top_lower = + 7 /* нижний предел для верхней границы диапазона, в котором будет + стохастически колебаться кол-во записей добавляемых на одном шаге */ + ; + + /* для параметризации используем подходящие параметры, + * которые не имеют здесь смысла в первоначальном значении. */ + const double ratio = + double(config.params.batch_read ? config.params.batch_read : 1) / + double(config.params.batch_write ? config.params.batch_write : 1); + + /* проще найти двоичным поиском (вариация метода Ньютона) */ + double hi = config.params.test_nops, lo = 1; + double x = std::sqrt(hi + lo) / ratio; + while (hi > lo) { + const double n = estimate(x, x * ratio); + if (n > config.params.test_nops) + hi = x - 1; + else + lo = x + 1; + x = (hi + lo) / 2; + } + + sliding.max_step_size = std::lrint(x); + if (sliding.max_step_size < count_top_lower) + sliding.max_step_size = count_top_lower; + sliding.max_window_size = std::lrint(x * ratio); + if (sliding.max_window_size < window_top_lower) + sliding.max_window_size = window_top_lower; + + while (estimate(sliding.max_step_size, sliding.max_window_size) > + config.params.test_nops * 2.0) { + if (ratio * sliding.max_step_size > sliding.max_window_size) { + if (sliding.max_step_size < count_top_lower) + break; + sliding.max_step_size = sliding.max_step_size * 7 / 8; + } else { + if (sliding.max_window_size < window_top_lower) + break; + sliding.max_window_size = sliding.max_window_size * 7 / 8; + } + } + + log_verbose("come up window_max %u from `batch_read`", + sliding.max_window_size); + log_verbose("come up step_max %u from `batch_write`", sliding.max_step_size); + return inherited::setup(); +} + bool testcase_ttl::run() { int err = db_open__begin__table_create_open_clean(dbi); if (unlikely(err != MDBX_SUCCESS)) { @@ -35,36 +116,6 @@ bool testcase_ttl::run() { return false; } - /* LY: тест "эмуляцией time-to-live": - * - организуется "скользящее окно", которое двигается вперед вдоль - * числовой оси каждую транзакцию. - * - по переднему краю "скользящего окна" записи добавляются в таблицу, - * а по заднему удаляются. - * - количество добавляемых/удаляемых записей псевдослучайно зависит - * от номера транзакции, но с экспоненциальным распределением. - * - размер "скользящего окна" также псевдослучайно зависит от номера - * транзакции с "отрицательным" экспоненциальным распределением - * MAX_WIDTH - exp(rnd(N)), при уменьшении окна сдвигается задний - * край и удаляются записи позади него. - * - * Таким образом имитируется поведение таблицы с TTL: записи стохастически - * добавляются и удаляются, но изредка происходят массивные удаления. - */ - - /* LY: для параметризации используем подходящие параметры, которые не имеют - * здесь смысла в первоначальном значении. */ - const unsigned window_max_lower = 333; - const unsigned count_max_lower = 333; - - const unsigned window_max = (config.params.batch_read > window_max_lower) - ? config.params.batch_read - : window_max_lower; - const unsigned count_max = (config.params.batch_write > count_max_lower) - ? config.params.batch_write - : count_max_lower; - log_verbose("ttl: using `batch_read` value %u for window_max", window_max); - log_verbose("ttl: using `batch_write` value %u for count_max", count_max); - uint64_t seed = prng64_map2_white(config.params.keygen.seed) + config.actor_id; keyvalue_maker.setup(config.params, config.actor_id, 0 /* thread_number */); @@ -77,17 +128,23 @@ bool testcase_ttl::run() { std::deque> fifo; uint64_t serial = 0; bool rc = false; - while (should_continue()) { + unsigned clear_wholetable_passed = 0; + unsigned clear_stepbystep_passed = 0; + unsigned dbfull_passed = 0; + unsigned loops = 0; + bool keyspace_overflow = false; + while (true) { const uint64_t salt = prng64_white(seed) /* mdbx_txn_id(txn_guard.get()) */; const unsigned window_width = - flipcoin_x4() ? 0 : edge2window(salt, window_max); - unsigned head_count = edge2count(salt, count_max); - log_debug("ttl: step #%zu (serial %" PRIu64 + (!should_continue() || flipcoin_x4()) ? 0 : edge2window(salt); + unsigned head_count = edge2count(salt); + log_debug("ttl: step #%" PRIu64 " (serial %" PRIu64 ", window %u, count %u) salt %" PRIu64, nops_completed, serial, window_width, head_count, salt); - if (window_width) { + if (window_width || flipcoin()) { + clear_stepbystep_passed += window_width == 0; while (fifo.size() > window_width) { uint64_t tail_serial = fifo.back().first; const unsigned tail_count = fifo.back().second; @@ -97,7 +154,7 @@ bool testcase_ttl::run() { for (unsigned n = 0; n < tail_count; ++n) { log_trace("ttl: remove-tail %" PRIu64, tail_serial); generate_pair(tail_serial); - err = mdbx_del(txn_guard.get(), dbi, &key->value, &data->value); + err = remove(key, data); if (unlikely(err != MDBX_SUCCESS)) { if (err == MDBX_MAP_FULL && config.params.ignore_dbfull) { log_notice("ttl: tail-bailout due '%s'", mdbx_strerror(err)); @@ -108,11 +165,14 @@ bool testcase_ttl::run() { if (unlikely(!keyvalue_maker.increment(tail_serial, 1))) failure("ttl: unexpected key-space overflow on the tail"); } + report(tail_count); } } else { log_trace("ttl: purge state"); db_table_clear(dbi); fifo.clear(); + clear_wholetable_passed += 1; + report(1); } err = breakable_restart(); @@ -120,38 +180,68 @@ bool testcase_ttl::run() { log_notice("ttl: bailout at commit due '%s'", mdbx_strerror(err)); break; } - fifo.push_front(std::make_pair(serial, head_count)); - retry: - for (unsigned n = 0; n < head_count; ++n) { - log_trace("ttl: insert-head %" PRIu64, serial); - generate_pair(serial); - err = mdbx_put(txn_guard.get(), dbi, &key->value, &data->value, - insert_flags); - if (unlikely(err != MDBX_SUCCESS)) { - if (err == MDBX_MAP_FULL && config.params.ignore_dbfull) { - log_notice("ttl: head-insert skip due '%s'", mdbx_strerror(err)); + if (!speculum_verify()) { + log_notice("ttl: bailout after tail-trim"); + return false; + } + + if (!keyspace_overflow && (should_continue() || !clear_wholetable_passed || + !clear_stepbystep_passed)) { + unsigned underutilization_x256 = + txn_underutilization_x256(txn_guard.get()); + if (dbfull_passed > underutilization_x256) { + log_notice("ttl: skip head-grow to avoid one more dbfull (was %u, " + "underutilization %.2f%%)", + dbfull_passed, underutilization_x256 / 2.560); + continue; + } + fifo.push_front(std::make_pair(serial, head_count)); + retry: + for (unsigned n = 0; n < head_count; ++n) { + log_trace("ttl: insert-head %" PRIu64, serial); + generate_pair(serial); + err = insert(key, data, insert_flags); + if (unlikely(err != MDBX_SUCCESS)) { + if ((err == MDBX_TXN_FULL || err == MDBX_MAP_FULL) && + config.params.ignore_dbfull) { + log_notice("ttl: head-insert skip due '%s'", mdbx_strerror(err)); + txn_restart(true, false); + serial = fifo.front().first; + fifo.front().second = head_count = n; + dbfull_passed += 1; + goto retry; + } + failure_perror("mdbx_put(head)", err); + } + + if (unlikely(!keyvalue_maker.increment(serial, 1))) { + log_notice("ttl: unexpected key-space overflow"); + keyspace_overflow = true; txn_restart(true, false); serial = fifo.front().first; fifo.front().second = head_count = n; goto retry; } - failure_perror("mdbx_put(head)", err); } - - if (unlikely(!keyvalue_maker.increment(serial, 1))) { - log_notice("ttl: unexpected key-space overflow"); - goto bailout; + err = breakable_restart(); + if (unlikely(err != MDBX_SUCCESS)) { + log_notice("ttl: head-commit skip due '%s'", mdbx_strerror(err)); + serial = fifo.front().first; + fifo.pop_front(); } + if (!speculum_verify()) { + log_notice("ttl: bailout after head-grow"); + return false; + } + loops += 1; + } else if (fifo.empty()) { + log_notice("ttl: done %u whole loops, %" PRIu64 " ops, %" PRIu64 " items", + loops, nops_completed, serial); + rc = true; + break; + } else { + log_notice("ttl: done, wait for empty, skip head-grow"); } - err = breakable_restart(); - if (unlikely(err != MDBX_SUCCESS)) { - log_notice("ttl: head-commit skip due '%s'", mdbx_strerror(err)); - serial = fifo.front().first; - fifo.pop_front(); - } - - report(1); - rc = true; } bailout: -- cgit v1.2.3