[PATCH v2 07/10] Introduce checkpoint schedule module

[Vladimir Davydov <vdavydov.dev@gmail.com>]

This is a very simple module that incorporates the logic for calculating
the time of the next scheduled checkpoint given the configured interval
between checkpoints. It doesn't have any dependencies, which allows to
cover it with a unit test. It will be used by the checkpoint daemon once
we rewrite it in C. Rationale: in future we might want to introduce more
complex rules for scheduling checkpoints (cron-like may be) and it will
be really nice to have this logic neatly separated and tested.
---
 src/box/CMakeLists.txt               |  1 +
 src/box/checkpoint_schedule.c        | 76 ++++++++++++++++++++++++++++
 src/box/checkpoint_schedule.h        | 85 +++++++++++++++++++++++++++++++
 test/unit/CMakeLists.txt             |  6 +++
 test/unit/checkpoint_schedule.c      | 96 ++++++++++++++++++++++++++++++++++++
 test/unit/checkpoint_schedule.result | 41 +++++++++++++++
 6 files changed, 305 insertions(+)
 create mode 100644 src/box/checkpoint_schedule.c
 create mode 100644 src/box/checkpoint_schedule.h
 create mode 100644 test/unit/checkpoint_schedule.c
 create mode 100644 test/unit/checkpoint_schedule.result

diff --git a/src/box/CMakeLists.txt b/src/box/CMakeLists.txt
index d1276472..d7a52c5e 100644
--- a/src/box/CMakeLists.txt
+++ b/src/box/CMakeLists.txt
@@ -106,6 +106,7 @@ add_library(box STATIC
     txn.c
     box.cc
     gc.c
+    checkpoint_schedule.c
     user_def.c
     user.cc
     authentication.cc
diff --git a/src/box/checkpoint_schedule.c b/src/box/checkpoint_schedule.c
new file mode 100644
index 00000000..d37eba7f
--- /dev/null
+++ b/src/box/checkpoint_schedule.c
@@ -0,0 +1,76 @@
+/*
+ * Copyright 2010-2018, 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 AUTHORS ``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
+ * AUTHORS 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 "checkpoint_schedule.h"
+
+#include <assert.h>
+#include <math.h>
+#include <stdlib.h>
+
+void
+checkpoint_schedule_cfg(struct checkpoint_schedule *sched,
+			double now, double interval)
+{
+	sched->interval = interval;
+	sched->start_time = now + interval;
+
+	/*
+	 * Add a random offset to the start time so as to avoid
+	 * simultaneous checkpointing when multiple instances
+	 * are running on the same host.
+	 */
+	if (interval > 0)
+		sched->start_time += fmod(rand(), interval);
+}
+
+void
+checkpoint_schedule_reset(struct checkpoint_schedule *sched, double now)
+{
+	sched->start_time = now + sched->interval;
+}
+
+double
+checkpoint_schedule_timeout(struct checkpoint_schedule *sched, double now)
+{
+	if (sched->interval <= 0)
+		return 0; /* checkpointing disabled */
+
+	if (now < sched->start_time)
+		return sched->start_time - now;
+
+	/* Time elapsed since the last checkpoint. */
+	double elapsed = fmod(now - sched->start_time, sched->interval);
+
+	/* Time left to the next checkpoint. */
+	double timeout = sched->interval - elapsed;
+
+	assert(timeout > 0);
+	return timeout;
+}
diff --git a/src/box/checkpoint_schedule.h b/src/box/checkpoint_schedule.h
new file mode 100644
index 00000000..7fbbfe2f
--- /dev/null
+++ b/src/box/checkpoint_schedule.h
@@ -0,0 +1,85 @@
+#ifndef TARANTOOL_BOX_CHECKPOINT_SCHEDULE_H_INCLUDED
+#define TARANTOOL_BOX_CHECKPOINT_SCHEDULE_H_INCLUDED
+/*
+ * Copyright 2010-2018, 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 AUTHORS ``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
+ * AUTHORS 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.
+ */
+
+#if defined(__cplusplus)
+extern "C" {
+#endif /* defined(__cplusplus) */
+
+struct checkpoint_schedule {
+	/**
+	 * Configured interval between checkpoints, in seconds.
+	 * Set to 0 if periodic checkpointing is disabled.
+	 */
+	double interval;
+	/**
+	 * Time of the first scheduled checkpoint. It is used
+	 * for calculating times of all subsequent checkpoints.
+	 */
+	double start_time;
+};
+
+/**
+ * (Re)configure a checkpoint schedule.
+ *
+ * @now is the current time.
+ * @interval is the configured interval between checkpoints.
+ */
+void
+checkpoint_schedule_cfg(struct checkpoint_schedule *sched,
+			double now, double interval);
+
+/**
+ * Reset a checkpoint schedule.
+ *
+ * Called when a checkpoint is triggered out of the schedule.
+ * Used to adjusts the schedule accordingly.
+ *
+ * @now is the current time.
+ */
+void
+checkpoint_schedule_reset(struct checkpoint_schedule *sched, double now);
+
+/**
+ * Return the time to the next scheduled checkpoint, in seconds.
+ * If auto checkpointing is disabled, returns 0.
+ *
+ * @now is the current time.
+ */
+double
+checkpoint_schedule_timeout(struct checkpoint_schedule *sched, double now);
+
+#if defined(__cplusplus)
+} /* extern "C" */
+#endif /* defined(__cplusplus) */
+
+#endif /* TARANTOOL_BOX_CHECKPOINT_SCHEDULE_H_INCLUDED */
diff --git a/test/unit/CMakeLists.txt b/test/unit/CMakeLists.txt
index aef53160..aac86f9e 100644
--- a/test/unit/CMakeLists.txt
+++ b/test/unit/CMakeLists.txt
@@ -195,3 +195,9 @@ target_link_libraries(coll.test core unit ${ICU_LIBRARIES} misc)
 
 add_executable(tuple_bigref.test tuple_bigref.c)
 target_link_libraries(tuple_bigref.test tuple unit)
