MB-24151: Implement general range read iterator in seqlist 40/77640/10
authorManu Dhundi <manu@couchbase.com>
Wed, 10 May 2017 00:36:40 +0000 (17:36 -0700)
committerManu Dhundi <manu@couchbase.com>
Wed, 10 May 2017 18:23:06 +0000 (18:23 +0000)
This commit implements range read iterator in sequence list, the ordered
data strucuture in Ephemeral buckets.

We need range read iterators because we have more than one client that
needs to do a range read (backfill, tombstone purger). Further the reads
can also have more involved constraints like memory management in backfills.
By having an API of read iterator we can just do the read from the sequence
list and additional stuff like memory management can be done outside by the
clients. That is, iterator clients can make progress at their own pace.

The iterator is unidirectional (forward only) and cannot be invalidated
while in use. That means reading the items in the iterator results in a
valid point-in-time snapshot. But this adds a caveat that while an
iterator instance is active, certain invariants are to be met to get the
snapshot, and this happens at the expense of increased memory usage.

For now, only one iterator can be created at a time.

Change-Id: Idb320a148299255b74b7cf7e92cef35a20f483d4
Reviewed-on: http://review.couchbase.org/77640
Reviewed-by: Dave Rigby <daver@couchbase.com>
Tested-by: Build Bot <build@couchbase.com>
CMakeLists.txt
src/linked_list.cc
src/linked_list.h
src/seqlist.cc [new file with mode: 0644]
src/seqlist.h
tests/module_tests/basic_ll_test.cc

index ffcfe84..0510264 100644 (file)
@@ -203,6 +203,7 @@ ADD_LIBRARY(ep_objs OBJECT
             src/pre_link_document_context.h
             src/replicationthrottle.cc
             src/linked_list.cc
+            src/seqlist.cc
             src/string_utils.cc
             src/storeddockey.cc
             src/stored-value.cc
index 63b3a80..0e91a4f 100644 (file)
@@ -355,6 +355,11 @@ std::mutex& BasicLinkedList::getHighSeqnosLock() const {
     return highSeqnosLock;
 }
 
+SequenceList::RangeIterator BasicLinkedList::makeRangeIterator() {
+    return SequenceList::RangeIterator(
+            std::make_unique<RangeIteratorLL>(*this));
+}
+
 void BasicLinkedList::dump() const {
     std::cerr << *this << std::endl;
 }
@@ -398,3 +403,88 @@ OrderedLL::iterator BasicLinkedList::purgeListElem(OrderedLL::iterator it) {
     }
     return it;
 }
+
+BasicLinkedList::RangeIteratorLL::RangeIteratorLL(BasicLinkedList& ll)
+    : list(ll), readLockHolder(list.rangeReadLock), itrRange(0, 0) {
+    std::lock_guard<SpinLock> lh(list.rangeLock);
+    if (list.highSeqno < 1) {
+        /* No need of holding a lock for the snapshot as there are no items;
+           Also iterator range is at default (0, 0) */
+        readLockHolder.unlock();
+        return;
+    }
+
+    /* Iterator to the beginning of linked list */
+    currIt = list.seqList.begin();
+
+    /* Mark the snapshot range on linked list. The range that can be read by the
+       iterator is inclusive of the start and the end. */
+    list.readRange = SeqRange(currIt->getBySeqno(), list.highSeqno);
+
+    /* Keep the range in the iterator obj. We store the range end seqno as one
+       higher than the end seqno that can be read by this iterator.
+       This is because, we must identify the end point of the iterator, and
+       we the read is inclusive of the end points of list.readRange.
+
+       Further, since use the class 'SeqRange' for 'itrRange' we cannot use
+       curr() == end() + 1 to identify the end point because 'SeqRange' does
+       not internally allow curr > end */
+    itrRange = SeqRange(currIt->getBySeqno(), list.highSeqno + 1);
+}
+
+BasicLinkedList::RangeIteratorLL::~RangeIteratorLL() {
+    std::lock_guard<SpinLock> lh(list.rangeLock);
+    list.readRange.reset();
+    /* As readLockHolder goes out of scope here, it will automatically release
+       the snapshot read lock on the linked list */
+}
+
+OrderedStoredValue& BasicLinkedList::RangeIteratorLL::operator*() const {
+    if (curr() >= end()) {
+        /* We can't read beyond the range end */
+        throw std::out_of_range(
+                "BasicLinkedList::RangeIteratorLL::operator*()"
+                ": Trying to read beyond range end seqno " +
+                std::to_string(end()));
+    }
+    return *currIt;
+}
+
+BasicLinkedList::RangeIteratorLL& BasicLinkedList::RangeIteratorLL::
+operator++() {
+    if (curr() >= end()) {
+        throw std::out_of_range(
+                "BasicLinkedList::RangeIteratorLL::operator++()"
+                ": Trying to move the iterator beyond range end"
+                " seqno " +
+                std::to_string(end()));
+    }
+
+    /* Check if the iterator is pointing to the last element. Increment beyond
+       the last element indicates the end of the iteration */
+    if (curr() == itrRange.getEnd() - 1) {
+        std::lock_guard<SpinLock> lh(list.rangeLock);
+        /* Release snapshot read lock on the linked list */
+        list.readRange.reset();
+        readLockHolder.unlock();
+
+        /* Update the begin to end() so the client can see that the iteration
+           has ended */
+        itrRange.setBegin(end());
+        return *this;
+    }
+
+    ++currIt;
+    {
+        /* As the iterator moves we reduce the snapshot range being read on the
+           linked list. This helps reduce the stale items in the list during
+           heavy update load from the front end */
+        std::lock_guard<SpinLock> lh(list.rangeLock);
+        list.readRange.setBegin(currIt->getBySeqno());
+    }
+
+    /* Also update the current range stored in the iterator obj */
+    itrRange.setBegin(currIt->getBySeqno());
+
+    return *this;
+}
index 73d019b..b3e0ff4 100644 (file)
@@ -180,6 +180,8 @@ public:
 
     std::mutex& getHighSeqnosLock() const override;
 
