Lock free hash table. More...

#include <ut0lock_free_hash.h>

Inheritance diagram for ut_lock_free_hash_t:

Classes
struct	key_val_t
	(key, val) tuple type. More...

Public Member Functions
	ut_lock_free_hash_t (size_t initial_size, bool del_when_zero)
	Constructor. More...

	~ut_lock_free_hash_t () override
	Destructor. More...

int64_t	get (uint64_t key) const override
	Get the value mapped to a given key. More...

void	set (uint64_t key, int64_t val) override
	Set the value for a given key, either inserting a new (key, val) tuple or overwriting an existent value. More...

void	del (uint64_t key) override
	Delete a (key, val) pair from the hash. More...

void	inc (uint64_t key) override
	Increment the value for a given key with 1 or insert a new tuple (key, 1). More...

void	dec (uint64_t key) override
	Decrement the value of a given key with 1 or insert a new tuple (key, -1). More...

Public Member Functions inherited from ut_hash_interface_t
virtual	~ut_hash_interface_t ()=default
	Destructor. More...

Private Types
typedef ut_lock_free_list_node_t< key_val_t >	arr_node_t
	An array node in the hash. More...

typedef ut::allocator< arr_node_t * >	hollow_alloc_t

typedef std::list< arr_node_t *, hollow_alloc_t >	hollow_t

Private Member Functions
size_t	guess_position (uint64_t key, size_t arr_size) const
	A hash function used to map a key to its suggested position in the array. More...

key_val_t *	get_tuple_from_array (key_val_t *arr, size_t arr_size, uint64_t key) const
	Get the array cell of a key from a given array. More...

std::pair< ut_lock_free_cnt_t::handle_t, key_val_t * >	get_tuple (uint64_t key, arr_node_t **arr) const
	Get the array cell of a key. More...

key_val_t *	insert_or_get_position_in_array (key_val_t *arr, size_t arr_size, uint64_t key)
	Insert the given key into a given array or return its cell if already present. More...

void	copy_to_another_array (arr_node_t src_arr, arr_node_t dst_arr)
	Copy all used elements from one array to another. More...

bool	update_tuple (key_val_t *t, int64_t val_to_set, bool is_delta)
	Update the value of a given tuple. More...

void	optimize ()
	Optimize the hash table. More...

void	insert_or_update (uint64_t key, int64_t val, bool is_delta, arr_node_t *arr, bool optimize_allowed=true)
	Insert a new tuple or update an existent one. More...

Private Attributes
std::atomic< arr_node_t * >	m_data
	Storage for the (key, val) tuples. More...

hollow_t *	m_hollow_objects
	Container for hollow (semi-destroyed) objects that have been removed from the list that starts at m_data. More...

ib_mutex_t	m_optimize_latch
	Concurrent copy-all-elements-to-the-next-array, removal of the head of the list and freeing of its m_base member are serialized with this latch. More...

bool	m_del_when_zero
	True if a tuple should be automatically deleted from the hash if its value becomes 0 after an increment or decrement. More...

Static Private Attributes
static const uint64_t	UNUSED = UINT64_MAX
	A key == UNUSED designates that this cell in the array is empty. More...

static const uint64_t	AVOID = UNUSED - 1
	A key == AVOID designates an unusable cell. More...

static const int64_t	DELETED = NOT_FOUND - 1
	A val == DELETED designates that this cell in the array has been used in the past, but it was deleted later. More...

static const int64_t	GOTO_NEXT_ARRAY = DELETED - 1
	A val == GOTO_NEXT_ARRAY designates that this tuple (key, whatever) has been moved to the next array. More...

Additional Inherited Members
Static Public Attributes inherited from ut_hash_interface_t
static const int64_t	NOT_FOUND = INT64_MAX
	The value that is returned when the searched for key is not found. More...

Detailed Description

Lock free hash table.

It stores (key, value) pairs where both the key and the value are of integer type. The possible keys are: UNUSED: a (key = UNUSED, val) tuple means that it is empty/unused. This is the initial state of all keys. AVOID: a (key = AVOID, val = any) tuple means that this tuple is disabled, does not contain a real data and should be avoided by searches and inserts. This is used when migrating all elements of an array to the next array. real key: anything other than the above means this is a real key, specified by the user.

