Memtx multikey index replace variants: factor out multikey logic

[CuriousGeorgiy]

Table of Contents

• Problem
• Goal
• Solution
  • memtx_index_key
  • Factoring out multikey logic

Problem

Currently, memtx multikey index variants encapsulate the processing of multiple multikey keys. This is bad for two reasons.

First, this violates the memtx index replace interface. Each replace operation is supposed to return a replaced and a successor tuple for tracking a transaction's read and write sets in memtx MVCC. However, multikey index variants yield multiple replaced and successor tuples which cannot be returned through the existing interface.

Second, this makes the replace operation coarse grained. Effectively, we lose control of the index state of each multikey key: either all the keys are inserted the index or they are deleted from it. However, in the context of memtx MVCC, each multikey key has an independent history chain, and thus its presence in the index needs to managed independently.

Together, these discrepancies prevent support of multikey index variants in memtx MVCC (see also #12313).

Last but not least, this complicates the indexing logic. The replace operation for multikey index variants builds complex insertion, deletion and rolling back loops on top of the regular index replace operation. This is bad, as the replace operation should be as simple as possible and it should not be responsible for multiple operations.

Goal

Most importantly, we need to make the replace operation for multikey index variants interoperable with memtx MVCC. To do this, we need to:

• return replaced and successor values from the replace operation for each multikey key;
• provide an interface for a replace operation on a single multikey key.

Additionally, it would be good to simplify the replace operation logic.

Internally, we will still have several overload of memtx_index_vtab::replace for each index variant (regular, multikey, functional). Merging these overloads is out of the scope of this RFC (#12190).

Solution

The solution will be based on the new memtx_index_key abstraction described below. This abstraction will allow to generalize a tuple in the case of multikey index variants.

memtx_index_key

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:

/**
 * Generalization of a tuple for multikey index variants that allows to uniquely identify multikey  
 * keys.
 */
struct memtx_index_key {
	/** Tuple used for indexing. */
	struct tuple *tuple;
	/**
	 * 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;
};

/** Replace a key in the index. */
int
memtx_index_replace_key(struct index *index, struct memtx_index_key old_key,
			struct memtx_index_key new_key, enum dup_replace_mode mode,
			struct memtx_index_key *replaced, struct memtx_index_key *successor);

memtx_index_replace_key will be used in memtx MVCC for chain-wise operations. This will allow it to manage each multikey key's presence in an index.

Factoring out multikey logic

The virtual index replace method, memtx_index_vtab::replace will be changed to have the following signature (same as memtx_index_replace_key):

int (*replace)(struct index *index, struct memtx_index_key old_key, struct memtx_index_key new_key,	       								
	       enum dup_replace_mode mode, struct memtx_index_key *replaced, 
	       struct memtx_index_key *successor);

Multikey index variants of replace (memtx_tree_index_replace_multikey and memtx_tree_func_index_replace) will only handle one operation: either the replacement of new_key and duplicate check of old_key->tuple or deletion of old_key.

We will introduce a new abstraction for multikey index results, memtx_index_result, and a new replace method, memtx_index_replace_with_results:

/** Generalization of an index result/successor tuple for multikey index variants. */
struct memtx_index_result {
	/** A list of result/successor `memtx_index_key`s allocated on the fiber region. */
	struct rlist keys;
};

/** 
 * Wrapper around `memtx_index_vtab::replace` with multiplexing and multikey logic for different index
 * variants. Collects lists of `replaced` and `successor` keys, allocating the lists on the fiber region
 * (requires cleanup after processing the result keys).
 */
int
memtx_index_replace_with_results(struct index *index, struct tuple *old_tuple,
				 struct tuple *new_tuple, enum dup_replace_mode mode,
				 struct memtx_index_result *replaced,
				 struct memtx_index_result *successor);

Since results are only used by MVCC, the rest of the code will use a simplified version of memtx_index_replace:

/** 
 * Simplified version of `memtx_index_replace_with_results` that does not collect results and does 
 * not require fiber region cleanup. 
 */
int
memtx_index_replace(struct index *index, struct tuple *old_tuple, struct tuple *new_tuple, 
		    enum dup_replace_mode mode);

Multikey logic will be factored out to memtx_index_replace{_with_results}. It will responsible for:

• multiplexing the logic between regular, multikey and functional indexes;
• handling insertion and deletion of multikey keys;
• handling rollback of failed multikey operations;
• collecting the replaced and successor lists (memtx_index_replace_with_results).

memtx_index_replace_with_results will be used in memtx MVCC to collect the results of index operations. This will allow it to collect multiple replaced and successor keys.

[drewdzzz]

AFAIU, memtx_index_replace_with_results will be used only in memtx_tx_add_stmt. Maybe, it would be better to inline it (or create a helper in memtx_tx)?

[CuriousGeorgiy]

It will also be used for memtx_space_replace_primary_key. Inlining it would expose memtx_tx to memtx_index internals.

[drewdzzz]

Can you provide some examples of usage of new API? For example, in memtx_tx_add_stmt?

[CuriousGeorgiy]

I have implemented a PoC of the API in #12385.

[drewdzzz]

AFAIR, you said there are some problems with functional indexes (that they are compared by pointers sometimes). How those problems will be solved in the new API?

[CuriousGeorgiy]

This will remain in encapsulated in memtx_tree_func_index_replace.