+    SequenceList::RangeIterator makeRangeIterator() override;
+
     void dump() const override;
 
 protected:
@@ -288,6 +290,42 @@ private:
 
     friend std::ostream& operator<<(std::ostream& os,
                                     const BasicLinkedList& ll);
+
+    class RangeIteratorLL : public SequenceList::RangeIteratorImpl {
+    public:
+        RangeIteratorLL(BasicLinkedList& ll);
+
+        ~RangeIteratorLL();
+
+        OrderedStoredValue& operator*() const override;
+
+        RangeIteratorLL& operator++() override;
+
+        seqno_t curr() const override {
+            return itrRange.getBegin();
+        }
+
+        seqno_t end() const override {
+            return itrRange.getEnd();
+        }
+
+    private:
+        /* Ref to BasicLinkedList object which is iterated by this iterator.
+           By setting the member variables of the list obj appropriately we
+           ensure that iterator is not invalidated */
+        BasicLinkedList& list;
+
+        /* The current list element pointed by the iterator */
+        OrderedLL::iterator currIt;
+
+        /* Lock holder which allows having only one iterator at a time */
+        std::unique_lock<std::mutex> readLockHolder;
+
+        /* Current range of the iterator */
+        SeqRange itrRange;
+    };
+
+    friend class RangeIteratorLL;
 };
 
 /// Outputs a textual description of the BasicLinkedList