The possible values are: NOT_FOUND: a (key, val = NOT_FOUND) tuple means that it is just being inserted and returning "not found" is ok. This is the initial state of all values. DELETED: a (key, val = DELETED) tuple means that a tuple with this key existed before but was deleted at some point. Searches for this key return "not found" and inserts reuse the tuple, replacing the DELETED value with something else. GOTO_NEXT_ARRAY: a (key, val = GOTO_NEXT_ARRAY) tuple means that the searches for this tuple (get and insert) should go to the next array and repeat the search there. Used when migrating all tuples from one array to the next. real value: anything other than the above means this is a real value, specified by the user.

Transitions for keys (a real key is anything other than UNUSED and AVOID): UNUSED -> real key – allowed UNUSED -> AVOID – allowed anything else is not allowed: real key -> UNUSED – not allowed real key -> AVOID – not allowed real key -> another real key – not allowed AVOID -> UNUSED – not allowed AVOID -> real key – not allowed

Transitions for values (a real value is anything other than NOT_FOUND, DELETED and GOTO_NEXT_ARRAY): NOT_FOUND -> real value – allowed NOT_FOUND -> DELETED – allowed real value -> another real value – allowed real value -> DELETED – allowed real value -> GOTO_NEXT_ARRAY – allowed DELETED -> real value – allowed DELETED -> GOTO_NEXT_ARRAY – allowed anything else is not allowed: NOT_FOUND -> GOTO_NEXT_ARRAY – not allowed real value -> NOT_FOUND – not allowed DELETED -> NOT_FOUND – not allowed GOTO_NEXT_ARRAY -> real value – not allowed GOTO_NEXT_ARRAY -> NOT_FOUND – not allowed GOTO_NEXT_ARRAY -> DELETED – not allowed

Member Typedef Documentation

◆ arr_node_t

typedef ut_lock_free_list_node_t<key_val_t> ut_lock_free_hash_t::arr_node_t

private

An array node in the hash.

The hash table consists of a linked list of such nodes.

◆ hollow_alloc_t

typedef ut::allocator<arr_node_t *> ut_lock_free_hash_t::hollow_alloc_t

private

◆ hollow_t

typedef std::list<arr_node_t *, hollow_alloc_t> ut_lock_free_hash_t::hollow_t

private

Constructor & Destructor Documentation

◆ ut_lock_free_hash_t()

ut_lock_free_hash_t::ut_lock_free_hash_t	(	size_t	initial_size,
		bool	del_when_zero
	)

inlineexplicit

Constructor.

Not thread safe.

Parameters

[in]	initial_size	number of elements to allocate initially. Must be a power of 2, greater than 0.
[in]	del_when_zero	if true then automatically delete a tuple from the hash if due to increment or decrement its value becomes zero.

◆ ~ut_lock_free_hash_t()

ut_lock_free_hash_t::~ut_lock_free_hash_t ( )

inlineoverride

Destructor.

Not thread safe.

Member Function Documentation

◆ copy_to_another_array()

void ut_lock_free_hash_t::copy_to_another_array	(	arr_node_t *	src_arr,
		arr_node_t *	dst_arr
	)

inlineprivate

Copy all used elements from one array to another.

Flag the ones in the old array as 'go to the next array'.

Parameters

[in,out]	src_arr	array to copy from
[in,out]	dst_arr	array to copy to

◆ dec()

void ut_lock_free_hash_t::dec ( uint64_t key )

inlineoverridevirtual

Decrement the value of a given key with 1 or insert a new tuple (key, -1).

With respect to calling this together with set(), inc() or dec() the same applies as with inc(), see its comment. The only guarantee is that the calls will execute in isolation, but the order in which they will execute is undeterministic.

Parameters

[in] key key whose value to decrement

Implements ut_hash_interface_t.

◆ del()

void ut_lock_free_hash_t::del ( uint64_t key )

inlineoverridevirtual

Delete a (key, val) pair from the hash.

If this gets called concurrently with get(), inc(), dec() or set(), then to the caller it will look like the calls executed in isolation, the hash structure itself will not be damaged, but it is undefined in what order the calls will be executed. For example: Let this tuple exist in the hash: (key == 5, val == 10) Thread 1: inc(key == 5) Thread 2: del(key == 5) [1] If inc() executes first then the tuple will become (key == 5, val == 11) and then del() will make it (key == 5, val == DELETED), which get()s for key == 5 will return as NOT_FOUND. [2] If del() executes first then the tuple will become (key == 5, val == DELETED) and then inc() will change it to (key == 5, value == 1). It is undefined which one of [1] or [2] will happen. It is up to the caller to accept this behavior or prevent it at a higher level.

Parameters

[in] key key whose pair to delete

