SERVER-27745: Implement LogicalClock

8 files changed, 374 insertions, 0 deletions

diff --git a/src/mongo/db/SConscript b/src/mongo/db/SConscript
index 4cf0a47af5b..54fbb66b0d9 100644
--- a/src/mongo/db/SConscript
+++ b/src/mongo/db/SConscript
@@ -957,6 +957,16 @@ env.Library(
     ],
 )
 
+env.Library(
+    target='logical_clock',
+    source=[
+        'logical_clock.cpp',
+    ],
+    LIBDEPS=[
+        'signed_logical_time',
+    ],
+)
+
 env.CppUnitTest(
     target='logical_time_test',
     source=[
@@ -968,6 +978,18 @@ env.CppUnitTest(
     ],
 )
 
+env.CppUnitTest(
+    target='logical_clock_test',
+    source=[
+        'logical_clock_test.cpp',
+    ],
+    LIBDEPS=[
+        'service_context',
+        'logical_clock',
+        'signed_logical_time',
+    ],
+)
+
 env.Library(
     target= 'op_observer_noop',
     source= [
diff --git a/src/mongo/db/logical_clock.cpp b/src/mongo/db/logical_clock.cpp
new file mode 100644
index 00000000000..c712941dee5
--- /dev/null
+++ b/src/mongo/db/logical_clock.cpp
@@ -0,0 +1,118 @@
+/**
+ *    Copyright (C) 2017 MongoDB, Inc.
+ *
+ *    This program is free software: you can redistribute it and/or  modify
+ *    it under the terms of the GNU Affero General Public License, version 3,
+ *    as published by the Free Software Foundation.
+ *
+ *    This program is distributed in the hope that it will be useful,
+ *    but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *    GNU Affero General Public License for more details.
+ *
+ *    You should have received a copy of the GNU Affero General Public License
+ *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ *    As a special exception, the copyright holders give permission to link the
+ *    code of portions of this program with the OpenSSL library under certain
+ *    conditions as described in each individual source file and distribute
+ *    linked combinations including the program with the OpenSSL library. You
+ *    must comply with the GNU Affero General Public License in all respects for
+ *    all of the code used other than as permitted herein. If you modify file(s)
+ *    with this exception, you may extend this exception to your version of the
+ *    file(s), but you are not obligated to do so. If you do not wish to do so,
+ *    delete this exception statement from your version. If you delete this
+ *    exception statement from all source files in the program, then also delete
+ *    it in the license file.
+ */
+
+#include "mongo/db/logical_clock.h"
+
+#include "mongo/base/status.h"
+#include "mongo/db/operation_context.h"
+#include "mongo/db/service_context.h"
+#include "mongo/db/time_proof_service.h"
+#include "mongo/platform/basic.h"
+
+namespace mongo {
+
+namespace {
+const auto getLogicalClock = ServiceContext::declareDecoration<std::unique_ptr<LogicalClock>>();
+}
+
+LogicalClock* LogicalClock::get(ServiceContext* service) {
+    return getLogicalClock(service).get();
+}
+
+LogicalClock* LogicalClock::get(OperationContext* ctx) {
+    return get(ctx->getClient()->getServiceContext());
+}
+
+void LogicalClock::set(ServiceContext* service, std::unique_ptr<LogicalClock> clockArg) {
+    auto& clock = getLogicalClock(service);
+    clock = std::move(clockArg);
+}
+
+LogicalClock::LogicalClock(ServiceContext* serviceContext,
+                           std::unique_ptr<TimeProofService> tps,
+                           bool validateProof)
+    : _serviceContext(serviceContext),
+      _timeProofService(std::move(tps)),
+      _validateProof(validateProof) {}
+
+SignedLogicalTime LogicalClock::getClusterTime() {
+    stdx::lock_guard<stdx::mutex> lock(_mutex);
+    return _clusterTime;
+}
+
+SignedLogicalTime LogicalClock::_makeSignedLogicalTime(LogicalTime logicalTime) {
+    return SignedLogicalTime(logicalTime, _timeProofService->getProof(logicalTime));
+}
+
+Status LogicalClock::advanceClusterTime(const SignedLogicalTime& newTime) {
+    if (_validateProof) {
+        invariant(_timeProofService);
+        auto res = _timeProofService->checkProof(newTime.getTime(), newTime.getProof());
+        if (res != Status::OK()) {
+            return res;
+        }
+    }
+
+    stdx::lock_guard<stdx::mutex> lock(_mutex);
+    // TODO: rate check per SERVER-27721
+    if (newTime.getTime() > _clusterTime.getTime()) {
+        _clusterTime = newTime;
+    }
+
+    return Status::OK();
+}
+
+LogicalTime LogicalClock::reserveTicks(uint64_t ticks) {
+
+    invariant(ticks > 0);
+
+    stdx::lock_guard<stdx::mutex> lock(_mutex);
+
+    const unsigned wallClockSecs =
+        durationCount<Seconds>(_serviceContext->getFastClockSource()->now().toDurationSinceEpoch());
+    unsigned currentSecs = _clusterTime.getTime().asTimestamp().getSecs();
+    LogicalTime clusterTimestamp = _clusterTime.getTime();
+
+    if (MONGO_unlikely(currentSecs < wallClockSecs)) {
+        clusterTimestamp = LogicalTime(Timestamp(wallClockSecs, 1));
+    } else {
+        clusterTimestamp.addTicks(1);
+    }
+    auto currentTime = clusterTimestamp;
+    clusterTimestamp.addTicks(ticks - 1);
+
+    _clusterTime = _makeSignedLogicalTime(clusterTimestamp);
+    return currentTime;
+}
+
+void LogicalClock::initClusterTimeFromTrustedSource(LogicalTime newTime) {
+    invariant(_clusterTime.getTime() == LogicalTime::kUninitialized);
+    _clusterTime = _makeSignedLogicalTime(newTime);
+}
+
+}  // namespace mongo
diff --git a/src/mongo/db/logical_clock.h b/src/mongo/db/logical_clock.h
new file mode 100644
index 00000000000..3119b75f225
--- /dev/null
+++ b/src/mongo/db/logical_clock.h
@@ -0,0 +1,100 @@
+/**
+ *    Copyright (C) 2017 MongoDB, Inc.
+ *
+ *    This program is free software: you can redistribute it and/or  modify
+ *    it under the terms of the GNU Affero General Public License, version 3,
+ *    as published by the Free Software Foundation.
+ *
+ *    This program is distributed in the hope that it will be useful,
+ *    but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *    GNU Affero General Public License for more details.
+ *
+ *    You should have received a copy of the GNU Affero General Public License
+ *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ *    As a special exception, the copyright holders give permission to link the
+ *    code of portions of this program with the OpenSSL library under certain
+ *    conditions as described in each individual source file and distribute
+ *    linked combinations including the program with the OpenSSL library. You
+ *    must comply with the GNU Affero General Public License in all respects for
+ *    all of the code used other than as permitted herein. If you modify file(s)
+ *    with this exception, you may extend this exception to your version of the
+ *    file(s), but you are not obligated to do so. If you do not wish to do so,
+ *    delete this exception statement from your version. If you delete this
+ *    exception statement from all source files in the program, then also delete
+ *    it in the license file.
+ */
+
+#pragma once
+
+#include "mongo/db/signed_logical_time.h"
+#include "mongo/stdx/mutex.h"
+
+namespace mongo {
+class TimeProofService;
+class ServiceContext;
+class OperationContext;
+
+/**
+ * LogicalClock maintain the clusterTime for a clusterNode. Every cluster node in a replica set has
+ * an instance of the LogicalClock installed as a ServiceContext decoration. LogicalClock owns the
+ * TimeProofService that allows it to generate proofs to sign LogicalTime values and to validate the
+ * proofs of SignedLogicalTime values.LogicalClock instance must be created before the instance
+ * starts up.
+ */
+class LogicalClock {
+public:
+    // Decorate ServiceContext with LogicalClock instance.
+    static LogicalClock* get(ServiceContext* service);
+    static LogicalClock* get(OperationContext* ctx);
+    static void set(ServiceContext* service, std::unique_ptr<LogicalClock> logicalClock);
+
+    /**
+     *  Creates an instance of LogicalClock. The TimeProofService must already be fully initialized.
+     *  The validateProof indicates if the advanceClusterTime validates newTime. It should do so
+     *  only when LogicalClock installed on mongos and the auth is off.
+     */
+    LogicalClock(ServiceContext*, std::unique_ptr<TimeProofService>, bool validateProof);
+
+    /**
+     * The method sets clusterTime to the newTime if the newTime > _clusterTime and the newTime
+     * passes the rate check and proof validation.
+     * Returns an error if the newTime does not pass the rate check or proof validation,
+     * OK otherwise.
+     */
+    Status advanceClusterTime(const SignedLogicalTime& newTime);
+
+    /**
+     * Returns the current clusterTime.
+     */
+    SignedLogicalTime getClusterTime();
+
+    /**
+     * Returns the next  clusterTime value and provides the guarantee that the next reserveTicks
+     * call will return the value at least nTicks ticks in the future from the current clusterTime.
+     */
+    LogicalTime reserveTicks(uint64_t nTicks = 1);
+
+    /**
+     * Resets _clusterTime to the signed time created from newTime. Should be used at the
+     * initialization after reading the oplog. Must not be called on already initialized clock.
+     */
+    void initClusterTimeFromTrustedSource(LogicalTime newTime);
+
+private:
+    /**
+     * Utility to create valid SignedLogicalTime from LogicalTime.
+     */
+    SignedLogicalTime _makeSignedLogicalTime(LogicalTime);
+
+    ServiceContext* _serviceContext;
+    std::unique_ptr<TimeProofService> _timeProofService;
+
+    // the mutex protects _clusterTime
+    stdx::mutex _mutex;
+    SignedLogicalTime _clusterTime;
+    const bool _validateProof;
+};
+
+}  // namespace mongo
diff --git a/src/mongo/db/logical_clock_test.cpp b/src/mongo/db/logical_clock_test.cpp
new file mode 100644
index 00000000000..cba0cc1faa6
--- /dev/null
+++ b/src/mongo/db/logical_clock_test.cpp
@@ -0,0 +1,118 @@
+/**
+ *    Copyright (C) 2017 MongoDB, Inc.
+ *
+ *    This program is free software: you can redistribute it and/or  modify
+ *    it under the terms of the GNU Affero General Public License, version 3,
+ *    as published by the Free Software Foundation.
+ *
+ *    This program is distributed in the hope that it will be useful,
+ *    but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *    GNU Affero General Public License for more details.
+ *
+ *    You should have received a copy of the GNU Affero General Public License
+ *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ *    As a special exception, the copyright holders give permission to link the
+ *    code of portions of this program with the OpenSSL library under certain
+ *    conditions as described in each individual source file and distribute
+ *    linked combinations including the program with the OpenSSL library. You
+ *    must comply with the GNU Affero General Public License in all respects for
+ *    all of the code used other than as permitted herein. If you modify file(s)
+ *    with this exception, you may extend this exception to your version of the
+ *    file(s), but you are not obligated to do so. If you do not wish to do so,
+ *    delete this exception statement from your version. If you delete this
+ *    exception statement from all source files in the program, then also delete
+ *    it in the license file.
+ */
+
+#include "mongo/db/logical_clock.h"
+#include "mongo/bson/timestamp.h"
+#include "mongo/db/logical_time.h"
+#include "mongo/db/service_context_noop.h"
+#include "mongo/db/signed_logical_time.h"
+#include "mongo/db/time_proof_service.h"
+#include "mongo/platform/basic.h"
+#include "mongo/stdx/memory.h"
+#include "mongo/unittest/unittest.h"
+
+namespace mongo {
+namespace {
+
+/**
+ * Setup LogicalClock with invalid initial time.
+ */
+class LogicalClockTestBase : public unittest::Test {
+protected:
+    void setUp() {
+        _serviceContext = stdx::make_unique<ServiceContextNoop>();
+        auto pTps = stdx::make_unique<TimeProofService>();
+        _timeProofService = pTps.get();
+        _clock = stdx::make_unique<LogicalClock>(_serviceContext.get(), std::move(pTps), true);
+    }
+
+    void tearDown() {
+        _clock.reset();
+        _serviceContext.reset();
+    }
+
+    LogicalClock* getClock() {
+        return _clock.get();
+    }
+
+    SignedLogicalTime makeSignedLogicalTime(LogicalTime logicalTime) {
+        return SignedLogicalTime(logicalTime, _timeProofService->getProof(logicalTime));
+    }
+
+private:
+    TimeProofService* _timeProofService;
+    std::unique_ptr<ServiceContextNoop> _serviceContext;
+    std::unique_ptr<LogicalClock> _clock;
+};
+
+// Check that the initial time does not change during logicalClock creation.
+TEST_F(LogicalClockTestBase, roundtrip) {
+    // Create different logicalClock instance to validate that the initial time is preserved.
+    ServiceContextNoop serviceContext;
+    Timestamp tX(1);
+    auto pTps = stdx::make_unique<TimeProofService>();
+    auto time = LogicalTime(tX);
+
+    LogicalClock logicalClock(&serviceContext, std::move(pTps), true);
+    logicalClock.initClusterTimeFromTrustedSource(time);
+    auto storedTime(std::move(logicalClock.getClusterTime()));
+
+    ASSERT_TRUE(storedTime.getTime() == time);
+}
+
+// Verify the reserve ticks functionality.
+TEST_F(LogicalClockTestBase, reserveTicks) {
+    auto t1 = getClock()->reserveTicks(1);
+    auto t2(std::move(getClock()->getClusterTime()));
+    ASSERT_TRUE(t1 == t2.getTime());
+
+    auto t3 = getClock()->reserveTicks(1);
+    t1.addTicks(1);
+    ASSERT_TRUE(t3 == t1);
+
+    t3 = getClock()->reserveTicks(100);
+    t1.addTicks(1);
+    ASSERT_TRUE(t3 == t1);
+
+    t3 = getClock()->reserveTicks(1);
+    t1.addTicks(100);
+    ASSERT_TRUE(t3 == t1);
+}
+
+// Verify the advanceClusterTime functionality.
+TEST_F(LogicalClockTestBase, advanceClusterTime) {
+    auto t1 = getClock()->reserveTicks(1);
+    t1.addTicks(100);
+    SignedLogicalTime l1 = makeSignedLogicalTime(t1);
+    ASSERT_OK(getClock()->advanceClusterTime(l1));
+    auto l2(std::move(getClock()->getClusterTime()));
+    ASSERT_TRUE(l1.getTime() == l2.getTime());
+}
+
+}  // unnamed namespace
+}  // namespace mongo
diff --git a/src/mongo/db/logical_time.cpp b/src/mongo/db/logical_time.cpp
index 9d36a17a234..e9e5b4c5b34 100644
--- a/src/mongo/db/logical_time.cpp
+++ b/src/mongo/db/logical_time.cpp
@@ -33,6 +33,8 @@
 
 namespace mongo {
 
+const LogicalTime LogicalTime::kUninitialized = LogicalTime();
+
 LogicalTime::LogicalTime(Timestamp ts) : _time(ts.asULL()) {}
 
 void LogicalTime::addTicks(uint64_t ticks) {
diff --git a/src/mongo/db/logical_time.h b/src/mongo/db/logical_time.h
index 6d3fb74a99b..2bc43bf54d4 100644
--- a/src/mongo/db/logical_time.h
+++ b/src/mongo/db/logical_time.h
@@ -38,6 +38,7 @@ namespace mongo {
  */
 class LogicalTime {
 public:
+    LogicalTime() = default;
     explicit LogicalTime(Timestamp);
 
     Timestamp asTimestamp() const {
@@ -57,6 +58,11 @@ public:
 
     std::string toString() const;
 
+    /**
+     * An uninitialized value of LogicalTime. Default constructed.
+     */
+    static const LogicalTime kUninitialized;
+
 private:
     uint64_t _time{0};
 };
diff --git a/src/mongo/db/logical_time_test.cpp b/src/mongo/db/logical_time_test.cpp
index dbff22f8ce3..d5d1f15a7b2 100644
--- a/src/mongo/db/logical_time_test.cpp
+++ b/src/mongo/db/logical_time_test.cpp
@@ -86,6 +86,12 @@ TEST(LogicalTime, addTicksConst) {
     ASSERT_TRUE(tY == lQ.asTimestamp());
 }
 
+TEST(LogicalTime, defaultInit) {
+    Timestamp tX(0);
+    LogicalTime lT;
+    ASSERT_TRUE(tX == lT.asTimestamp());
+}
+
 TEST(SignedLogicalTime, roundtrip) {
     Timestamp tX(1);
     TimeProofService tps;
diff --git a/src/mongo/db/signed_logical_time.h b/src/mongo/db/signed_logical_time.h
index 12c8d373d49..52cf1230e58 100644
--- a/src/mongo/db/signed_logical_time.h
+++ b/src/mongo/db/signed_logical_time.h
@@ -42,6 +42,8 @@ class SignedLogicalTime {
 public:
     using TimeProof = TimeProofService::TimeProof;
 
+    SignedLogicalTime() = default;
+
     explicit SignedLogicalTime(LogicalTime time, TimeProof proof)
         : _time(std::move(time)), _proof(std::move(proof)) {}