Tarantool development patches archive
 help / color / mirror / Atom feed
From: Vladimir Davydov <vdavydov.dev@gmail.com>
To: kostja@tarantool.org
Cc: tarantool-patches@freelists.org
Subject: [PATCH v2 07/10] Introduce checkpoint schedule module
Date: Sat,  8 Dec 2018 18:48:11 +0300	[thread overview]
Message-ID: <10b6f097fbeb46c0d66bb35efc49b411dc7573de.1544282224.git.vdavydov.dev@gmail.com> (raw)
In-Reply-To: <cover.1544282224.git.vdavydov.dev@gmail.com>
In-Reply-To: <cover.1544282224.git.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

  parent reply	other threads:[~2018-12-08 15:48 UTC|newest]

Thread overview: 22+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-12-08 15:48 [PATCH v2 00/10] Allow to limit size of WAL files Vladimir Davydov
2018-12-08 15:48 ` [PATCH v2 01/10] gc: do not use WAL watcher API for deactivating stale consumers Vladimir Davydov
2018-12-08 21:41   ` Konstantin Osipov
2018-12-08 15:48 ` [PATCH v2 02/10] wal: simplify watcher API Vladimir Davydov
2018-12-08 21:41   ` Konstantin Osipov
2018-12-08 15:48 ` [PATCH v2 03/10] box: fix certain cfg options initialized twice on recovery Vladimir Davydov
2018-12-08 21:42   ` Konstantin Osipov
2018-12-08 15:48 ` [PATCH v2 04/10] box: don't use box_checkpoint_is_in_progress outside box.cc Vladimir Davydov
2018-12-08 21:43   ` Konstantin Osipov
2018-12-08 15:48 ` [PATCH v2 05/10] box: move checkpointing to gc module Vladimir Davydov
2018-12-08 21:44   ` Konstantin Osipov
2018-12-08 15:48 ` [PATCH v2 06/10] gc: some renames Vladimir Davydov
2018-12-08 21:44   ` Konstantin Osipov
2018-12-08 15:48 ` Vladimir Davydov [this message]
2018-12-08 21:45   ` [PATCH v2 07/10] Introduce checkpoint schedule module Konstantin Osipov
2018-12-08 15:48 ` [PATCH v2 08/10] Rewrite checkpoint daemon in C Vladimir Davydov
2018-12-08 21:45   ` Konstantin Osipov
2018-12-08 15:48 ` [PATCH v2 09/10] wal: pass struct instead of vclock to checkpoint methods Vladimir Davydov
2018-12-08 21:46   ` Konstantin Osipov
2018-12-08 15:48 ` [PATCH v2 10/10] wal: trigger checkpoint if there are too many WALs Vladimir Davydov
2018-12-08 21:48   ` Konstantin Osipov
2018-12-09 11:20 ` [PATCH v2 00/10] Allow to limit size of WAL files Vladimir Davydov

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=10b6f097fbeb46c0d66bb35efc49b411dc7573de.1544282224.git.vdavydov.dev@gmail.com \
    --to=vdavydov.dev@gmail.com \
    --cc=kostja@tarantool.org \
    --cc=tarantool-patches@freelists.org \
    --subject='Re: [PATCH v2 07/10] Introduce checkpoint schedule module' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox