Memtx MVCC: support of multikey index variants

[CuriousGeorgiy]

Table of Contents

• Problem
• Goal
• Problem breakdown
  • Index replace
  • Tracking read/write sets
  • Looking up tracked states
  • Functional key management
• Solution
  • memtx_story_link_key
  • memtx_index_key
  • story_link_key_storage

Problem at large

Currently, we do not support multikey index variants in memtx MVCC. There are two reasons for this.

Firstly, we rely on the index replace interface to collect the read and write set of a transaction statement through the result (replaced) and successor return values. However, multikey index variants internally process multiple tuples at a time, yielding multiple result and successor values which cannot be returned through the existing interface. Furthermore, (scope of #12285).

Secondly, we rely on the fact that there is a 1:1 mapping between stories (versions) and tuples they correspond to. Based on this assumption, there is a single story chain for each tuple in the index. However, multikey index variants break this assumption, since a story starts to be associated with an array of keys rather than one key. This means that we need a new abstraction to manage the relationship between a story and its keys in the index (scope of this RFC).

Goal

Ultimately, we want to support multikey index variants in memtx MVCC. This suggests two goals.

Most importantly, we need to avoid changing any abstractions outside of memtx MVCC. We must keep all the required logic contained in memtx MVCC.

We need to abstract away the differences between different index variants (regular, multikey, functional).

Ideally, we need to design an abstraction that would keep all the existing memtx MVCC logic, and would simply generalize it to multiple keys per story.

Problem breakdown

To support multikey index variants, we need to solve several subproblems identified below.

Index replace

Currently, an index replace operates on tuples rather than multikey keys. This implies that a multikey index replace internally processes all the multikey keys of the tuple. However, since in the context of memtx MVCC each multikey key can form a separate history chain, the presence of each multikey key in the index needs to managed separately. Therefore, the replace interface needs to be generalized to operate on a multikey key rather than on a tuple (scope of #12285).

Tracking read/write sets

For regular indexes it was enough to use the tuple to uniquely identify a key in the index and to have a single history chain. However, in the case of multikey indexes, multiple keys can map to the same tuple. This also means that each story has to participate in multiple history chains for each of its associated keys. Therefore, the existing memtx_story needs to be generalized for the case of multiple keys to be able to track the state of each multikey index key. Furthermore, the existing tuple-based read/write set operations need to be generalized to work on a multikey key rather than a tuple.

Looking up tracked states

For regular multikey indexes, we could use a memtx_story-local array of tracking states to index into using the multikey key. However, for functional multikey indexes, we need to use a generic search structure. Creating such a search structure per each memtx_story seems infeasible. Therefore, the mh_history_t registry needs to be generalized for the case of multiple keys to be able to look up multikey index key tracking states.

Functional key management

For unikey functional indexes it was enough to use the tuple to uniquely identify a functional key in the index. However, in the case of multikey indexes, multiple functional keys can map to the same tuple. Therefore the functional key management needs to be generalized for multikey functional indexes.

Solution

The solution will be based on the new abstractions described below. These abstractions will allow to generalize a story, a tuple and state lookup in the case of multikey index variants.

memtx_story_link_key

We will introduce a new abstraction that generalizes a story in the case of multikey index variants, memtx_story_link_key:

/**
 * Link that connects a memtx_story with older and newer stories of the same
 * key in index.
 */
struct memtx_story_link_key {
	/** Backlink to the story this key is associated with. */
	struct memtx_story *story;
	/**
	 * Encoding of the key for multikey indexes. For regular multikey
	 * indexes it represents the index in the multikey array. For functional
	 * multikey indexes it represents the pointer to the functional key. For regular
	 * indexes, it is set to `MULTIKEY_NONE`.
	 */
	hint_t hint;
	 /**
	 * For a statement in transaction `TXN`, `is_own_change == true`
	 * in story `A` for index `I` means:
	 * - The tuple `A` replaced a tuple `B` that was added by
	 *   this same transaction, and `A->tuple[I] == B->tuple[I]`;
	 * - OR the key `A->tuple[I]` was not present in index `I` because this
	 *   transaction `TXN` had previously executed a statement that removed/
	 *   replaced a tuple `B`, such that `A->tuple[I] == B->tuple[I]` and
	 *   this is guaranteed to always remain true (due to the presence of a
	 *   read tracker or some other conditions).
	 */
	bool is_own_change;
	/** Newer key on this key's history chain. */
	struct memtx_story_link *newer_key;
	/** Older key on this key's history chain. */
	struct memtx_story_link *older_key;
	/** List of gap items @sa gap_item. */
	struct rlist nearby_gaps;
	/**
	 * If the tuple of story is physically in index, here the pointer
	 * to that index is stored.
	 */
	struct index *in_index;
};

Each memtx_story_link will have a list of keys:

/**
 * Link that connects a story with older and newer stories of the same
 * key list in index.
 */
struct memtx_story_link {
	/** List of `memtx_link_keys` associated with this story. */
	struct rlist keys;
};

Each memtx_story_link_key will form a separate history chain based on its key, i.e., each story will be part of multiple distinct history chains formed by its keys.

The lifetime of a story will become the lifetime of all its keys, i.e., a story will be retained as long as any of its keys is referenced by MVCC.

All read/write set logic will use memtx_link_keys instead of memtx_links.

This will solve Tracking read/write sets, as it will allow to track the state of each multikey key.

memtx_index_key

In the scope of #12285, we will introduce new abstractions that generalize a tuple and replace in the case of multikey index variants: memtx_index_key and memtx_index_replace_key.

Each tuple in memtx MVCC logic will be replaced by a memtx_index_key and all story-wise logic will be multiplexed for memtx_story_link::key_count iterations over each memtx_story_link_key. Particularly, each chain-wise memtx_index_replace in memtx MVCC will be replaced with memtx_index_replace_key.

For instance, this piece of code handling secondary index duplicate conflicts:
https://github.com/tarantool/tarantool/blame/5fe44d8445f209330b874d2eb11a76086da1a804/src/box/memtx_tx.c#L3085-L3098

Will look like this:

for (uint32_t i = 1; i < story->index_count; i++) {
	for (uint32_t key_idx = 0; key_idx < story->link[iid].key_count; ++key_idx) {
		struct memtx_link_key *key = &story->link->keys[key_idx];
		struct memtx_story *top_story =
			memtx_tx_handle_dups_in_secondary_index(key);
		/*
		 * We have already checked gap readers before for the case
		 * of insertion to the primary index.
		 * In any (replace or insert) case we must handle gap readers
		 * in the secondary indexes as well since in all kinds of
		 * statements can insert new value to secondary index.
		 * Note that newer_story is in top of chain due to previous
		 * manipulations.
		 */
		memtx_tx_handle_conflict_gap_readers(key, stmt->txn);
	}
}

The tuple- (key-) wise logic will use memtx_index_key instead of tuple to uniquely identify a key in an index.

For instance, memtx_tx_track_gap_slow:

tarantool/src/box/memtx_tx.c

Lines 3910 to 3935 in 5fe44d8

	void
	memtx_tx_track_gap_slow(struct txn *txn, struct space *space, struct index *index,
	struct tuple *successor, enum iterator_type type,
	const char *key, uint32_t part_count)
	{
	if (txn->status != TXN_INPROGRESS)
	return;
	struct nearby_gap_item *item =
	memtx_tx_nearby_gap_item_new(txn, type, key, part_count);
	if (successor != NULL) {
	struct memtx_story *story;
	if (tuple_has_flag(successor, TUPLE_IS_DIRTY)) {
	story = memtx_tx_story_get(successor);
	} else {
	story = memtx_tx_story_new(space, successor);
	}
	assert(index->dense_id < story->index_count);
	assert(story->link[index->dense_id].in_index != NULL);
	rlist_add(&story->link[index->dense_id].read_gaps,
	&item->base.in_read_gaps);
	} else {
	rlist_add(&index->read_gaps, &item->base.in_read_gaps);
	}
	}

Will look like this (memtx_tx_story_link_key_get is discussed in story_link_key_storage):

void
memtx_tx_track_gap_slow(struct txn *txn, struct space *space, struct index *index,
			struct memtx_index_key *successor_key, enum iterator_type type,
			const char *key, uint32_t part_count)
{
	if (txn->status != TXN_INPROGRESS)
		return;

	struct nearby_gap_item *item =
		memtx_tx_nearby_gap_item_new(txn, type, key, part_count);

	struct tuple *successor = successor_multikey.tuple;
	if (successor != NULL) {
		struct memtx_story *story;
		if (tuple_has_flag(successor, TUPLE_IS_DIRTY)) {
			story = memtx_tx_story_get(successor);
		} else {
			story = memtx_tx_story_new(space, successor);
		}
		assert(index->dense_id < story->index_count);
                struct memtx_story_link_key *key = memtx_tx_story_link_key_get(successor, 
									       index->dense_id);
               
		assert(key->in_index != NULL);
		rlist_add(&key->read_gaps,
			  &item->base.in_read_gaps);
	} else {
		rlist_add(&index->read_gaps, &item->base.in_read_gaps);
	}
}

This will solve Index replace and Tracking read/write sets, as it will to process each multikey key independently.

story_link_key_storage

We will introduce a new abstraction that will allow to look up a memtx_story_link_key by memtx_index_key and generalize func_key_storage:

/** Key for search in `story_link_key_storage`. */
struct story_link_key_storage_key {
	/** Index key whose `memtx_story_link_key` we are searching for. */
	struct memtx_index_key index_key;
	/** Dense id of the index. */
	uint32_t index_id;
};

/** An element of `story_link_key_storage`. */
struct story_link_key_storage_item {
	/** Story link key. */
	struct memtx_story_link_key *link_key;
	/** Dense id of the index. */
	uint32_t index_id;
	/** Hash of the item. */
	uint32_t hash;
};

/** Look up a `memtx_story_link_key` in index `index_id` based on `key`. */
static struct memtx_story_link_key *
memtx_tx_story_link_key_get(struct memtx_index_key key, uint32_t index_id);

In order to track the read and write set of a memtx_index_key using memtx_story_link_key, memtx MVCC logic will be modified to use memtx_tx_story_link_get. This will effectively solve Looking up tracked states.

[drewdzzz]

At least, we should come up with an optimization to avoid hash table lookups when mk indexes are not used.
Or come up with a solution without a hash table, but probably it won't be so clean.