+
+add_executable(checkpoint_schedule.test
+    checkpoint_schedule.c
+    ${PROJECT_SOURCE_DIR}/src/box/checkpoint_schedule.c
+)
+target_link_libraries(checkpoint_schedule.test m unit)
diff --git a/test/unit/checkpoint_schedule.c b/test/unit/checkpoint_schedule.c
new file mode 100644
index 00000000..025c73b1
--- /dev/null
+++ b/test/unit/checkpoint_schedule.c
@@ -0,0 +1,96 @@
+#include <math.h>
+#include <stdbool.h>
+#include <stddef.h>
+#include <stdlib.h>
+#include <time.h>
+
+#include "unit.h"
+#include "checkpoint_schedule.h"
+
+static inline bool
+feq(double a, double b)
+{
+	return fabs(a - b) <= 1;
+}
+
+int
+main()
+{
+	header();
+	plan(38);
+
+	srand(time(NULL));
+	double now = rand();
+
+	struct checkpoint_schedule sched;
+	checkpoint_schedule_cfg(&sched, now, 0);
+
+	is(checkpoint_schedule_timeout(&sched, now), 0,
+	   "checkpointing disabled - timeout after configuration");
+
+	now += rand();
+	is(checkpoint_schedule_timeout(&sched, now), 0,
+	   "checkpointing disabled - timeout after sleep");
+
+	checkpoint_schedule_reset(&sched, now);
+	is(checkpoint_schedule_timeout(&sched, now), 0,
+	   "checkpointing disabled - timeout after reset");
+
+	double intervals[] = { 100, 600, 1200, 1800, 3600, };
+	int intervals_len = sizeof(intervals) / sizeof(intervals[0]);
+	for (int i = 0; i < intervals_len; i++) {
+		double interval = intervals[i];
+
+		checkpoint_schedule_cfg(&sched, now, interval);
+		double t = checkpoint_schedule_timeout(&sched, now);
+		ok(t >= interval && t <= interval * 2,
+		   "checkpoint interval %.0lf - timeout after configuration",
+		   interval);
+
+		double t0;
+		for (int j = 0; j < 100; j++) {
+			checkpoint_schedule_cfg(&sched, now, interval);
+			t0 = checkpoint_schedule_timeout(&sched, now);
+			if (fabs(t - t0) > interval / 4)
+				break;
+		}
+		ok(fabs(t - t0) > interval / 4,
+		   "checkpoint interval %.0lf - initial timeout randomization",
+		   interval);
+
+		now += t0 / 2;
+		t = checkpoint_schedule_timeout(&sched, now);
+		ok(feq(t, t0 / 2),
+		   "checkpoint interval %.0lf - timeout after sleep 1",
+		   interval);
+
+		now += t0 / 2;
+		t = checkpoint_schedule_timeout(&sched, now);
+		ok(feq(t, interval),
+		   "checkpoint interval %.0lf - timeout after sleep 2",
+		   interval);
+
+		now += interval / 2;
+		t = checkpoint_schedule_timeout(&sched, now);
+		ok(feq(t, interval / 2),
+		   "checkpoint interval %.0lf - timeout after sleep 3",
+		   interval);
+
+		now += interval;
+		t = checkpoint_schedule_timeout(&sched, now);
+		ok(feq(t, interval / 2),
+		   "checkpoint interval %.0lf - timeout after sleep 4",
+		   interval);
+
+		checkpoint_schedule_reset(&sched, now);
+		t = checkpoint_schedule_timeout(&sched, now);
+		ok(feq(t, interval),
+		   "checkpoint interval %.0lf - timeout after reset",
+		   interval);
+	}
+
+	check_plan();
+	footer();
+
+	return 0;
+}
diff --git a/test/unit/checkpoint_schedule.result b/test/unit/checkpoint_schedule.result
new file mode 100644
index 00000000..e34c762a
--- /dev/null
+++ b/test/unit/checkpoint_schedule.result
@@ -0,0 +1,41 @@
+	*** main ***
+1..38
+ok 1 - checkpointing disabled - timeout after configuration
+ok 2 - checkpointing disabled - timeout after sleep
+ok 3 - checkpointing disabled - timeout after reset
+ok 4 - checkpoint interval 100 - timeout after configuration
+ok 5 - checkpoint interval 100 - initial timeout randomization
+ok 6 - checkpoint interval 100 - timeout after sleep 1
+ok 7 - checkpoint interval 100 - timeout after sleep 2
+ok 8 - checkpoint interval 100 - timeout after sleep 3
+ok 9 - checkpoint interval 100 - timeout after sleep 4
+ok 10 - checkpoint interval 100 - timeout after reset
+ok 11 - checkpoint interval 600 - timeout after configuration
+ok 12 - checkpoint interval 600 - initial timeout randomization
+ok 13 - checkpoint interval 600 - timeout after sleep 1
+ok 14 - checkpoint interval 600 - timeout after sleep 2
+ok 15 - checkpoint interval 600 - timeout after sleep 3
+ok 16 - checkpoint interval 600 - timeout after sleep 4
+ok 17 - checkpoint interval 600 - timeout after reset
+ok 18 - checkpoint interval 1200 - timeout after configuration
+ok 19 - checkpoint interval 1200 - initial timeout randomization
+ok 20 - checkpoint interval 1200 - timeout after sleep 1
+ok 21 - checkpoint interval 1200 - timeout after sleep 2
+ok 22 - checkpoint interval 1200 - timeout after sleep 3
+ok 23 - checkpoint interval 1200 - timeout after sleep 4
+ok 24 - checkpoint interval 1200 - timeout after reset
+ok 25 - checkpoint interval 1800 - timeout after configuration
+ok 26 - checkpoint interval 1800 - initial timeout randomization
+ok 27 - checkpoint interval 1800 - timeout after sleep 1
+ok 28 - checkpoint interval 1800 - timeout after sleep 2
+ok 29 - checkpoint interval 1800 - timeout after sleep 3
+ok 30 - checkpoint interval 1800 - timeout after sleep 4
+ok 31 - checkpoint interval 1800 - timeout after reset
+ok 32 - checkpoint interval 3600 - timeout after configuration
+ok 33 - checkpoint interval 3600 - initial timeout randomization
+ok 34 - checkpoint interval 3600 - timeout after sleep 1
+ok 35 - checkpoint interval 3600 - timeout after sleep 2
+ok 36 - checkpoint interval 3600 - timeout after sleep 3
+ok 37 - checkpoint interval 3600 - timeout after sleep 4
+ok 38 - checkpoint interval 3600 - timeout after reset
+	*** main: done ***
-- 
2.11.0