From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: From: Kirill Shcherbatov Subject: [PATCH v5 11/12] box: introduce offset slot cache in key_part Date: Mon, 29 Oct 2018 09:56:32 +0300 Message-Id: In-Reply-To: References: In-Reply-To: References: To: tarantool-patches@freelists.org Cc: vdavydov.dev@gmail.com, Kirill Shcherbatov List-ID: Same key_part could be used in different formats multiple times, so different field->offset_slot would be allocated. In most scenarios we work with series of tuples of same format, and (in general) format lookup for field would be expensive operation for JSON-paths defined in key_part. New offset_slot_cache field in key_part structure and epoch-based mechanism to validate it's actuality should be effective approach to improve performance. Part of #1012 --- src/box/alter.cc | 7 +++-- src/box/blackhole.c | 5 ++-- src/box/engine.h | 11 ++++---- src/box/key_def.c | 12 ++++++-- 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, 108 insertions(+), 61 deletions(-) diff --git a/src/box/alter.cc b/src/box/alter.cc index fc4d44e..261b4b2 100644 --- a/src/box/alter.cc +++ b/src/box/alter.cc @@ -869,7 +869,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 @@ -1680,7 +1683,7 @@ on_replace_dd_space(struct trigger * /* trigger */, void *event) access_check_ddl(def->name, def->id, def->uid, SC_SPACE, PRIV_C, true); 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 88dab3f..efd70f9 100644 --- a/src/box/blackhole.c +++ b/src/box/blackhole.c @@ -138,7 +138,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"); @@ -155,7 +155,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 0043f4e..17071fd 100644 --- a/src/box/key_def.c +++ b/src/box/key_def.c @@ -189,6 +189,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 = TUPLE_OFFSET_SLOT_NIL; + def->parts[part_no].format_cache = NULL; if (path != NULL) { def->parts[part_no].path_len = path_len; assert(def->parts[part_no].path != NULL); @@ -722,10 +724,13 @@ key_def_merge(const struct key_def *first, const struct key_def *second) new_def->parts[pos].path = data; data += part->path_len + 1; } - key_def_set_part(new_def, pos++, part->fieldno, part->type, + 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); + new_def->parts[pos].offset_slot_cache = part->offset_slot_cache; + new_def->parts[pos].format_cache = part->format_cache; + pos++; } /* Set-append second key def's part to the new key def. */ @@ -738,10 +743,13 @@ key_def_merge(const struct key_def *first, const struct key_def *second) new_def->parts[pos].path = data; data += part->path_len + 1; } - key_def_set_part(new_def, pos++, part->fieldno, part->type, + 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); + new_def->parts[pos].offset_slot_cache = part->offset_slot_cache; + new_def->parts[pos].format_cache = part->format_cache; + pos++; } key_def_set_cmp(new_def); return new_def; diff --git a/src/box/key_def.h b/src/box/key_def.h index 5c0dfe3..8699487 100644 --- a/src/box/key_def.h +++ b/src/box/key_def.h @@ -101,6 +101,14 @@ struct key_part { char *path; /** The length of JSON path. */ uint32_t path_len; + /** + * Source format for offset_slot_cache actuality + * 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 c572751..fc9f019 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 1a248b7..d57dad3 100644 --- a/src/box/memtx_space.c +++ b/src/box/memtx_space.c @@ -955,7 +955,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) { @@ -981,7 +981,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 7dc3410..b5bec0c 100644 --- a/src/box/memtx_space.h +++ b/src/box/memtx_space.h @@ -79,7 +79,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 548f667..99badf6 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 f3e9e1e..ad2bc64 100644 --- a/src/box/space.h +++ b/src/box/space.h @@ -417,10 +417,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. @@ -471,9 +472,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 ed5bca3..f18d9cd 100644 --- a/src/box/sysview.c +++ b/src/box/sysview.c @@ -507,8 +507,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 920968c..3c939cb 100644 --- a/src/box/tuple_format.c +++ b/src/box/tuple_format.c @@ -451,7 +451,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); @@ -460,6 +461,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); @@ -999,29 +1001,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 e82af67..adb4a7b 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. */ @@ -250,6 +252,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. @@ -257,7 +260,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 eb40ef1..e4793d9 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; @@ -3016,7 +3017,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