diff --git a/src/seqlist.cc b/src/seqlist.cc
new file mode 100644 (file)
index 0000000..02d2705
--- /dev/null
@@ -0,0 +1,41 @@
+/* -*- Mode: C++; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
+/*
+ *     Copyright 2017 Couchbase, Inc
+ *
+ *   Licensed under the Apache License, Version 2.0 (the "License");
+ *   you may not use this file except in compliance with the License.
+ *   You may obtain a copy of the License at
+ *
+ *       http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *   Unless required by applicable law or agreed to in writing, software
+ *   distributed under the License is distributed on an "AS IS" BASIS,
+ *   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *   See the License for the specific language governing permissions and
+ *   limitations under the License.
+ */
+
+#include <mutex>
+#include "linked_list.h"
+
+SequenceList::RangeIterator::RangeIterator(
+        std::unique_ptr<RangeIteratorImpl> rangeIterImpl)
+    : rangeIterImpl(std::move(rangeIterImpl)) {
+}
+
+OrderedStoredValue& SequenceList::RangeIterator::operator*() const {
+    return *(*rangeIterImpl);
+}
+
+SequenceList::RangeIterator& SequenceList::RangeIterator::operator++() {
+    ++(*rangeIterImpl);
+    return *this;
+}
+
+seqno_t SequenceList::RangeIterator::curr() {
+    return rangeIterImpl->curr();
+}
+
+seqno_t SequenceList::RangeIterator::end() {
+    return rangeIterImpl->end();
+}
index 96d5315..db2b7f8 100644 (file)
@@ -62,6 +62,50 @@ using seqno_t = int64_t;
  *              rangeRead and Clean Up
  */
 class SequenceList {
+protected:
+    /**
+     * Abstract base class for implementation of range iterators in derived
+     * classes of SequenceList.
+     *
+     * (a) The API is for unidirectional (forward only) iterator.
+     * (b) Iterator cannot be invalidated while in use.
+     * (c) Reading all the items from the iterator results in point-in-time
+     *     snapshot.
+     * (d) Only 1 iterator can be created for now.
+     * (e) Currently iterator can be created only from start till end
+     */
+    class RangeIteratorImpl {
+    public:
+        virtual ~RangeIteratorImpl() {
+        }
+
+        /**
+         * Returns the stored item at iterator's position
+         */
+        virtual OrderedStoredValue& operator*() const = 0;
+
+        /**
+         * Pre increment of the iterator position
+         *
+         * Note: We do not allow post increment for now as we support only
+         *       one iterator at a time. (hence, we don't create a temp copy
+         *       of the iterator obj)
+         */
+        virtual RangeIteratorImpl& operator++() = 0;
+
+        /**
+         * Curr iterator position, indicated by the seqno of the item at that
+         * position
+         */
+        virtual seqno_t curr() const = 0;
+
+        /**
+         * End position of iterator, indicated by the seqno > highest_seqno
+         * in the iterator range
+         */
+        virtual seqno_t end() const = 0;
+    };
+
 public:
     /**
      * Indicates whether the updateListElem is successful or the list is
@@ -70,6 +114,74 @@ public:
      */
     enum class UpdateStatus { Success, Append };
 
+    /**
+     * RangeIterator for a SequenceList objects.
+     *
+     * The iterator is unidirectional (forward only) and cannot be invalidated
+     * while in use. That means reading the items in the iterator results in a
+     * valid point-in-time snapshot. But this adds a caveat that while an
+     * iterator instance is active, certain invariants are to be met to get the
+     * snapshot, and this happens at the expense of increased memory usage.
+     *
+     * Implementation follows the pimpl idiom. This class serves as a wrapper
+     * for the abstract base class that defines the APIs for range iteration on
+     * the derived concrete classes of the SequenceList. It calls the range
+     * iterators of the concrete classes polymorphically at runtime. However
+     * clients get this statically typed "RangeIterator" object when they
+     * request for an iterator for a SequenceList object.
+     *
+     * Usage:
+     * 1. Create an iterator instance using SequenceList::makeRangeIterator()
+     * 2. Iterate (read) through all the list elements.
+     * 3. Delete the iterator.
+     * Note: (a) Do not hold the iterator for long, as it will result in stale
+     *           items in list and hence increased memory usage.
+     *       (b) Make sure to delete the iterator after using it.
+     *       (c) For now, we allow on one RangeIterator. Try to create more
+     *           iterators will result in the create call(s) being blocked.
+     */
+    class RangeIterator {
+    public:
+        RangeIterator(std::unique_ptr<RangeIteratorImpl> rangeIterImpl);
+
+        /* Needed for MSVC.
+           MSVC does not do "return value optimization" if copy constructor is
+           defined before move constructor
+           (http://stackoverflow.com/questions/29459040)
+         */
+        RangeIterator(RangeIterator&& other)
+            : rangeIterImpl(std::move(other.rangeIterImpl)) {
+        }
+
+        RangeIterator(RangeIterator& other) = delete;
+
+        /**
+         * Returns the stored item at iterator's position
+         */
+        OrderedStoredValue& operator*() const;
+
+        /**
+         * Pre increment of the iterator position
+         */
+        RangeIterator& operator++();
+
+        /**
+         * Curr iterator position, indicated by the seqno of the item at that
+         * position
+         */
+        seqno_t curr();
+
+        /**
+         * Curr iterator position, indicated by the seqno of the item at that
+         * position
+         */
+        seqno_t end();
+
+    private:
+        /* Pointer to the abstract class of range iterator implementation */
+        std::unique_ptr<RangeIteratorImpl> rangeIterImpl;
+    };
+
     virtual ~SequenceList() {
     }
 
@@ -238,6 +350,11 @@ public:
     virtual std::mutex& getHighSeqnosLock() const = 0;
 
     /**
+     * Returns a range iterator for the underlying SequenceList obj
+     */
+    virtual SequenceList::RangeIterator makeRangeIterator() = 0;
+
+    /**
      * Debug - prints a representation of the list to stderr.
      */
     virtual void dump() const = 0;
index 0fbabcc..3934a2b 100644 (file)
@@ -120,6 +120,8 @@ protected:
      * To be called when there is range read.
      */
     void updateItemDuringRangeRead(seqno_t highSeqno, const std::string& key) {
+        const std::string val("data");
+
         /* Get a fake sequence lock */
         std::mutex fakeSeqLock;
         std::lock_guard<std::mutex> lg(fakeSeqLock);
@@ -131,6 +133,28 @@ protected:
 
         EXPECT_EQ(SequenceList::UpdateStatus::Append,
                   basicLL->updateListElem(lg, *osv));
+
+        /* Release the current sv from the HT */
+        StoredDocKey sKey = makeStoredDocKey(key);
+        auto hbl = ht.getLockedBucket(sKey);
+        auto ownedSv = ht.unlocked_release(hbl, osv->getKey());
+        basicLL->markItemStale(std::move(ownedSv));
+
+        /* Add a new storedvalue for the append */
+        Item itm(sKey,
+                 0,
+                 0,
+                 val.data(),
+                 val.length(),
+                 /*ext_meta*/ nullptr,
+                 /*ext_len*/ 0,
+                 /*theCas*/ 0,
+                 /*bySeqno*/ highSeqno + 1);
+        auto newSv = ht.unlocked_addNewStoredValue(hbl, itm);
+
+        basicLL->appendToList(lg, *(newSv->toOrderedStoredValue()));
+        std::lock_guard<std::mutex> highSeqnoLh(basicLL->getHighSeqnosLock());
+        basicLL->updateHighSeqno(highSeqnoLh, *(newSv->toOrderedStoredValue()));
     }
 
     /**
@@ -345,6 +369,10 @@ TEST_F(BasicLinkedListTest, UpdateDuringRangeRead) {
     /* Update an item in the list when a fake range read is happening */
     updateItemDuringRangeRead(numItems,
                               keyPrefix + std::to_string(numItems - 1));
+
+    /* Check if the new element is added correctly */
+    std::vector<seqno_t> expectedSeqno = {1, 2, 3, 4};
+    EXPECT_EQ(expectedSeqno, basicLL->getAllSeqnoForVerification());
 }
 
 TEST_F(BasicLinkedListTest, DeletedItem) {
@@ -401,3 +429,184 @@ TEST_F(BasicLinkedListTest, MarkStale) {
     EXPECT_EQ(svSize, basicLL->getStaleValueBytes());
     EXPECT_EQ(svMetaDataSize, basicLL->getStaleMetadataBytes());
 }
+
+TEST_F(BasicLinkedListTest, RangeIterator) {
+    const int numItems = 3;
+
+    /* Add 3 new items */
+    std::vector<seqno_t> expectedSeqno =
+            addNewItemsToList(1, std::string("key"), numItems);
+
+    auto itr = basicLL->makeRangeIterator();
+
+    std::vector<seqno_t> actualSeqno;
+
+    /* Read all the items with the iterator */
+    while (itr.curr() != itr.end()) {
+        actualSeqno.push_back((*itr).getBySeqno());
+        ++itr;
+    }
+    EXPECT_EQ(expectedSeqno, actualSeqno);
+}
+
+TEST_F(BasicLinkedListTest, RangeIteratorNoItems) {
+    auto itr = basicLL->makeRangeIterator();
+    /* Since there are no items in the list to iterate over, we expect itr start
+       to be end */
+    EXPECT_EQ(itr.curr(), itr.end());
+}
+
+TEST_F(BasicLinkedListTest, RangeIteratorSingleItem) {
+    /* Add an item */
+    std::vector<seqno_t> expectedSeqno =
+            addNewItemsToList(1, std::string("key"), 1);
+
+    auto itr = basicLL->makeRangeIterator();
+
+    std::vector<seqno_t> actualSeqno;
+    /* Read all the items with the iterator */
+    while (itr.curr() != itr.end()) {
+        actualSeqno.push_back((*itr).getBySeqno());
+        ++itr;
+    }
+    EXPECT_EQ(expectedSeqno, actualSeqno);
+}
+
+TEST_F(BasicLinkedListTest, RangeIteratorOverflow) {
+    const int numItems = 1;
+    bool caughtOutofRangeExcp = false;
+
+    /* Add an item */
+    addNewItemsToList(1, std::string("key"), numItems);
+
+    auto itr = basicLL->makeRangeIterator();
+
+    /* Iterator till end */
+    while (itr.curr() != itr.end()) {
+        ++itr;
+    }
+
+    /* Try iterating beyond the end and expect exception to be thrown */
+    try {
+        ++itr;
+    } catch (std::out_of_range& e) {
+        caughtOutofRangeExcp = true;
+    }
+    EXPECT_TRUE(caughtOutofRangeExcp);
+}
+
+TEST_F(BasicLinkedListTest, RangeIteratorDeletion) {
+    const int numItems = 3;
+
+    /* Add 3 new items */
+    std::vector<seqno_t> expectedSeqno =
+            addNewItemsToList(1, std::string("key"), numItems);
+
+    /* Check if second range reader can read items after the first one is
+       deleted */
+    for (int i = 0; i < 2; ++i) {
+        auto itr = basicLL->makeRangeIterator();
+        std::vector<seqno_t> actualSeqno;
+
+        /* Read all the items with the iterator */
+        while (itr.curr() != itr.end()) {
+            actualSeqno.push_back((*itr).getBySeqno());
+            ++itr;
+        }
+        EXPECT_EQ(expectedSeqno, actualSeqno);
+
+        /* itr is deleted as each time we loop */
+    }
+}
+
+TEST_F(BasicLinkedListTest, RangeIteratorAddNewItemDuringRead) {
+    const int numItems = 3;
+
+    /* Add 3 new items */
+    std::vector<seqno_t> expectedSeqno =
+            addNewItemsToList(1, std::string("key"), numItems);
+
+    {
+        auto itr = basicLL->makeRangeIterator();
+
+        std::vector<seqno_t> actualSeqno;
+
+        /* Read one item */
+        actualSeqno.push_back((*itr).getBySeqno());
+        ++itr;
+
+        /* Add a new item */
+        addNewItemsToList(numItems + 1 /* start */, std::string("key"), 1);
+
+        /* Read the other items */
+        while (itr.curr() != itr.end()) {
+            actualSeqno.push_back((*itr).getBySeqno());
+            ++itr;
+        }
+        EXPECT_EQ(expectedSeqno, actualSeqno);
+
+        /* itr is deleted */
+    }
+
+    /* Now create new iterator and if we can read all elements */
+    expectedSeqno.push_back(numItems + 1);
+
+    {
+        auto itr = basicLL->makeRangeIterator();
+        std::vector<seqno_t> actualSeqno;
+
+        /* Read the other items */
+        while (itr.curr() != itr.end()) {
+            actualSeqno.push_back((*itr).getBySeqno());
+            ++itr;
+        }
+        EXPECT_EQ(expectedSeqno, actualSeqno);
+    }
+}
+
+TEST_F(BasicLinkedListTest, RangeIteratorUpdateItemDuringRead) {
+    const int numItems = 3;
+    const std::string keyPrefix("key");
+
+    /* Add 3 new items */
+    std::vector<seqno_t> expectedSeqno =
+            addNewItemsToList(1, keyPrefix, numItems);
+
+    {
+        auto itr = basicLL->makeRangeIterator();
+
+        std::vector<seqno_t> actualSeqno;
+
+        /* Read one item */
+        actualSeqno.push_back((*itr).getBySeqno());
+        ++itr;
+
+        /* Update an item */
+        updateItemDuringRangeRead(numItems /*highSeqno*/,
+                                  keyPrefix + std::to_string(2));
+
+        /* Read the other items */
+        while (itr.curr() != itr.end()) {
+            actualSeqno.push_back((*itr).getBySeqno());
+            ++itr;
+        }
+        EXPECT_EQ(expectedSeqno, actualSeqno);
+
+        /* itr is deleted */
+    }
+
+    /* Now create new iterator and if we can read all elements */
+    expectedSeqno.push_back(numItems + 1);
+
+    {
+        auto itr = basicLL->makeRangeIterator();
+        std::vector<seqno_t> actualSeqno;
+
+        /* Read the other items */
+        while (itr.curr() != itr.end()) {
+            actualSeqno.push_back((*itr).getBySeqno());
+            ++itr;
+        }
+        EXPECT_EQ(expectedSeqno, actualSeqno);
+    }
+}