Tarantool
Replies: 9 comments 6 replies
-
|
It might be better to read the secondary key build data files in a separated thread[s] and wait for them before starting building the secondary keys (if we use the approach with separated index recovery data files). |
Beta Was this translation helpful? Give feedback.
-
Addresses or offsets? The example suggests offsets. I'd use addresses different from 1, 2, 3 to avoid confusion. |
Beta Was this translation helpful? Give feedback.
-
|
Addresses, so we can use the .index files as actual tuple pointer containers (by using the map from old to new addresses created on recovery). Updated the example. |
Beta Was this translation helpful? Give feedback.
-
What's the point of wrapping the chunks in Anyway, it'd be nice to estimate the size of such a file for a typical index and the amount of time it'll take to load it in memory. |
Beta Was this translation helpful? Give feedback.
-
|
This makes it use the same API for reading the files as memtx uses for snapshots and vinyl uses for its on-disk files. Common API makes it possible to change the underlying storage type for all indexes at once in the future (e. g. to reading from S3 or something). Size of the index file is roughly |
Beta Was this translation helpful? Give feedback.
-
Then I think we should store the index files in the XLOG file format (with the header) and also add some versioning info for future extensibility. |
Beta Was this translation helpful? Give feedback.
-
It'd be good to do a small experiment proving the viability of the new approach:
(AFAIU using a hash table isn't really cache-friendly; I'm curious what performance impact of random accesses would be) |
Beta Was this translation helpful? Give feedback.
-
|
Modeled the algorithms in the Tarantool, and measured time it took to sort 1 000 000 000 64-bit integers (~8GB of memory). Here're the results:
Most of the time in the suggested approach with hash tables used is consumed while building the old2new tuple address association table (we do it while reading PK tuple addresses). The test (Tarantool patch).diff --git a/src/lib/core/assoc.h b/src/lib/core/assoc.h
index da0049bab4..44c4316a64 100644
--- a/src/lib/core/assoc.h
+++ b/src/lib/core/assoc.h
@@ -108,6 +108,24 @@ struct mh_i64ptr_node_t {
#define mh_cmp_key(a, b, arg) ((a) != (b->key))
#include "salad/mhash.h"
+/*
+ * Map: (i64) => (i64)
+ */
+#define mh_name _i64i64
+#define mh_key_t uint64_t
+struct mh_i64i64_node_t {
+ mh_key_t key;
+ uint64_t val;
+};
+
+#define mh_node_t struct mh_i64i64_node_t
+#define mh_arg_t void *
+#define mh_hash(a, arg) (a->key)
+#define mh_hash_key(a, arg) (a)
+#define mh_cmp(a, b, arg) ((a->key) != (b->key))
+#define mh_cmp_key(a, b, arg) ((a) != (b->key))
+#include "salad/mhash.h"
+
/*
* Map: (char * with length) => (void *)
*/
diff --git a/src/main.cc b/src/main.cc
index bba2b1e177..102854b046 100644
--- a/src/main.cc
+++ b/src/main.cc
@@ -92,6 +92,8 @@
#include "on_shutdown.h"
#include "tnt_thread.h"
+static void doit();
+
static pid_t master_pid = getpid();
static struct pidfh *pid_file_handle;
static char *script = NULL;
@@ -506,6 +508,8 @@ load_cfg(void)
title_set_custom(cfg_gets("custom_proc_title"));
title_update();
box_cfg();
+ doit();
+ exit(-1);
}
static void
@@ -1106,3 +1110,245 @@ main(int argc, char **argv)
tarantool_free();
return exit_code;
}
+
+static uint64_t *L;
+static uint64_t *R;
+
+// Merges two subarrays of arr[].
+// First subarray is arr[l..m]
+// Second subarray is arr[m+1..r]
+static void merge(uint64_t arr[], size_t l, size_t m, size_t r)
+{
+ size_t i, j, k;
+ size_t n1 = m - l + 1;
+ size_t n2 = r - m;
+
+ // Copy data to temp arrays L[] and R[]
+ for (i = 0; i < n1; i++)
+ L[i] = arr[l + i];
+ for (j = 0; j < n2; j++)
+ R[j] = arr[m + 1 + j];
+
+ // Merge the temp arrays back into arr[l..r
+ i = 0;
+ j = 0;
+ k = l;
+ while (i < n1 && j < n2) {
+ if (L[i] <= R[j]) {
+ arr[k] = L[i];
+ i++;
+ }
+ else {
+ arr[k] = R[j];
+ j++;
+ }
+ k++;
+ }
+
+ // Copy the remaining elements of L[],
+ // if there are any
+ while (i < n1) {
+ arr[k] = L[i];
+ i++;
+ k++;
+ }
+
+ // Copy the remaining elements of R[],
+ // if there are any
+ while (j < n2) {
+ arr[k] = R[j];
+ j++;
+ k++;
+ }
+}
+
+// l is for left index and r is right index of the
+// sub-array of arr to be sorted
+static void mergeSort(uint64_t *arr, int l, int r)
+{
+ if (l < r) {
+ size_t m = l + (r - l) / 2;
+
+ // Sort first and second halves
+ mergeSort(arr, l, m);
+ mergeSort(arr, m + 1, r);
+
+ merge(arr, l, m, r);
+ }
+}
+
+#include <unordered_map>
+#include <vector>
+#include <cstdio>
+#include <cassert>
+#include <cstdint>
+#include <cstring>
+#include <algorithm>
+#include "tt_sort.h"
+#include "assoc.h"
+
+/*
+ * WARNING: requires a lot of memory:
+ * ~56 GB if use = NEW
+ * ~45 GB if use = NEW_ARRAY
+ * ~75 GB if use = NEW_STDUMAP
+ */
+const size_t COUNT = 1000000000;
+
+enum {
+ STDSORT,
+ TTSORT1,
+ TTSORT2,
+ TTSORT4,
+ TTSORT8,
+ TTSORT16,
+ TTSORT32,
+ MSORT,
+ NEW,
+ NEW_ARRAY,
+ NEW_STDUMAP,
+} use = NEW_STDUMAP;
+
+static void __attribute__((noinline))
+load(uint64_t *arr, const char *fname)
+{
+ FILE *fp = fopen(fname, "rb");
+ fread(arr, sizeof(uint64_t), COUNT, fp);
+ fclose(fp);
+}
+
+static void __attribute__((noinline))
+prepare_build_data_pk(uint64_t *pk, uint64_t *npk,
+ struct mh_i64i64_t *old2new,
+ uint64_t *old2new_array,
+ std::unordered_map<uint64_t, uint64_t> &old2new_stdmap)
+{
+ for (uint64_t i = 0; i < COUNT; i++) {
+ uint64_t old_addr = pk[i];
+ uint64_t new_addr = pk[i] + 4;
+ npk[i] = new_addr;
+ if (use == NEW) {
+ struct mh_i64i64_node_t node;
+ node.key = old_addr;
+ node.val = new_addr;
+ mh_i64i64_put(old2new, &node, NULL, NULL);
+ } else if (use == NEW_ARRAY) {
+ old2new_array[old_addr] = new_addr;
+ } else if (use == NEW_STDUMAP) {
+ old2new_stdmap[old_addr] = new_addr;
+ }
+ }
+}
+
+static void __attribute__((noinline))
+prepare_build_data_sk_stdsort(uint64_t *nsk, uint64_t *npk)
+{
+ memcpy(nsk, npk, sizeof(uint64_t) * COUNT);
+ std::sort(nsk, nsk + COUNT);
+}
+
+static int
+qcompare(const void *a, const void *b, void *c)
+{
+ (void)c;
+ return *(uint64_t *)a - *(uint64_t *)b;
+}
+
+static void __attribute__((noinline))
+prepare_build_data_sk_ttsort(uint64_t *nsk, uint64_t *npk, int n_threads)
+{
+ memcpy(nsk, npk, sizeof(uint64_t) * COUNT);
+ tt_sort(nsk, COUNT, sizeof(uint64_t), qcompare, NULL, n_threads);
+}
+
+static void __attribute__((noinline))
+prepare_build_data_sk_msort(uint64_t *nsk, uint64_t *npk)
+{
+ memcpy(nsk, npk, sizeof(uint64_t) * COUNT);
+ mergeSort(nsk, 0, COUNT - 1);
+}
+
+static void __attribute__((noinline))
+prepare_build_data_sk_new(uint64_t *sk,
+ struct mh_i64i64_t *old2new,
+ uint64_t *old2new_array,
+ std::unordered_map<uint64_t, uint64_t> &old2new_stdmap,
+ uint64_t *nsk)
+{
+ for (uint64_t i = 0; i < COUNT; i++) {
+ if (use == NEW) {
+ nsk[i] = mh_i64i64_node(old2new, mh_i64i64_find(old2new, sk[i], NULL))->val;
+ } else if (use == NEW_ARRAY) {
+ nsk[i] = old2new_array[sk[i]];
+ } else if (use == NEW_STDUMAP) {
+ nsk[i] = old2new_stdmap[sk[i]];
+ } else {
+ fprintf(stderr, "%s:%d\n", __FILE__, __LINE__);
+ }
+ }
+}
+
+static void
+doit() {
+ /* Indexes as saved in .index files. */
+ uint64_t *pk = (uint64_t *)calloc(sizeof(uint64_t), COUNT);
+ uint64_t *sk = (uint64_t *)calloc(sizeof(uint64_t), COUNT);
+ /* Actual indexes with new addresses. */
+ uint64_t *npk = (uint64_t *)calloc(sizeof(uint64_t), COUNT);
+ uint64_t *nsk = (uint64_t *)calloc(sizeof(uint64_t), COUNT);
+ /* Association between .index and new addresses. */
+ struct mh_i64i64_t *old2new = mh_i64i64_new();
+ uint64_t *old2new_array = (uint64_t *)calloc(sizeof(uint64_t), COUNT);
+ std::unordered_map<uint64_t, uint64_t> old2new_stdmap;
+ /* Merge sort temporal arrays. */
+ L = (uint64_t *)calloc(sizeof(uint64_t), COUNT);
+ R = (uint64_t *)calloc(sizeof(uint64_t), COUNT);
+ /* Sanity check. */
+ assert(pk != NULL);
+ assert(sk != NULL);
+ assert(npk != NULL);
+ assert(nsk != NULL);
+ assert(old2new != NULL);
+ assert(old2new_array != NULL);
+ /* Load the .index files into memory. */
+ load(&pk[0], "i0.bin");
+ if (use == NEW)
+ load(&sk[0], "i1.bin");
+ /* Load tuples, assign them new addresses and fill old2new. */
+ prepare_build_data_pk(&pk[0], &npk[0], old2new, old2new_array, old2new_stdmap);
+ /* Sort secondary keys. */
+ switch (use) {
+ case NEW:
+ case NEW_ARRAY:
+ case NEW_STDUMAP:
+ prepare_build_data_sk_new(&sk[0], old2new, old2new_array, old2new_stdmap, &nsk[0]);
+ break;
+ case STDSORT:
+ prepare_build_data_sk_stdsort(&nsk[0], &npk[0]);
+ break;
+ case TTSORT1:
+ prepare_build_data_sk_ttsort(&nsk[0], &npk[0], 1);
+ break;
+ case TTSORT2:
+ prepare_build_data_sk_ttsort(&nsk[0], &npk[0], 2);
+ break;
+ case TTSORT4:
+ prepare_build_data_sk_ttsort(&nsk[0], &npk[0], 4);
+ break;
+ case TTSORT8:
+ prepare_build_data_sk_ttsort(&nsk[0], &npk[0], 8);
+ break;
+ case TTSORT16:
+ prepare_build_data_sk_ttsort(&nsk[0], &npk[0], 16);
+ break;
+ case TTSORT32:
+ prepare_build_data_sk_ttsort(&nsk[0], &npk[0], 32);
+ break;
+ case MSORT:
+ prepare_build_data_sk_msort(&nsk[0], &npk[0]);
+ break;
+ default:
+ fprintf(stderr, "use is invalid\n");
+ exit(-1);
+ }
+}The .index file generator.#include <random>
#include <vector>
#include <cstdio>
#include <cstdint>
#include <algorithm>
const size_t COUNT = 1000000000;
static void __attribute__((noinline))
init(uint64_t *arr)
{
fprintf(stderr, "Creating...");
fflush(stderr);
for (size_t i = 0; i < COUNT; i++)
arr[i] = i;
fprintf(stderr, " Done: %lu\nShuffling...", arr[0]);
fflush(stderr);
std::random_device r;
std::seed_seq seed{r(), r(), r(), r(), r(), r(), r(), r()};
std::mt19937 rng(seed);
std::shuffle(arr, arr + COUNT, rng);
fprintf(stderr, " Done: %lu\nWriting...", arr[0]);
fflush(stderr);
FILE *fp = fopen("a.bin", "wb");
fwrite(arr, sizeof(uint64_t), COUNT, fp);
fclose(fp);
fprintf(stderr, " Done.\n");
fflush(stderr);
}
int
main() {
static uint64_t arr[COUNT];
init(arr);
} |
Beta Was this translation helpful? Give feedback.
-
Some thoughts:
What's the ratio? |
Beta Was this translation helpful? Give feedback.
-
Let's save number of elements in header of |
Beta Was this translation helpful? Give feedback.
-
Before replace triggers don't break snapshot creation process - they break only recovery since they can modify tuples, hence, reorder tuples in secondary indexes. So we shouldn't use Also, please, mention |
Beta Was this translation helpful? Give feedback.
-
|
Could you please provide more information about how and when you will use these To be more specific, let's say you have two spaces:
By the way, does building secondary indexes only after WAL recovery really provides any sensible performance gains? It would be simpler to always build secondary indexes after snapshot recovery. |
Beta Was this translation helpful? Give feedback.
-
I would elaborate a bit. The idea is to have a "fake" space (let's call it Such space shouldn't actually store anything in-memory, only process the tuples in a system So, basically, the flow is:
|
Beta Was this translation helpful? Give feedback.
-
As I understood there are variants that are possible to implement without any options. For this we need to ensure that the secondary keys order data don't break old tarantool versions anyhow (including waste of memory). I think that we can consider the following variants:
In my opinion, backhole engine/NOP operations are tricks, while holding the extra data in separate files looks like a direct solution. So, it seems better for me. OTOH, we should verify how snapshotting time is changed in case of several secondary indexes. If it becomes much longer, maybe the option to refuse to write it is useful (but I'm not sure). It is also important to take into account that modern SSD is able to serve several parallel write requests with the speed near to the single write. I think that parallel write of several files may be very profitable here.
Technically speaking, shouldn't we check presence of such triggers while reading the data, not writing? I guess that if we have the trigger on writing a snapshot, we likely have it after restart too, but there is no such a guarantee. |
Beta Was this translation helpful? Give feedback.
-
|
Will this feature work for functional and multikey indexes? Please add this information to the RFC. |
Beta Was this translation helpful? Give feedback.
-
Reviewers
The problem
The issue is descibed in #10847: since we save tuples in snapshot in PK order, we have to sort them to build each secondary key (and the sorting process has
n*log(n)complexity). Let's save the order of secondary keys in the snapshot to reduce the build complexity toO(n)(this, in theory, should speed-up recovery of secondary keys).The algrithm
As the issue suggests, let's write the order of secondary indexes to the snapshot. The algorithm is:
[0xa3, 0xb2, 0xc1]. Then we know that the first tuple in primary index had address0x01and its new address is0xa3, the second one had0x02and the new address is0xb2and so on. So we can easily build the mapping:[0xffff00001111, 0xffff00003333, 0xffff00002222]and now it becomes[0xffff0000aaaa, 0xffff0000cccc, 0xffff0000bbbb]- array of actual tuples in required order.The storage
One could think to insert the information described in the
.snapfile itself, but there's few options to that:Another option is to store the information in separated file[s]. It's already done in Vinyl, so the proposal is to store the snapshot files similar way in
memtx_dir. So, for each seconady key of a space the following structure is to be created:<space_id>/<index_id>/<recovery_data_file>.Option 0: separated files
This one is simple: just store a number of
MP_STRINGentries specifying the index order data (a binary sequence of 8-byte pointers wrappind into a string header) in<memtx_dir>/<space_id>/<index_id>/<vclock_signature>.indexfiles (user may be afraid to delete an.indexfile, whereas he shouldn't, so better naming suggestions are appreciated). These files are created along with the regular snapshot file inmemtx_engine_begin_checkpoint, but only for TREE index and if the space has nobefore_replacetriggers.The entries to store are
MP_STRINGinstead of arrays ofMP_UINTin order to minimize the data validation time.The optimal amount of tuple data to store in a single
MP_STRINGsorting data batch is to be investigated.The data is started to load on the initial recovery start if no
force_recoveryspecified and used on the secondary indexes build step and we continue to read next chunks after eachdata_batch_sizereplaces.Option 1: a system space
The idea is to save the information in a system space: create the space on startup and remove it after recovery.
box.snapshot()after the downgrade (for backward compatibility).Haven't investigated this one thoroughly, so no technical details for now.
The configuration
A new configuration variable is proposed:
memtx_use_sk_recovery_data. If the variable is disabled, we sort the secondary key tuples as before and don't write recovery data on snapshot.Changelog
2. The data is stored and loaded with batches of a size yet to be specified.
Beta Was this translation helpful? Give feedback.
All reactions