[Tarantool-patches] [PATCH v2 1/5] box: introduce matrix clock

[Serge Petrenko <sergepetrenko@tarantool.org>]

From: Georgy Kirichenko <georgy@tarantool.org>

A matrix clock which allows to maintain a set of vclocks and
their components order. The main target is to be able to
build a vclock which contains lsns each one is less or equal
that n corresponding lsn from a matrix clock.

The purpose of the matrix clock is to evaluate a vclock
which is already processed by wal consumers like relays
or to obtain a majority vclock to commit journal entries
in case of synchronous replication.

@sergepetrenko: refactoring & rewrite comments to doxygen style.

Part of #980, #3794
Prerequisite #4114
---
 src/box/CMakeLists.txt   |   4 +
 src/box/mclock.c         | 394 +++++++++++++++++++++++++++++++++++++++
 src/box/mclock.h         | 151 +++++++++++++++
 src/box/wal.c            |   1 -
 test/unit/CMakeLists.txt |   2 +
 test/unit/mclock.result  |  18 ++
 test/unit/mclock.test.c  | 160 ++++++++++++++++
 7 files changed, 729 insertions(+), 1 deletion(-)
 create mode 100644 src/box/mclock.c
 create mode 100644 src/box/mclock.h
 create mode 100644 test/unit/mclock.result
 create mode 100644 test/unit/mclock.test.c

diff --git a/src/box/CMakeLists.txt b/src/box/CMakeLists.txt
index 56758bd2f..cbffab046 100644
--- a/src/box/CMakeLists.txt
+++ b/src/box/CMakeLists.txt
@@ -32,6 +32,9 @@ target_link_libraries(box_error core stat)
 add_library(vclock STATIC vclock.c)
 target_link_libraries(vclock core)
 
+add_library(mclock STATIC mclock.c)
+target_link_libraries(mclock vclock core)
+
 add_library(xrow STATIC xrow.c iproto_constants.c)
 target_link_libraries(xrow server core small vclock misc box_error
                       scramble ${MSGPUCK_LIBRARIES})
