From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: From: Kirill Shcherbatov Subject: [PATCH v5 8/9] box: introduce offset slot cache in key_part Date: Mon, 26 Nov 2018 13:49:42 +0300 Message-Id: In-Reply-To: References: In-Reply-To: References: To: tarantool-patches@freelists.org, vdavydov.dev@gmail.com Cc: kostja@tarantool.org, Kirill Shcherbatov List-ID: Tuned tuple_field_by_part_raw routine with key_part's offset_slot_cache. Introduced tuple_format epoch to test validity of this cache. The key_part caches last offset_slot source format to make epoch comparison because same space may have multiple format of same epoch that have different key_parts and related offset_slots distribution. Part of #1012 --- src/box/alter.cc | 7 +++-- src/box/blackhole.c | 5 ++-- src/box/engine.h | 11 ++++---- src/box/key_def.c | 17 +++++++---- src/box/key_def.h | 8 ++++++ src/box/memtx_engine.c | 4 +-- src/box/memtx_space.c | 5 ++-- src/box/memtx_space.h | 2 +- src/box/schema.cc | 4 +-- src/box/space.c | 6 ++-- src/box/space.h | 8 ++++-- src/box/sysview.c | 3 +- src/box/tuple.c | 4 +-- src/box/tuple_format.c | 62 ++++++++++++++++++++++++++--------------- src/box/tuple_format.h | 6 +++- src/box/vinyl.c | 7 +++-- src/box/vy_lsm.c | 5 ++-- test/unit/vy_iterators_helper.c | 6 ++-- test/unit/vy_mem.c | 2 +- test/unit/vy_point_lookup.c | 2 +- 20 files changed, 110 insertions(+), 64 deletions(-) diff --git a/src/box/alter.cc b/src/box/alter.cc index 029da02..6291159 100644 --- a/src/box/alter.cc +++ b/src/box/alter.cc @@ -856,7 +856,10 @@ alter_space_do(struct txn *txn, struct alter_space *alter) * Create a new (empty) space for the new definition. * Sic: the triggers are not moved over yet. */ - alter->new_space = space_new_xc(alter->space_def, &alter->key_list); + alter->new_space = + space_new_xc(alter->space_def, &alter->key_list, + alter->old_space->format != NULL ? + alter->old_space->format->epoch + 1 : 1); /* * Copy the replace function, the new space is at the same recovery * phase as the old one. This hack is especially necessary for @@ -1667,7 +1670,7 @@ on_replace_dd_space(struct trigger * /* trigger */, void *event) access_check_ddl(def->name, def->id, def->uid, SC_SPACE, PRIV_C); RLIST_HEAD(empty_list); - struct space *space = space_new_xc(def, &empty_list); + struct space *space = space_new_xc(def, &empty_list, 0); /** * The new space must be inserted in the space * cache right away to achieve linearisable diff --git a/src/box/blackhole.c b/src/box/blackhole.c index 0412ffe..2727d12 100644 --- a/src/box/blackhole.c +++ b/src/box/blackhole.c @@ -139,7 +139,7 @@ blackhole_engine_shutdown(struct engine *engine) static struct space * blackhole_engine_create_space(struct engine *engine, struct space_def *def, - struct rlist *key_list) + struct rlist *key_list, uint64_t epoch) { if (!rlist_empty(key_list)) { diag_set(ClientError, ER_UNSUPPORTED, "Blackhole", "indexes"); @@ -156,7 +156,8 @@ blackhole_engine_create_space(struct engine *engine, struct space_def *def, /* Allocate tuples on runtime arena, but check space format. */ struct tuple_format *format; format = tuple_format_new(&tuple_format_runtime->vtab, NULL, 0, - def->fields, def->field_count, def->dict); + def->fields, def->field_count, def->dict, + epoch); if (format == NULL) { free(space); return NULL; diff --git a/src/box/engine.h b/src/box/engine.h index 5b96c74..0e8c76c 100644 --- a/src/box/engine.h +++ b/src/box/engine.h @@ -72,7 +72,8 @@ struct engine_vtab { void (*shutdown)(struct engine *); /** Allocate a new space instance. */ struct space *(*create_space)(struct engine *engine, - struct space_def *def, struct rlist *key_list); + struct space_def *def, struct rlist *key_list, + uint64_t epoch); /** * Write statements stored in checkpoint @vclock to @stream. */ @@ -237,9 +238,9 @@ engine_find(const char *name) static inline struct space * engine_create_space(struct engine *engine, struct space_def *def, - struct rlist *key_list) + struct rlist *key_list, uint64_t epoch) { - return engine->vtab->create_space(engine, def, key_list); + return engine->vtab->create_space(engine, def, key_list, epoch); } static inline int @@ -390,9 +391,9 @@ engine_find_xc(const char *name) static inline struct space * engine_create_space_xc(struct engine *engine, struct space_def *def, - struct rlist *key_list) + struct rlist *key_list, uint64_t epoch) { - struct space *space = engine_create_space(engine, def, key_list); + struct space *space = engine_create_space(engine, def, key_list, epoch); if (space == NULL) diag_raise(); return space; diff --git a/src/box/key_def.c b/src/box/key_def.c index bc6cecd..2953bfa 100644 --- a/src/box/key_def.c +++ b/src/box/key_def.c @@ -177,7 +177,8 @@ key_def_set_part(struct key_def *def, uint32_t part_no, uint32_t fieldno, enum field_type type, enum on_conflict_action nullable_action, struct coll *coll, uint32_t coll_id, enum sort_order sort_order, const char *path, - uint32_t path_len) + uint32_t path_len, int32_t offset_slot_cache, + struct tuple_format *format_cache) { assert(part_no < def->part_count); assert(type < field_type_MAX); @@ -189,6 +190,8 @@ key_def_set_part(struct key_def *def, uint32_t part_no, uint32_t fieldno, def->parts[part_no].coll = coll; def->parts[part_no].coll_id = coll_id; def->parts[part_no].sort_order = sort_order; + def->parts[part_no].offset_slot_cache = offset_slot_cache; + def->parts[part_no].format_cache = format_cache; if (path != NULL) { def->parts[part_no].path_len = path_len; assert(def->parts[part_no].path != NULL); @@ -239,7 +242,8 @@ key_def_new(const struct key_part_def *parts, uint32_t part_count) } key_def_set_part(def, i, part->fieldno, part->type, part->nullable_action, coll, part->coll_id, - part->sort_order, part->path, path_len); + part->sort_order, part->path, path_len, + TUPLE_OFFSET_SLOT_NIL, NULL); } key_def_set_cmp(def); return def; @@ -291,7 +295,8 @@ box_key_def_new(uint32_t *fields, uint32_t *types, uint32_t part_count) key_def_set_part(key_def, item, fields[item], (enum field_type)types[item], ON_CONFLICT_ACTION_DEFAULT, - NULL, COLL_NONE, SORT_ORDER_ASC, NULL, 0); + NULL, COLL_NONE, SORT_ORDER_ASC, NULL, 0, + TUPLE_OFFSET_SLOT_NIL, NULL); } key_def_set_cmp(key_def); return key_def; @@ -699,7 +704,8 @@ key_def_merge(const struct key_def *first, const struct key_def *second) key_def_set_part(new_def, pos++, part->fieldno, part->type, part->nullable_action, part->coll, part->coll_id, part->sort_order, part->path, - part->path_len); + part->path_len, part->offset_slot_cache, + part->format_cache); } /* Set-append second key def's part to the new key def. */ @@ -715,7 +721,8 @@ key_def_merge(const struct key_def *first, const struct key_def *second) key_def_set_part(new_def, pos++, part->fieldno, part->type, part->nullable_action, part->coll, part->coll_id, part->sort_order, part->path, - part->path_len); + part->path_len, part->offset_slot_cache, + part->format_cache); } key_def_set_cmp(new_def); return new_def; diff --git a/src/box/key_def.h b/src/box/key_def.h index 7731e48..3e08eb4 100644 --- a/src/box/key_def.h +++ b/src/box/key_def.h @@ -95,6 +95,14 @@ struct key_part { char *path; /** The length of JSON path. */ uint32_t path_len; + /** + * Source format for offset_slot_cache hit validations. + * Cache is expected to use "the format with the newest + * epoch is most relevant" strategy. + */ + struct tuple_format *format_cache; + /** Cache with format's field offset slot. */ + int32_t offset_slot_cache; }; struct key_def; diff --git a/src/box/memtx_engine.c b/src/box/memtx_engine.c index 1bc46c6..caafef0 100644 --- a/src/box/memtx_engine.c +++ b/src/box/memtx_engine.c @@ -358,10 +358,10 @@ memtx_engine_end_recovery(struct engine *engine) static struct space * memtx_engine_create_space(struct engine *engine, struct space_def *def, - struct rlist *key_list) + struct rlist *key_list, uint64_t epoch) { struct memtx_engine *memtx = (struct memtx_engine *)engine; - return memtx_space_new(memtx, def, key_list); + return memtx_space_new(memtx, def, key_list, epoch); } static int diff --git a/src/box/memtx_space.c b/src/box/memtx_space.c index eb790a6..38c9de0 100644 --- a/src/box/memtx_space.c +++ b/src/box/memtx_space.c @@ -965,7 +965,7 @@ static const struct space_vtab memtx_space_vtab = { struct space * memtx_space_new(struct memtx_engine *memtx, - struct space_def *def, struct rlist *key_list) + struct space_def *def, struct rlist *key_list, uint64_t epoch) { struct memtx_space *memtx_space = malloc(sizeof(*memtx_space)); if (memtx_space == NULL) { @@ -991,7 +991,8 @@ memtx_space_new(struct memtx_engine *memtx, struct tuple_format *format = tuple_format_new(&memtx_tuple_format_vtab, keys, key_count, - def->fields, def->field_count, def->dict); + def->fields, def->field_count, def->dict, + epoch); if (format == NULL) { free(memtx_space); return NULL; diff --git a/src/box/memtx_space.h b/src/box/memtx_space.h index 5325383..bad6917 100644 --- a/src/box/memtx_space.h +++ b/src/box/memtx_space.h @@ -86,7 +86,7 @@ memtx_space_replace_all_keys(struct space *, struct tuple *, struct tuple *, struct space * memtx_space_new(struct memtx_engine *memtx, - struct space_def *def, struct rlist *key_list); + struct space_def *def, struct rlist *key_list, uint64_t epoch); #if defined(__cplusplus) } /* extern "C" */ diff --git a/src/box/schema.cc b/src/box/schema.cc index 8625d92..865e07e 100644 --- a/src/box/schema.cc +++ b/src/box/schema.cc @@ -283,7 +283,7 @@ sc_space_new(uint32_t id, const char *name, struct rlist key_list; rlist_create(&key_list); rlist_add_entry(&key_list, index_def, link); - struct space *space = space_new_xc(def, &key_list); + struct space *space = space_new_xc(def, &key_list, 0); space_cache_replace(NULL, space); if (replace_trigger) trigger_add(&space->on_replace, replace_trigger); @@ -495,7 +495,7 @@ schema_init() space_def_delete(def); }); RLIST_HEAD(key_list); - struct space *space = space_new_xc(def, &key_list); + struct space *space = space_new_xc(def, &key_list, 0); space_cache_replace(NULL, space); init_system_space(space); trigger_run_xc(&on_alter_space, space); diff --git a/src/box/space.c b/src/box/space.c index 4d174f7..0a23cf8 100644 --- a/src/box/space.c +++ b/src/box/space.c @@ -183,18 +183,18 @@ fail: } struct space * -space_new(struct space_def *def, struct rlist *key_list) +space_new(struct space_def *def, struct rlist *key_list, uint64_t epoch) { struct engine *engine = engine_find(def->engine_name); if (engine == NULL) return NULL; - return engine_create_space(engine, def, key_list); + return engine_create_space(engine, def, key_list, epoch); } struct space * space_new_ephemeral(struct space_def *def, struct rlist *key_list) { - struct space *space = space_new(def, key_list); + struct space *space = space_new(def, key_list, 0); if (space == NULL) return NULL; space->def->opts.is_temporary = true; diff --git a/src/box/space.h b/src/box/space.h index 7eb7ae2..99eff48 100644 --- a/src/box/space.h +++ b/src/box/space.h @@ -419,10 +419,11 @@ struct field_def; * Allocate and initialize a space. * @param space_def Space definition. * @param key_list List of index_defs. + * @param epoch Last epoch to initialize format. * @retval Space object. */ struct space * -space_new(struct space_def *space_def, struct rlist *key_list); +space_new(struct space_def *space_def, struct rlist *key_list, uint64_t epoch); /** * Create an ephemeral space. @@ -474,9 +475,10 @@ int generic_space_prepare_alter(struct space *, struct space *); } /* extern "C" */ static inline struct space * -space_new_xc(struct space_def *space_def, struct rlist *key_list) +space_new_xc(struct space_def *space_def, struct rlist *key_list, + uint64_t epoch) { - struct space *space = space_new(space_def, key_list); + struct space *space = space_new(space_def, key_list, epoch); if (space == NULL) diag_raise(); return space; diff --git a/src/box/sysview.c b/src/box/sysview.c index 29de430..64106c0 100644 --- a/src/box/sysview.c +++ b/src/box/sysview.c @@ -508,8 +508,9 @@ sysview_engine_shutdown(struct engine *engine) static struct space * sysview_engine_create_space(struct engine *engine, struct space_def *def, - struct rlist *key_list) + struct rlist *key_list, uint64_t epoch) { + (void)epoch; struct space *space = (struct space *)calloc(1, sizeof(*space)); if (space == NULL) { diag_set(OutOfMemory, sizeof(*space), diff --git a/src/box/tuple.c b/src/box/tuple.c index 62e06e7..d8cf517 100644 --- a/src/box/tuple.c +++ b/src/box/tuple.c @@ -205,7 +205,7 @@ tuple_init(field_name_hash_f hash) * Create a format for runtime tuples */ tuple_format_runtime = tuple_format_new(&tuple_format_runtime_vtab, - NULL, 0, NULL, 0, NULL); + NULL, 0, NULL, 0, NULL, 0); if (tuple_format_runtime == NULL) return -1; @@ -377,7 +377,7 @@ box_tuple_format_new(struct key_def **keys, uint16_t key_count) { box_tuple_format_t *format = tuple_format_new(&tuple_format_runtime_vtab, - keys, key_count, NULL, 0, NULL); + keys, key_count, NULL, 0, NULL, 0); if (format != NULL) tuple_format_ref(format); return format; diff --git a/src/box/tuple_format.c b/src/box/tuple_format.c index be89764..5d90632 100644 --- a/src/box/tuple_format.c +++ b/src/box/tuple_format.c @@ -461,7 +461,8 @@ tuple_format_delete(struct tuple_format *format) struct tuple_format * tuple_format_new(struct tuple_format_vtab *vtab, struct key_def * const *keys, uint16_t key_count, const struct field_def *space_fields, - uint32_t space_field_count, struct tuple_dictionary *dict) + uint32_t space_field_count, struct tuple_dictionary *dict, + uint64_t epoch) { struct tuple_format *format = tuple_format_alloc(keys, key_count, space_field_count, dict); @@ -470,6 +471,7 @@ tuple_format_new(struct tuple_format_vtab *vtab, struct key_def * const *keys, format->vtab = *vtab; format->engine = NULL; format->is_temporary = false; + format->epoch = epoch; if (tuple_format_register(format) < 0) { tuple_format_destroy(format); free(format); @@ -1029,29 +1031,43 @@ tuple_field_by_part_raw(struct tuple_format *format, const char *data, if (likely(part->path == NULL)) return tuple_field_raw(format, data, field_map, part->fieldno); - uint32_t field_count = tuple_format_field_count(format); - struct tuple_field *root_field = - likely(part->fieldno < field_count) ? - tuple_format_field(format, part->fieldno) : NULL; - struct tuple_field *field = - unlikely(root_field == NULL) ? NULL: - tuple_format_field_by_path(format, root_field, part->path, - part->path_len); - if (unlikely(field == NULL)) { - /* - * Legacy tuple having no field map for JSON - * index require full path parse. - */ - const char *field_raw = - tuple_field_raw(format, data, field_map, part->fieldno); - if (unlikely(field_raw == NULL)) - return NULL; - if (tuple_field_go_to_path(&field_raw, part->path, - part->path_len) != 0) - return NULL; - return field_raw; + int32_t offset_slot; + if (likely(part->format_cache == format)) { + assert(format->epoch != 0); + offset_slot = part->offset_slot_cache; + } else { + uint32_t field_count = tuple_format_field_count(format); + struct tuple_field *root_field = + likely(part->fieldno < field_count) ? + tuple_format_field(format, part->fieldno) : NULL; + struct tuple_field *field = + unlikely(root_field == NULL) ? NULL: + tuple_format_field_by_path(format, root_field, part->path, + part->path_len); + if (unlikely(field == NULL)) { + /* + * Legacy tuple having no field map for JSON + * index require full path parse. + */ + const char *field_raw = + tuple_field_raw(format, data, field_map, part->fieldno); + if (unlikely(field_raw == NULL)) + return NULL; + if (tuple_field_go_to_path(&field_raw, part->path, + part->path_len) != 0) + return NULL; + return field_raw; + } + offset_slot = field->offset_slot; + /* Cache offset_slot if required. */ + if (part->format_cache != format && + (part->format_cache == NULL || + part->format_cache->epoch < format->epoch)) { + assert(format->epoch != 0); + part->offset_slot_cache = offset_slot; + part->format_cache = format; + } } - int32_t offset_slot = field->offset_slot; assert(offset_slot < 0); assert(-offset_slot * sizeof(uint32_t) <= format->field_map_size); if (unlikely(field_map[offset_slot] == 0)) diff --git a/src/box/tuple_format.h b/src/box/tuple_format.h index 860f052..8a7ebfa 100644 --- a/src/box/tuple_format.h +++ b/src/box/tuple_format.h @@ -137,6 +137,8 @@ tuple_field_is_nullable(const struct tuple_field *tuple_field) * Tuple format describes how tuple is stored and information about its fields */ struct tuple_format { + /** Counter that grows incrementally on space rebuild. */ + uint64_t epoch; /** Virtual function table */ struct tuple_format_vtab vtab; /** Pointer to engine-specific data. */ @@ -254,6 +256,7 @@ tuple_format_unref(struct tuple_format *format) * @param key_count The number of keys in @a keys array. * @param space_fields Array of fields, defined in a space format. * @param space_field_count Length of @a space_fields. + * @param epoch Epoch of new format. * * @retval not NULL Tuple format. * @retval NULL Memory error. @@ -261,7 +264,8 @@ tuple_format_unref(struct tuple_format *format) struct tuple_format * tuple_format_new(struct tuple_format_vtab *vtab, struct key_def * const *keys, uint16_t key_count, const struct field_def *space_fields, - uint32_t space_field_count, struct tuple_dictionary *dict); + uint32_t space_field_count, struct tuple_dictionary *dict, + uint64_t epoch); /** * Check, if @a format1 can store any tuples of @a format2. For diff --git a/src/box/vinyl.c b/src/box/vinyl.c index 3c9fbf8..ebb1301 100644 --- a/src/box/vinyl.c +++ b/src/box/vinyl.c @@ -584,7 +584,7 @@ vinyl_engine_check_space_def(struct space_def *def) static struct space * vinyl_engine_create_space(struct engine *engine, struct space_def *def, - struct rlist *key_list) + struct rlist *key_list, uint64_t epoch) { struct space *space = malloc(sizeof(*space)); if (space == NULL) { @@ -610,7 +610,8 @@ vinyl_engine_create_space(struct engine *engine, struct space_def *def, struct tuple_format *format = tuple_format_new(&vy_tuple_format_vtab, keys, key_count, - def->fields, def->field_count, def->dict); + def->fields, def->field_count, def->dict, + epoch); if (format == NULL) { free(space); return NULL; @@ -3017,7 +3018,7 @@ vy_send_lsm(struct vy_join_ctx *ctx, struct vy_lsm_recovery_info *lsm_info) if (ctx->key_def == NULL) goto out; ctx->format = tuple_format_new(&vy_tuple_format_vtab, &ctx->key_def, - 1, NULL, 0, NULL); + 1, NULL, 0, NULL, 0); if (ctx->format == NULL) goto out_free_key_def; tuple_format_ref(ctx->format); diff --git a/src/box/vy_lsm.c b/src/box/vy_lsm.c index 681b165..e57f864 100644 --- a/src/box/vy_lsm.c +++ b/src/box/vy_lsm.c @@ -61,7 +61,7 @@ vy_lsm_env_create(struct vy_lsm_env *env, const char *path, void *upsert_thresh_arg) { env->key_format = tuple_format_new(&vy_tuple_format_vtab, - NULL, 0, NULL, 0, NULL); + NULL, 0, NULL, 0, NULL, 0); if (env->key_format == NULL) return -1; tuple_format_ref(env->key_format); @@ -154,7 +154,8 @@ vy_lsm_new(struct vy_lsm_env *lsm_env, struct vy_cache_env *cache_env, lsm->disk_format = format; } else { lsm->disk_format = tuple_format_new(&vy_tuple_format_vtab, - &cmp_def, 1, NULL, 0, NULL); + &cmp_def, 1, NULL, 0, NULL, + format->epoch); if (lsm->disk_format == NULL) goto fail_format; } diff --git a/test/unit/vy_iterators_helper.c b/test/unit/vy_iterators_helper.c index 7fad560..bbb3149 100644 --- a/test/unit/vy_iterators_helper.c +++ b/test/unit/vy_iterators_helper.c @@ -22,7 +22,7 @@ vy_iterator_C_test_init(size_t cache_size) vy_cache_env_create(&cache_env, cord_slab_cache()); vy_cache_env_set_quota(&cache_env, cache_size); vy_key_format = tuple_format_new(&vy_tuple_format_vtab, NULL, 0, - NULL, 0, NULL); + NULL, 0, NULL, 0); tuple_format_ref(vy_key_format); size_t mem_size = 64 * 1024 * 1024; @@ -202,7 +202,7 @@ create_test_mem(struct key_def *def) struct key_def * const defs[] = { def }; struct tuple_format *format = tuple_format_new(&vy_tuple_format_vtab, defs, def->part_count, - NULL, 0, NULL); + NULL, 0, NULL, 0); fail_if(format == NULL); /* Create mem */ @@ -220,7 +220,7 @@ create_test_cache(uint32_t *fields, uint32_t *types, assert(*def != NULL); vy_cache_create(cache, &cache_env, *def, true); *format = tuple_format_new(&vy_tuple_format_vtab, def, 1, NULL, 0, - NULL); + NULL, 0); tuple_format_ref(*format); } diff --git a/test/unit/vy_mem.c b/test/unit/vy_mem.c index ebf3fbc..325c7cc 100644 --- a/test/unit/vy_mem.c +++ b/test/unit/vy_mem.c @@ -78,7 +78,7 @@ test_iterator_restore_after_insertion() /* Create format */ struct tuple_format *format = tuple_format_new(&vy_tuple_format_vtab, &key_def, 1, NULL, 0, - NULL); + NULL, 0); assert(format != NULL); tuple_format_ref(format); diff --git a/test/unit/vy_point_lookup.c b/test/unit/vy_point_lookup.c index 65dafcb..d8e3a9e 100644 --- a/test/unit/vy_point_lookup.c +++ b/test/unit/vy_point_lookup.c @@ -85,7 +85,7 @@ test_basic() vy_cache_create(&cache, &cache_env, key_def, true); struct tuple_format *format = tuple_format_new(&vy_tuple_format_vtab, &key_def, 1, NULL, 0, - NULL); + NULL, 0); isnt(format, NULL, "tuple_format_new is not NULL"); tuple_format_ref(format); -- 2.7.4