Implements ut_hash_interface_t.

◆ get()

int64_t ut_lock_free_hash_t::get ( uint64_t key ) const

inlineoverridevirtual

Get the value mapped to a given key.

Parameters

[in] key key to look for

Returns: the value that corresponds to key or NOT_FOUND.

Implements ut_hash_interface_t.

◆ get_tuple()

std::pair< ut_lock_free_cnt_t::handle_t, key_val_t * > ut_lock_free_hash_t::get_tuple	(	uint64_t	key,
		arr_node_t **	arr
	)		const

inlineprivate

Get the array cell of a key.

Parameters

[in]	key	key to search for
[in,out]	arr	start the search from this array; when this method ends, *arr will point to the array in which the search ended (in which the returned key_val resides)

Returns: If key was found: handle to the (updated) arr which contains the tuple and pointer to the array cell with the tuple. Otherwise an empty handle, and nullptr.

◆ get_tuple_from_array()

key_val_t * ut_lock_free_hash_t::get_tuple_from_array	(	key_val_t *	arr,
		size_t	arr_size,
		uint64_t	key
	)		const

inlineprivate

Get the array cell of a key from a given array.

Parameters

[in]	arr	array to search into
[in]	arr_size	number of elements in the array
[in]	key	search for a tuple with this key

Returns: pointer to the array cell or NULL if not found

◆ guess_position()

size_t ut_lock_free_hash_t::guess_position	(	uint64_t	key,
		size_t	arr_size
	)		const

inlineprivate

A hash function used to map a key to its suggested position in the array.

A linear search to the right is done after this position to find the tuple with the given key or find a tuple with key == UNUSED or AVOID which means that the key is not present in the array.

Parameters

[in]	key	key to map into a position
[in]	arr_size	number of elements in the array

Returns: a position (index) in the array where the tuple is guessed to be

◆ inc()

void ut_lock_free_hash_t::inc ( uint64_t key )

inlineoverridevirtual

Increment the value for a given key with 1 or insert a new tuple (key, 1).

If two threads call this method at the same time with the same key, then it is guaranteed that when both calls have finished, the value will be incremented with 2. If two threads call this method and set() at the same time with the same key it is undeterministic whether the value will be what was given to set() or what was given to set() + 1. E.g. Thread 1: set(key, val) Thread 2: inc(key) or Thread 1: inc(key) Thread 2: set(key, val) when both have finished the value will be either val or val + 1.

Parameters

[in] key key whose value to increment or insert as 1

Implements ut_hash_interface_t.

◆ insert_or_get_position_in_array()

key_val_t * ut_lock_free_hash_t::insert_or_get_position_in_array	(	key_val_t *	arr,
		size_t	arr_size,
		uint64_t	key
	)

inlineprivate

Insert the given key into a given array or return its cell if already present.

Parameters

[in]	arr	array into which to search and insert
[in]	arr_size	number of elements in the array
[in]	key	key to insert or whose cell to retrieve

Returns: a pointer to the inserted or previously existent tuple or NULL if a tuple with this key is not present in the array and the array is full, without any unused cells and thus insertion cannot be done into it.

◆ insert_or_update()

void ut_lock_free_hash_t::insert_or_update	(	uint64_t	key,
		int64_t	val,
		bool	is_delta,
		arr_node_t *	arr,
		bool	optimize_allowed = `true`
	)

inlineprivate

Insert a new tuple or update an existent one.

If a tuple with this key does not exist then a new one is inserted (key, val) and is_delta is ignored. If a tuple with this key exists and is_delta is true, then the current value is changed to be current value + val, otherwise it is overwritten to be val.

Parameters

[in]	key	key to insert or whose value to update
[in]	val	value to set; if the tuple does not exist or if is_delta is false, then the new value is set to val, otherwise it is set to old + val
[in]	is_delta	if true then set the new value to old + val, otherwise just set to val.
[in]	arr	array to start the search from
[in]	optimize_allowed	if true then call optimize() after an eventual grow(), if false, then never call optimize(). Used to prevent recursive optimize() call by insert_or_update() -> optimize() -> copy_to_another_array() -> insert_or_update() -> optimize().

◆ optimize()

void ut_lock_free_hash_t::optimize ( )

inlineprivate

Optimize the hash table.

Called after a new array is appended to the list of arrays (grow). Having more than one array in the list of arrays works, but is suboptimal because searches (for get/insert/update) have to search in more than one array. This method starts from the head of the list and migrates all tuples from this array to the next arrays. Then it removes the array from the head of the list, waits for readers to go away and frees it's m_base member.