@@ -134,6 +137,7 @@ add_library(box STATIC
     execute.c
     sql_stmt_cache.c
     wal.c
+    mclock.c
     call.c
     merger.c
     ${lua_sources}
diff --git a/src/box/mclock.c b/src/box/mclock.c
new file mode 100644
index 000000000..de4ca2a08
--- /dev/null
+++ b/src/box/mclock.c
@@ -0,0 +1,394 @@
+/*
+ * Copyright 2010-2020, Tarantool AUTHORS, please see AUTHORS file.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above
+ *    copyright notice, this list of conditions and the
+ *    following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above
+ *    copyright notice, this list of conditions and the following
+ *    disclaimer in the documentation and/or other materials
+ *    provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY <COPYRIGHT HOLDER> ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
+ * <COPYRIGHT HOLDER> OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
+ * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
+ * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+#include "mclock.h"
+
+void
+mclock_create(struct mclock *mclock)
+{
+	memset(mclock, 0, sizeof(struct mclock));
+}
+
+void
+mclock_destroy(struct mclock *mclock)
+{
+	memset(mclock, 0, sizeof(struct mclock));
+}
+
+/**
+ * Check whether vclock contains any ids unknown to the matrix
+ * clock and initialize the corresponding column, if it does.
+ *
+ * @param mclock Matrix clock.
+ * @param id the replica id vector clock comes from.
+ * @param vclock Vector clock.
+ */
+static void
+mclock_adjust_col_map(struct mclock *mclock, uint32_t id,
+		      const struct vclock *vclock)
+{
+	assert(id < VCLOCK_MAX);
+	/* Evaluate new matrix column identifiers. */
+	uint32_t new_col_map = vclock->map & ~mclock->col_map;
+	struct bit_iterator col_map_it;
+	bit_iterator_init(&col_map_it, &new_col_map, sizeof(new_col_map), true);
+	for (size_t col_id = bit_iterator_next(&col_map_it); col_id < VCLOCK_MAX;
+	     col_id = bit_iterator_next(&col_map_it)) {
+		/* Register new replica identifier. */
+		mclock->col_map |= (1 << col_id);
+		struct bit_iterator row_map_it;
+		bit_iterator_init(&row_map_it, &mclock->row_map,
+				  sizeof(mclock->row_map), true);
+		/* Buuild an order map for given column. */
+		mclock->order[col_id][0] = id;
+		for (size_t row_id = bit_iterator_next(&row_map_it), i = 1;
+		     row_id < VCLOCK_MAX;
+		     row_id = bit_iterator_next(&row_map_it)) {
+			if (row_id != id)
+				mclock->order[col_id][i++] = row_id;
+		}
+	}
+}
+
+/**
+ * Fetch the n-th largest lsn for the given replica id from the
+ * matrix clock.
+ *
+ * @param mclock Matrix clock.
+ * @param col_id Replica id to fetch lsn for.
+ * @param pos The position of desired lsn in ordered array.
+ *
+ * @return An lsn from the \a pos position in the ordered array
+ *         corresponding to \a col_id.
+ */
+static inline int64_t
+mclock_get_pos_lsn(const struct mclock *mclock, uint32_t col_id, uint32_t pos)
+{
+	assert(col_id < VCLOCK_MAX);
+	assert(pos < VCLOCK_MAX);
+	uint32_t row_id = mclock->order[col_id][pos];
+	return vclock_get(mclock->vclock + row_id, col_id);
+}
+
+/**
+ * Search the ordered array corresponding to the given replica id
+ * for the range which contains entries with given lsn.
+ *
+ * @param mclock Matrix clock.
+ * @param col_id Replica id to perform search for.
+ * @param lsn Lsn to match.
+ * @param[in,out] from The beginning of the found range.
+ * @param[in,out] to The end of the found range.
+ */
+static inline void
+mclock_find_range(const struct mclock *mclock, uint32_t col_id, int64_t lsn,
+		  uint32_t *from, uint32_t *to)
+{
+	/* Setup initial search ranges for the binary search. */
+	uint32_t from_lo = *from, from_hi = *to;
+	uint32_t to_lo = *from, to_hi = *to;
+	/* Look for `from' position. */
+	while (from_hi - from_lo > 1) {
+		uint32_t mid = (from_lo + from_hi) / 2;
+		int64_t mid_lsn = mclock_get_pos_lsn(mclock, col_id, mid);
+		if (mid_lsn <= lsn)
+			from_hi = mid;
+		else
+			from_lo = mid;
+		/*
+		 * Optimization: check if we could decrease
+		 * the `to' search range.
+		 */
+		if (mid_lsn < lsn)
+			to_hi = MIN(mid, to_hi);
+		else
+			to_lo  = MAX(mid, to_lo);
+	}
+	if (mclock_get_pos_lsn(mclock, col_id, from_lo) > lsn)
+		*from = from_hi;
+	else
+		*from = from_lo;
+	/* Look for `to' position. */
+	while (to_hi - to_lo > 1) {
+		uint32_t mid = (to_lo + to_hi) / 2;
+		int64_t mid_lsn = mclock_get_pos_lsn(mclock, col_id, mid);
+		if (mid_lsn < lsn)
+			to_hi = mid;
+		else
+			to_lo = mid;
+	}
+	*to = to_hi;
+}
+
+/**
+ * Make space for an array element being moved from \a old_pos
+ * to \a new pos. In order to do so, shift all array members
+ * between old pos and new pos in the direction of \a old_pos,
+ * effectively making space for the element at \a new_pos and
+ * rewriting it at \a old_pos at the same time.
+ *
+ * @param mclock Matrix clock.
+ * @param col_id The column id to shift.
+ * @param old_pos The previous position of the array element
+ *                being moved.
+ * @param new_pos Desired position of the array element being
+ *                moved.
+ */
+static inline void
+mclock_shift(struct mclock *mclock, uint32_t col_id, uint32_t old_pos,
+	     uint32_t new_pos)
+{
+	if (old_pos > new_pos) {
+		memmove(mclock->order[col_id] + new_pos + 1,
+			mclock->order[col_id] + new_pos,
+			(old_pos - new_pos) * sizeof(**mclock->order));
+	} else if (old_pos < new_pos) {
+		memmove(mclock->order[col_id] + old_pos,
+			mclock->order[col_id] + old_pos + 1,
+			(new_pos - old_pos) * sizeof(**mclock->order));
+	}
+}
+
+/**
+ * Update replica vclock and reorder mclock members.
+ *
+ * @param mclock Matrix clock.
+ * @param id Replica id whose vclock to update.
+ * @param vclock Vector clock.
+ */
+static void
+mclock_update_vclock(struct mclock *mclock, uint32_t id,
+		     const struct vclock *vclock)
+{
+	uint32_t count = __builtin_popcount(mclock->row_map);
+	mclock_adjust_col_map(mclock, id, vclock);
+	/* Perform reordering for each column. */
+	struct bit_iterator col_map_it;
+	bit_iterator_init(&col_map_it, &mclock->col_map,
+			  sizeof(mclock->col_map), true);
+	for (size_t col_id = bit_iterator_next(&col_map_it); col_id < VCLOCK_MAX;
+	     col_id = bit_iterator_next(&col_map_it)) {
+		int64_t new_lsn = vclock_get(vclock, col_id);
+		int64_t old_lsn = vclock_get(mclock->vclock + id, col_id);
+
+		if (old_lsn == new_lsn)
+			continue;
+		/*
+		 * Find a positions range which contains given
+		 * replica id for current column (old lsn position).
+		 */
+		uint32_t from = 0, to = count;
+		mclock_find_range(mclock, col_id, old_lsn, &from, &to);
+		assert(to > from);
+		uint32_t old_pos = from, new_pos;
+		while (old_pos < to) {
+			uint32_t replica_id = mclock->order[col_id][old_pos];
+			if (replica_id == id)
+				break;
+			++old_pos;
+		}
+		/* Replica id should be found. */
+		assert(old_pos < to);
+		if (new_lsn > mclock_get_pos_lsn(mclock, col_id, 0)) {
+			/*
+			 * New lsn is the biggest one so put on
+			 * the first position in a column.
+			 */
+			new_pos = 0;
+		} else if (new_lsn <= mclock_get_pos_lsn(mclock, col_id,
+							 count - 1)) {
+			/* The least one - the last position. */
+			new_pos = count - 1;
+		} else {
+			/* Find a range of position which contains new lsn. */
+			if (new_lsn > old_lsn)
+				from = 0;
+			else
+				to = count;
+			mclock_find_range(mclock, col_id, new_lsn, &from, &to);
+			/* Take care about positions shift - to the
+			 * head or to the tail of column order map.
+			 */
+			new_pos = to - (new_lsn <= old_lsn? 1: 0);
+		}
+
+		if (old_pos == new_pos)
+			continue;
+		mclock_shift(mclock, col_id, old_pos, new_pos);
+		mclock->order[col_id][new_pos] = id;
+	}
+
+	vclock_copy(&mclock->vclock[id], vclock);
+}
+
+/**
+ * Delete the vclock coming from a replica with given id.
+ *
+ * @param mclock Matrix clock.
+ * @param id Replica id whose vclock to remove.
+ */
+static void
+mclock_delete_vclock(struct mclock *mclock, uint32_t id)
+{
+	assert((mclock->row_map & (1 << id)) != 0);
+	uint32_t count = __builtin_popcount(mclock->row_map);
+	/* Perform reordering for each column. */
+	struct bit_iterator col_map_it;
+	bit_iterator_init(&col_map_it, &mclock->col_map,
+			  sizeof(mclock->col_map), true);
+
+	for (size_t col_id = bit_iterator_next(&col_map_it);
+	     col_id < VCLOCK_MAX; col_id = bit_iterator_next(&col_map_it)) {
+		int64_t old_lsn = vclock_get(mclock->vclock + id, col_id);
+		/*
+		 * Find a positions range which contains given
+		 * replica id for current column (old lsn position).
+		 */
+		uint32_t from = 0, to = count;
+		mclock_find_range(mclock, col_id, old_lsn, &from, &to);
+		assert(to > from);
+		uint32_t old_pos = from, new_pos = count - 1;
+		while (old_pos < to) {
+			uint32_t replica_id = mclock->order[col_id][old_pos];
+			if (replica_id == id)
+				break;
+			++old_pos;
+		}
+		/* Replica id should be found. */
+		assert(old_pos < to);
+		new_pos = count - 1;
+
+		if (old_pos == new_pos)
+			continue;
+		mclock_shift(mclock, col_id, old_pos, new_pos);
+	}
+	mclock->row_map ^= (1 << id);
+}
+
+void
+mclock_update(struct mclock *mclock, uint32_t id, const struct vclock *vclock)
+{
+	/* Vclock is zero - delete the corresponding entry. */
+	if (vclock_sum(vclock) == 0) {
+		if ((mclock->row_map & (1 << id)) != 0)
+			mclock_delete_vclock(mclock, id);
+		return;
+	}
+	/*
+	 * The given replica id is not yet attached so
+	 * put a zero vclock on the last position with
+	 * corresponding replica identifier.
+	 */
+	if ((mclock->row_map & (1 << id)) == 0) {
+		vclock_create(&mclock->vclock[id]);
+		mclock->row_map |= 1 << id;
+		uint32_t count = __builtin_popcount(mclock->row_map);
+		struct bit_iterator col_map_it;
+		bit_iterator_init(&col_map_it, &mclock->col_map,
+				  sizeof(mclock->col_map), true);
+		for (size_t col_id = bit_iterator_next(&col_map_it);
+		     col_id < VCLOCK_MAX;
+		     col_id = bit_iterator_next(&col_map_it)) {
+			mclock->order[col_id][count - 1] = id;
+		}
+	}
+	mclock_update_vclock(mclock, id, vclock);
+}
+
+int
+mclock_get(struct mclock *mclock, int32_t offset, struct vclock *vclock)
+{
+	int32_t count = __builtin_popcount(mclock->row_map);
+	/* Check if given offset is out of mclock range. */
+	if (offset >= count || offset < -count) {
+		vclock_create(vclock);
+		return -1;
+	}
+	offset = (offset + count) % count;
+	vclock_create(vclock);
+	/* Fetch lsn for each known replica identifier. */
+	struct bit_iterator col_map_it;
+	bit_iterator_init(&col_map_it, &mclock->col_map,
+			  sizeof(mclock->col_map), true);
+	for (size_t col_id = bit_iterator_next(&col_map_it); col_id < VCLOCK_MAX;
+	     col_id = bit_iterator_next(&col_map_it)) {
+		int64_t lsn = mclock_get_pos_lsn(mclock, col_id, offset);
+		if (lsn > 0)
+			vclock_follow(vclock, col_id, lsn);
+	}
+	return 0;
+}
+
+int
+mclock_get_row(struct mclock *mclock, uint32_t id, struct vclock *vclock)
+{
+	if (mclock->row_map && (1 << id) == 0)
+		return -1;
+	vclock_copy(vclock, mclock->vclock + id);
+	return 0;
+}
+
+int
+mclock_get_col(struct mclock *mclock, uint32_t id, struct vclock *vclock)
+{
+	vclock_create(vclock);
+	if (mclock->col_map && (1 << id) == 0)
+		return -1;
+
+	struct bit_iterator row_map_it;
+	bit_iterator_init(&row_map_it, &mclock->row_map,
+			  sizeof(mclock->row_map), true);
+	for (size_t row_id = bit_iterator_next(&row_map_it);
+	     row_id < VCLOCK_MAX; row_id = bit_iterator_next(&row_map_it)) {
+		int64_t lsn = vclock_get(mclock->vclock + row_id, id);
+		if (lsn == 0)
+			continue;
+		vclock_follow(vclock, row_id, lsn);
+	}
+
+	return 0;
+}
+
+bool
+mclock_check(struct mclock *mclock)
+{
+	uint32_t count = __builtin_popcount(mclock->row_map);
+	struct bit_iterator col_map_it;
+	bit_iterator_init(&col_map_it, &mclock->col_map,
+			  sizeof(mclock->col_map), true);
+	for (size_t col_id = bit_iterator_next(&col_map_it); col_id < VCLOCK_MAX;
+	     col_id = bit_iterator_next(&col_map_it)) {
+		for (uint32_t n = 0; n < count - 1; ++n)
+			if (mclock_get_pos_lsn(mclock, col_id, n) <
+			    mclock_get_pos_lsn(mclock, col_id, n + 1))
+				return false;
+	}
+	return true;
+}
diff --git a/src/box/mclock.h b/src/box/mclock.h
new file mode 100644
index 000000000..fb734a6d5
--- /dev/null
+++ b/src/box/mclock.h
@@ -0,0 +1,151 @@
+#ifndef INCLUDES_TARANTOOL_MCLOCK_H
+#define INCLUDES_TARANTOOL_MCLOCK_H
+/*
+ * Copyright 2010-2020, Tarantool AUTHORS, please see AUTHORS file.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above
+ *    copyright notice, this list of conditions and the
+ *    following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above
+ *    copyright notice, this list of conditions and the following
+ *    disclaimer in the documentation and/or other materials
+ *    provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY <COPYRIGHT HOLDER> ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
+ * <COPYRIGHT HOLDER> OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
+ * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
+ * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+#include <stdlib.h>
+
+#include "vclock.h"
+
+#if defined(__cplusplus)
+extern "C" {
+#endif /* defined(__cplusplus) */
+
+/**
+ * The matrix clock structure contains vclocks as seen by
+ * cluster members.
+ */
+struct mclock {
+	/** A bit map containing row ids present in the mclock. */
+	uint32_t row_map;
+	/**
+	 * A bit map ofd component ids set in any of the
+	 * contained vclocks.
+	 */
+	uint32_t col_map;
+	/**
+	 * An array of vclocks indexed by replica ids.
+	 */
+	struct vclock vclock[VCLOCK_MAX];
+	/**
+	 * Per column ordered map. Each row describes an ordered
+	 * map of attached replica identifiers where the biggest
+	 * lsn is on the first position. In case of sequence of
+	 * the equal lsns the latest is on the last position in
+	 * the sequence.
+	 * For instance, if we have the following vclocks:
+	 *  1: {1: 10, 2: 12, 3: 0}
+	 *  2: {1: 10, 2: 14, 3: 1}
+	 *  3: {1: 0, 2: 8, 3: 4}
+	 * The order map will look as follows:
+	 *  {{1, 2, 3}, {2, 1, 3}, {3, 2, 1}}
+	 */
+	uint8_t order[VCLOCK_MAX][VCLOCK_MAX];
+};
+
+/** Create a mclock structure. */
+void
+mclock_create(struct mclock *mclock);
+
+/** Reset mclock. */
+void
+mclock_destroy(struct mclock *mclock);
+
+/**
+ * Update a vclock identified by replica id and
+ * sort mclock members.
+ */
+void
+mclock_update(struct mclock *mclock, uint32_t id, const struct vclock *vclock);
+
+/**
+ * Build a vclock each component of which is less than or equal
+ * to offset + 1 (or count + offset + 1 if offset < 0)
+ * corresponding components of contained vclocks.
+ * So mclock_get(mclock, 0) selects the biggest lsns for each
+ * column and mclock_get(-1) will select the smallest lsns for
+ * each column.
+ * For instance if we have mclock with the following vclocks:
+ *  1: {1: 10, 2: 12, 3: 0}
+ *  2: {1: 10, 2: 14, 3: 1}
+ *  3: {1: 0, 2: 8, 3: 4}
+ * mclock_get(0) will build vclock {1: 10, 2: 14, 3: 4}
+ * whereas  mclock_get(2) build {1: 0, 2: 8, 3: 0}
+ *
+ * @param mclock Matrix clock.
+ * @param offset The count of components which are greater than
+ *               the output vclock.
+ *
+ * @return A vclock whose each component is less than or equal to
+ *         offset + 1 other vclocks' components.
+ */
+int
+mclock_get(struct mclock *mclock, int32_t offset, struct vclock *vclock);
+
+/**
+ * Get a vclock corresponding to the given replica id.
+ *
+ * @param mclock Matrix clock.
+ * @param id Replica id.
+ * @param[out] vclock Found vclock.
+ *
+ * @return  0 vclock was found
+ *         -1 vclock corresponding to \a id isn't in mclock.
+ */
+int
+mclock_get_row(struct mclock *mclock, uint32_t id, struct vclock *vclock);
+
+/**
+ * Fetch a column from a matrix clock. Such column describes
+ * the id replica lsn visible by cluster members.
+ *
+ * Get a column from the matrix clock. The column contains the
+ * vclock components corresponding to the given id as seen by
+ * cluster members.
+ *
+ * @param mclock Matrix clock.
+ * @param id Replica id indicating vclock component to fetch.
+ * @param[out] vclock Found column.
+ *
+ * @return  0 the column was found
+ *         -1 the corresponding column isn't in mclock.
+ */
+int
+mclock_get_col(struct mclock *mclock, uint32_t id,  struct vclock *vclock);
+
+/** Check the mclock integrity. */
+bool
+mclock_check(struct mclock *mclock);
+
+#if defined(__cplusplus)
+} /* extern "C" */
+#endif /* defined(__cplusplus) */
+
+#endif /* INCLUDES_TARANTOOL_MCLOCK_H */
diff --git a/src/box/wal.c b/src/box/wal.c
index 1668c9348..ecbe0919e 100644
--- a/src/box/wal.c
+++ b/src/box/wal.c
@@ -1429,7 +1429,6 @@ wal_notify_watchers(struct wal_writer *writer, unsigned events)
 		wal_watcher_notify(watcher, events);
 }
 
