src/seqlist.h

   1 /* -*- Mode: C++; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
   2 /*
   3  *     Copyright 2017 Couchbase, Inc
   4  *
   5  *   Licensed under the Apache License, Version 2.0 (the "License");
   6  *   you may not use this file except in compliance with the License.
   7  *   You may obtain a copy of the License at
   8  *
   9  *       http://www.apache.org/licenses/LICENSE-2.0
  10  *
  11  *   Unless required by applicable law or agreed to in writing, software
  12  *   distributed under the License is distributed on an "AS IS" BASIS,
  13  *   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14  *   See the License for the specific language governing permissions and
  15  *   limitations under the License.
  16  */
  17
  18 /**
  19  * This header file contains the abstract base class for the classes that hold
  20  * ordered sequence of items in memory. This is not generic, holds only ordered
  21  * seq of OrderedStoredValue's. (OrderedStoredValue is the in-memory
  22  * representation of an
  23  * item)
  24  */
  25
  26 #pragma once
  27
  28 #include <mutex>
  29 #include <vector>
  30
  31 #include "config.h"
  32 #include "item.h"
  33 #include "memcached/engine_error.h"
  34 #include "stored-value.h"
  35
  36 /* [EPHE TODO]: Check if uint64_t can be used instead */
  37 using seqno_t = int64_t;
  38
  39 /**
  40  * SequenceList is the abstract base class for the classes that hold ordered
  41  * sequence of items in memory. To store/retreive items sequencially in memory,
  42  * in our multi-threaded, monotonically increasing seq model, we need these
  43  * classes around basic data structures like Linkedlist or Skiplist.
  44  *
  45  * 'OrderedStoredValue' is the in-memory representation of an item that can be
  46  * stored sequentially and SequenceList derivatives store a sequence of
  47  * 'OrderedStoredValues'. Based on the implementation of SequenceList,
  48  * OrderedStoredValue might have to carry an intrusive component that
  49  * is necessary for the list.
  50  *
  51  * SequenceList expects the module that contains it, takes the responsibility
  52  * of serializing the OrderedStoredValue. SequenceList only guarentees to hold
  53  * the OrderedStoredValue in the order they are sent to it. For this it forces
  54  * the write calls to pass the seq lock held by them
  55  *
  56  * Note: These classes only handle the position of the 'OrderedStoredValue' in
  57  *       the ordered sequence desired. They do not update a OrderedStoredValue.
  58  *
  59  *       In the file 'item', 'OrderedStoredValue' are used interchangeably
  60  *
  61  * [EPHE TODO]: create a documentation (with diagrams) explaining write, update,
  62  *              rangeRead and Clean Up
  63  */
  64 class SequenceList {
  65 protected:
  66     /**
  67      * Abstract base class for implementation of range iterators in derived
  68      * classes of SequenceList.
  69      *
  70      * (a) The API is for unidirectional (forward only) iterator.
  71      * (b) Iterator cannot be invalidated while in use.
  72      * (c) Reading all the items from the iterator results in point-in-time
  73      *     snapshot.
  74      * (d) Only 1 iterator can be created for now.
  75      * (e) Currently iterator can be created only from start till end
  76      */
  77     class RangeIteratorImpl {
  78     public:
  79         virtual ~RangeIteratorImpl() {
  80         }
  81
  82         /**
  83          * Returns the stored item at iterator's position
  84          */
  85         virtual OrderedStoredValue& operator*() const = 0;
  86
  87         /**
  88          * Pre increment of the iterator position
  89          *
  90          * Note: We do not allow post increment for now as we support only
  91          *       one iterator at a time. (hence, we don't create a temp copy
  92          *       of the iterator obj)
  93          */
  94         virtual RangeIteratorImpl& operator++() = 0;
  95
  96         /**
  97          * Curr iterator position, indicated by the seqno of the item at that
  98          * position
  99          */
 100         virtual seqno_t curr() const = 0;
 101
 102         /**
 103          * End position of iterator, indicated by the seqno > highest_seqno
 104          * in the iterator range
 105          */
 106         virtual seqno_t end() const = 0;
 107     };
 108
 109 public:
 110     /**
 111      * Indicates whether the updateListElem is successful or the list is
 112      * allowing
 113      * only appends at the moment.
 114      */
 115     enum class UpdateStatus { Success, Append };
 116
 117     /**
 118      * RangeIterator for a SequenceList objects.
 119      *
 120      * The iterator is unidirectional (forward only) and cannot be invalidated
 121      * while in use. That means reading the items in the iterator results in a
 122      * valid point-in-time snapshot. But this adds a caveat that while an
 123      * iterator instance is active, certain invariants are to be met to get the
 124      * snapshot, and this happens at the expense of increased memory usage.
 125      *
 126      * Implementation follows the pimpl idiom. This class serves as a wrapper
 127      * for the abstract base class that defines the APIs for range iteration on
 128      * the derived concrete classes of the SequenceList. It calls the range
 129      * iterators of the concrete classes polymorphically at runtime. However
 130      * clients get this statically typed "RangeIterator" object when they
 131      * request for an iterator for a SequenceList object.
 132      *
 133      * Usage:
 134      * 1. Create an iterator instance using SequenceList::makeRangeIterator()
 135      * 2. Iterate (read) through all the list elements.
 136      * 3. Delete the iterator.
 137      * Note: (a) Do not hold the iterator for long, as it will result in stale
 138      *           items in list and hence increased memory usage.
 139      *       (b) Make sure to delete the iterator after using it.
 140      *       (c) For now, we allow on one RangeIterator. Try to create more
 141      *           iterators will result in the create call(s) being blocked.
 142      */
 143     class RangeIterator {
 144     public:
 145         RangeIterator(std::unique_ptr<RangeIteratorImpl> rangeIterImpl);
 146
 147         /* Needed for MSVC.
 148            MSVC does not do "return value optimization" if copy constructor is
 149            defined before move constructor
 150            (http://stackoverflow.com/questions/29459040)
 151          */
 152         RangeIterator(RangeIterator&& other)
 153             : rangeIterImpl(std::move(other.rangeIterImpl)) {
 154         }
 155
 156         RangeIterator(RangeIterator& other) = delete;
 157
 158         /**
 159          * Returns the stored item at iterator's position
 160          */
 161         OrderedStoredValue& operator*() const;
 162
 163         /**
 164          * Pre increment of the iterator position
 165          */
 166         RangeIterator& operator++();
 167
 168         /**
 169          * Curr iterator position, indicated by the seqno of the item at that
 170          * position
 171          */
 172         seqno_t curr();
 173
 174         /**
 175          * Curr iterator position, indicated by the seqno of the item at that
 176          * position
 177          */
 178         seqno_t end();
 179
 180     private:
 181         /* Pointer to the abstract class of range iterator implementation */
 182         std::unique_ptr<RangeIteratorImpl> rangeIterImpl;
 183     };
 184
 185     virtual ~SequenceList() {
 186     }
 187
 188     /**
 189      * Add a new item at the end of the list.
 190      *
 191      * @param seqLock A sequence lock the calling module is expected to hold.
 192      * @param v Ref to orderedStoredValue which will placed into the linked list
 193      *          Its intrusive list links will be updated.
 194      */
 195     virtual void appendToList(std::lock_guard<std::mutex>& seqLock,
 196                               OrderedStoredValue& v) = 0;
 197
 198     /**
 199      * If possible, update an existing element the list and move it to end.
 200      * If there is a range read in the position of the element being updated
 201      * we do not allow the update and indicate the caller to do an append.
 202      *
 203      * @param seqLock A sequence lock the calling module is expected to hold.
 204      * @param v Ref to orderedStoredValue which will placed into the linked list
 205      *          Its intrusive list links will be updated.
 206      *
 207      * @return UpdateStatus::Success list element has been updated and moved to
 208      *                               end.
 209      *         UpdateStatus::Append list element is *not* updated. Caller must
 210      *                              handle the append.
 211      */
 212     virtual SequenceList::UpdateStatus updateListElem(
 213             std::lock_guard<std::mutex>& seqLock, OrderedStoredValue& v) = 0;
 214
 215     /**
 216      * Provides point-in-time snapshots which can be used for incremental
 217      * replication.
 218      *
 219      * Copies the StoredValues as a vector of ref counterd items starting from
 220      * 'start + 1' seqno into 'items' as a snapshot.
 221      *
 222      * Since we use monotonically increasing point-in-time snapshots we cannot
 223      * guarantee that the snapshot ends at the requested end seqno. Due to
 224      * dedups we may have to send till a higher seqno in the snapshot.
 225      *
 226      * @param start requested start seqno
 227      * @param end requested end seqno
 228      *
 229      * @return ENGINE_SUCCESS, items in the snapshot and adjusted endSeqNo
 230      *         ENGINE_ENOMEM on no memory to copy items
 231      *         ENGINE_ERANGE on incorrect start and end
 232      */
 233     virtual std::tuple<ENGINE_ERROR_CODE, std::vector<UniqueItemPtr>, seqno_t>
 234     rangeRead(seqno_t start, seqno_t end) = 0;
 235
 236     /**
 237      * Updates the highSeqno in the list. Since seqno is generated and managed
 238      * outside the list, the module managing it must update this after the seqno
 239      * is generated for the item already put in the list.
 240      * @param highSeqnoLock The lock protecting the high seqnos the caller is
 241      * expected to hold
 242      * @param v Ref to orderedStoredValue
 243      */
 244     virtual void updateHighSeqno(std::lock_guard<std::mutex>& highSeqnoLock,
 245                                  const OrderedStoredValue& v) = 0;
 246
 247     /**
 248      * Updates the highestDedupedSeqno in the list. Since seqno is generated and
 249      * managed outside the list, the module managing it must update this after
 250      * the seqno is generated for the item already put in the list.
 251      * @param highSeqnoLock The lock protecting the high seqnos the caller is
 252      * expected to hold
 253      * @param v Ref to orderedStoredValue
 254      *
 255      */
 256     virtual void updateHighestDedupedSeqno(
 257             std::lock_guard<std::mutex>& highSeqnoLock,
 258             const OrderedStoredValue& v) = 0;
 259
 260     /**
 261      * Mark an OrderedStoredValue stale and assumes its ownership.
 262      * Note: It is upto the sequential data structure implementation how it
 263      *       wants to own the OrderedStoredValue (as owned type vs non-owned
 264      *       type)
 265      *
 266      * @param ownedSv StoredValue whose ownership is passed to the sequential
 267      *                data structure.
 268      */
 269     virtual void markItemStale(StoredValue::UniquePtr ownedSv) = 0;
 270
 271     /**
 272      * Remove from sequence list and delete all OSVs which are purgable.
 273      * OSVs which can be purged are items which are outside the ReadRange and
 274      * are Stale.
 275      *
 276      * @return The number of items purged from the sequence list (and hence
 277      *         deleted).
 278      */
 279     virtual size_t purgeTombstones() = 0;
 280
 281     /**
 282      * Updates the number of deleted items in the sequence list whenever
 283      * an item is modified.
 284      *
 285      * @param oldDeleted Was the old item deleted?
 286      * @param newDeleted Was the new item replacing it deleted?
 287      */
 288     virtual void updateNumDeletedItems(bool oldDeleted, bool newDeleted) = 0;
 289
 290     /**
 291      * Returns the number of stale items in the list.
 292      *
 293      * @return count of stale items
 294      */
 295     virtual uint64_t getNumStaleItems() const = 0;
 296
 297     /**
 298      * Return the count of bytes of the values of stale items in the list.
 299      */
 300     virtual size_t getStaleValueBytes() const = 0;
 301
 302     /**
 303      * Return the count of bytes of the metadata of stale items in the list.
 304      */
 305     virtual size_t getStaleMetadataBytes() const = 0;
 306
 307     /**
 308      * Returns the number of deleted items in the list.
 309      *
 310      * @return count of deleted items
 311      */
 312     virtual uint64_t getNumDeletedItems() const = 0;
 313
 314     /**
 315      * Returns the number of items in the list.
 316      *
 317      * @return count of items
 318      */
 319     virtual uint64_t getNumItems() const = 0;
 320
 321     /**
 322      * Returns the highSeqno in the list.
 323      */
 324     virtual uint64_t getHighSeqno() const = 0;
 325
 326     /**
 327      * Returns the highest de-duplicated sequence number in the list.
 328      */
 329     virtual uint64_t getHighestDedupedSeqno() const = 0;
 330
 331     /**
 332      * Returns the highest purged Deleted sequence number in the list.
 333      */
 334     virtual seqno_t getHighestPurgedDeletedSeqno() const = 0;
 335
 336     /**
 337      * Returns the current range read begin sequence number.
 338      */
 339     virtual uint64_t getRangeReadBegin() const = 0;
 340
 341     /**
 342      * Returns the current range read end sequence number.
 343      */
 344     virtual uint64_t getRangeReadEnd() const = 0;
 345
 346     /**
 347      * Returns the lock which must be held to modify the highSeqno or the
 348      * highestDedupedSeqno
 349      */
 350     virtual std::mutex& getHighSeqnosLock() const = 0;
 351
 352     /**
 353      * Returns a range iterator for the underlying SequenceList obj
 354      */
 355     virtual SequenceList::RangeIterator makeRangeIterator() = 0;
 356
 357     /**
 358      * Debug - prints a representation of the list to stderr.
 359      */
 360     virtual void dump() const = 0;
 361 };