◆ set()

void ut_lock_free_hash_t::set	(	uint64_t	key,
		int64_t	val
	)

inlineoverridevirtual

Set the value for a given key, either inserting a new (key, val) tuple or overwriting an existent value.

If two threads call this method at the same time with the key, but different val, then when both methods have finished executing the value will be one of the two ones, but undeterministic which one. E.g. Thread 1: set(key, val_a) Thread 2: set(key, val_b) when both have finished, then a tuple with the given key will be present with value either val_a or val_b.

Parameters

[in]	key	key whose value to set
[in]	val	value to be set

Implements ut_hash_interface_t.

◆ update_tuple()

bool ut_lock_free_hash_t::update_tuple	(	key_val_t *	t,
		int64_t	val_to_set,
		bool	is_delta
	)

inlineprivate

Update the value of a given tuple.

Parameters

[in,out]	t	tuple whose value to update
[in]	val_to_set	value to set or delta to apply
[in]	is_delta	if true then set the new value to old + val, otherwise just set to val

Return values

true	update succeeded
false	update failed due to GOTO_NEXT_ARRAY

Returns: whether the update succeeded or not

Member Data Documentation

◆ AVOID

const uint64_t ut_lock_free_hash_t::AVOID = UNUSED - 1

staticprivate

A key == AVOID designates an unusable cell.

This cell of the array has been empty (key == UNUSED), but was then marked as AVOID in order to prevent new inserts into it. Searches should treat this like UNUSED (ie if they encounter it before the key they are searching for then stop the search and declare 'not found').

◆ DELETED

const int64_t ut_lock_free_hash_t::DELETED = NOT_FOUND - 1

staticprivate

A val == DELETED designates that this cell in the array has been used in the past, but it was deleted later.

Searches should return NOT_FOUND when they encounter it.

◆ GOTO_NEXT_ARRAY

const int64_t ut_lock_free_hash_t::GOTO_NEXT_ARRAY = DELETED - 1

staticprivate

A val == GOTO_NEXT_ARRAY designates that this tuple (key, whatever) has been moved to the next array.

The search for it should continue there.

◆ m_data

std::atomic<arr_node_t *> ut_lock_free_hash_t::m_data

private

Storage for the (key, val) tuples.

◆ m_del_when_zero

bool ut_lock_free_hash_t::m_del_when_zero

private

True if a tuple should be automatically deleted from the hash if its value becomes 0 after an increment or decrement.

◆ m_hollow_objects

hollow_t* ut_lock_free_hash_t::m_hollow_objects

private

Container for hollow (semi-destroyed) objects that have been removed from the list that starts at m_data.

Those objects have their m_base member freed and are entirely destroyed at the end of the hash table life time. The access to this member is protected by m_optimize_latch (adding of new elements) and the removal of elements is done in the destructor of the hash table.

◆ m_optimize_latch

ib_mutex_t ut_lock_free_hash_t::m_optimize_latch

private

Concurrent copy-all-elements-to-the-next-array, removal of the head of the list and freeing of its m_base member are serialized with this latch.

Those operations could be implemented without serialization, but this immensely increases the complexity of the code. Growing of the hash table is not too hot operation and thus we chose simplicity and maintainability instead of top performance in this case. "Get" operations and "insert/update" ones that do not cause grow still run concurrently even if this latch is locked.

◆ UNUSED

const uint64_t ut_lock_free_hash_t::UNUSED = UINT64_MAX

staticprivate

A key == UNUSED designates that this cell in the array is empty.

The documentation for this class was generated from the following file:

storage/innobase/include/ut0lock_free_hash.h

Classes

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Static Private Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ arr_node_t

◆ hollow_alloc_t

◆ hollow_t

Constructor & Destructor Documentation

◆ ut_lock_free_hash_t()

◆ ~ut_lock_free_hash_t()

Member Function Documentation

◆ copy_to_another_array()

◆ dec()

◆ del()

◆ get()

◆ get_tuple()

◆ get_tuple_from_array()

◆ guess_position()

◆ inc()

◆ insert_or_get_position_in_array()

◆ insert_or_update()

◆ optimize()

◆ set()

◆ update_tuple()

Member Data Documentation

◆ AVOID

◆ DELETED

◆ GOTO_NEXT_ARRAY

◆ m_data

◆ m_del_when_zero

◆ m_hollow_objects

◆ m_optimize_latch

◆ UNUSED