-
 /**
  * After fork, the WAL writer thread disappears.
  * Make sure that atexit() handlers in the child do
diff --git a/test/unit/CMakeLists.txt b/test/unit/CMakeLists.txt
index 4ac08de8d..dd3e5f0c3 100644
--- a/test/unit/CMakeLists.txt
+++ b/test/unit/CMakeLists.txt
@@ -65,6 +65,8 @@ add_executable(bloom.test bloom.cc)
 target_link_libraries(bloom.test salad)
 add_executable(vclock.test vclock.cc)
 target_link_libraries(vclock.test vclock unit)
+add_executable(mclock.test mclock.test.c)
+target_link_libraries(mclock.test mclock vclock bit unit)
 add_executable(xrow.test xrow.cc)
 target_link_libraries(xrow.test xrow unit)
 add_executable(decimal.test decimal.c)
diff --git a/test/unit/mclock.result b/test/unit/mclock.result
new file mode 100644
index 000000000..eb3aa649d
--- /dev/null
+++ b/test/unit/mclock.result
@@ -0,0 +1,18 @@
+1..2
+    1..1
+	*** test_random_stress ***
+    ok 1 - random stress
+	*** test_random_stress: done ***
+ok 1 - subtests
+    1..8
+	*** test_func ***
+    ok 1 - consistency 1
+    ok 2 - first vclock 1
+    ok 3 - last vclock 1
+    ok 4 - second vclock
+    ok 5 - consistency 2
+    ok 6 - consistency 3
+    ok 7 - first vclock - 2
+    ok 8 - last vclock - 2
+	*** test_func: done ***
+ok 2 - subtests
diff --git a/test/unit/mclock.test.c b/test/unit/mclock.test.c
new file mode 100644
index 000000000..675cbeee3
--- /dev/null
+++ b/test/unit/mclock.test.c
@@ -0,0 +1,160 @@
+/*
+ * Copyright 2010-2020, Tarantool AUTHORS, please see AUTHORS file.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above
+ *    copyright notice, this list of conditions and the
+ *    following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above
+ *    copyright notice, this list of conditions and the following
+ *    disclaimer in the documentation and/or other materials
+ *    provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY <COPYRIGHT HOLDER> ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
+ * <COPYRIGHT HOLDER> OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
+ * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
+ * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+#include "unit.h"
+#include <stdarg.h>
+
+#include "box/mclock.h"
+
+static void
+test_random_stress()
+{
+	srand(time(NULL));
+	plan(1);
+	header();
+	struct mclock mclock;
+	mclock_create(&mclock);
+	bool ok = true;
+	for (int i = 0; i < 50000; ++i) {
+		struct vclock vclock;
+		vclock_create(&vclock);
+		uint32_t id = rand() % 31 + 1;
+		/* Count of non-zero items. */
+		int tm = rand() % 31;
+		for (int t = 0; t < tm;) {
+			uint32_t j = rand() % 31 + 1;
+			if (vclock_get(&vclock, j) > 0)
+				continue;
+			vclock_follow(&vclock, j, rand() + 1);
+			++t;
+		}
+		mclock_update(&mclock, id, &vclock);
+		if (!(ok = mclock_check(&mclock)))
+			break;
+	}
+	struct vclock vclock;
+	vclock_create(&vclock);
+	for (int i = 1; i < 32; ++i)
+		mclock_update(&mclock, i, &vclock);
+	mclock_destroy(&mclock);
+	is(ok, true, "random stress");
+	footer();
+	check_plan();
+}
+
+static void
+test_func()
+{
+	plan(8);
+	header();
+	struct mclock mclock;
+	mclock_create(&mclock);
+	struct vclock v1, v2, v3;
+	vclock_create(&v1);
+	vclock_follow(&v1, 1, 11);
+	vclock_follow(&v1, 2, 21);
+	vclock_follow(&v1, 3, 31);
+	vclock_create(&v2);
+	vclock_follow(&v2, 1, 22);
+	vclock_follow(&v2, 2, 12);
+	vclock_follow(&v2, 3, 30);
+	vclock_create(&v3);
+	vclock_follow(&v3, 2, 32);
+	vclock_follow(&v3, 3, 2);
+	vclock_follow(&v3, 4, 5);
+	mclock_update(&mclock, 1, &v1);
+	mclock_update(&mclock, 2, &v2);
+	mclock_update(&mclock, 3, &v3);
+	is(mclock_check(&mclock), true, "consistency 1");
+
+	struct vclock v, t;
+	vclock_create(&t);
+	vclock_follow(&t, 1, 22);
+	vclock_follow(&t, 2, 32);
+	vclock_follow(&t, 3, 31);
+	vclock_follow(&t, 4, 5);
+
+	mclock_get(&mclock, 0, &v);
+	is(vclock_compare(&v, &t), 0, "first vclock 1");
+
+	vclock_create(&t);
+	vclock_follow(&t, 2, 12);
+	vclock_follow(&t, 3, 2);
+
+	mclock_get(&mclock, -1, &v);
+	is(vclock_compare(&v, &t), 0, "last vclock 1");
+
+	vclock_create(&t);
+	vclock_follow(&t, 1, 11);
+	vclock_follow(&t, 2, 21);
+	vclock_follow(&t, 3, 30);
+
+	mclock_get(&mclock, 1, &v);
+	is(vclock_compare(&v, &t), 0, "second vclock");
+
+	vclock_follow(&v1, 1, 40);
+	vclock_follow(&v1, 4, 10);
+	mclock_update(&mclock, 1, &v1);
+	is(mclock_check(&mclock), true, "consistency 2");
+	vclock_follow(&v2, 2, 35);
+	vclock_follow(&v2, 4, 3);
+	mclock_update(&mclock, 2, &v2);
+	is(mclock_check(&mclock), true, "consistency 3");
+
+	vclock_create(&t);
+	vclock_follow(&t, 1, 40);
+	vclock_follow(&t, 2, 35);
+	vclock_follow(&t, 3, 31);
+	vclock_follow(&t, 4, 10);
+
+	mclock_get(&mclock, 0, &v);
+	is(vclock_compare(&v, &t), 0, "first vclock - 2");
+
+	vclock_create(&t);
+	vclock_follow(&t, 2, 21);
+	vclock_follow(&t, 3, 2);
+	vclock_follow(&t, 4, 3);
+
+	mclock_get(&mclock, -1, &v);
+	is(vclock_compare(&v, &t), 0, "last vclock - 2");
+
+	footer();
+	check_plan();
+
+}
+
+int main(void)
+{
+	plan(2);
+	test_random_stress();
+	test_func();
+	check_plan();
+}
+
-- 
2.21.1 (Apple Git-122.3)