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 public:
  66     /**
  67      * Indicates whether the updateListElem is successful or the list is
  68      * allowing
  69      * only appends at the moment.
  70      */
  71     enum class UpdateStatus { Success, Append };
  72
  73     virtual ~SequenceList() {
  74     }
  75
  76     /**
  77      * Add a new item at the end of the list.
  78      *
  79      * @param seqLock A sequence lock the calling module is expected to hold.
  80      * @param v Ref to orderedStoredValue which will placed into the linked list
  81      *          Its intrusive list links will be updated.
  82      */
  83     virtual void appendToList(std::lock_guard<std::mutex>& seqLock,
  84                               OrderedStoredValue& v) = 0;
  85
  86     /**
  87      * If possible, update an existing element the list and move it to end.
  88      * If there is a range read in the position of the element being updated
  89      * we do not allow the update and indicate the caller to do an append.
  90      *
  91      * @param seqLock A sequence lock the calling module is expected to hold.
  92      * @param v Ref to orderedStoredValue which will placed into the linked list
  93      *          Its intrusive list links will be updated.
  94      *
  95      * @return UpdateStatus::Success list element has been updated and moved to
  96      *                               end.
  97      *         UpdateStatus::Append list element is *not* updated. Caller must
  98      *                              handle the append.
  99      */
 100     virtual SequenceList::UpdateStatus updateListElem(
 101             std::lock_guard<std::mutex>& seqLock, OrderedStoredValue& v) = 0;
 102
 103     /**
 104      * Provides point-in-time snapshots which can be used for incremental
 105      * replication.
 106      *
 107      * Copies the StoredValues as a vector of ref counterd items starting from
 108      * 'start + 1' seqno into 'items' as a snapshot.
 109      *
 110      * Since we use monotonically increasing point-in-time snapshots we cannot
 111      * guarantee that the snapshot ends at the requested end seqno. Due to
 112      * dedups we may have to send till a higher seqno in the snapshot.
 113      *
 114      * @param start requested start seqno
 115      * @param end requested end seqno
 116      *
 117      * @return ENGINE_SUCCESS, items in the snapshot and adjusted endSeqNo
 118      *         ENGINE_ENOMEM on no memory to copy items
 119      *         ENGINE_ERANGE on incorrect start and end
 120      */
 121     virtual std::tuple<ENGINE_ERROR_CODE, std::vector<UniqueItemPtr>, seqno_t>
 122     rangeRead(seqno_t start, seqno_t end) = 0;
 123
 124     /**
 125      * Updates the highSeqno in the list. Since seqno is generated and managed
 126      * outside the list, the module managing it must update this after the seqno
 127      * is generated for the item already put in the list.
 128      * @param highSeqnoLock The lock protecting the high seqnos the caller is
 129      * expected to hold
 130      * @param v Ref to orderedStoredValue
 131      */
 132     virtual void updateHighSeqno(std::lock_guard<std::mutex>& highSeqnoLock,
 133                                  const OrderedStoredValue& v) = 0;
 134
 135     /**
 136      * Updates the highestDedupedSeqno in the list. Since seqno is generated and
 137      * managed outside the list, the module managing it must update this after
 138      * the seqno is generated for the item already put in the list.
 139      * @param highSeqnoLock The lock protecting the high seqnos the caller is
 140      * expected to hold
 141      * @param v Ref to orderedStoredValue
 142      *
 143      */
 144     virtual void updateHighestDedupedSeqno(
 145             std::lock_guard<std::mutex>& highSeqnoLock,
 146             const OrderedStoredValue& v) = 0;
 147
 148     /**
 149      * Mark an OrderedStoredValue stale and assumes its ownership.
 150      * Note: It is upto the sequential data structure implementation how it
 151      *       wants to own the OrderedStoredValue (as owned type vs non-owned
 152      *       type)
 153      *
 154      * @param ownedSv StoredValue whose ownership is passed to the sequential
 155      *                data structure.
 156      */
 157     virtual void markItemStale(StoredValue::UniquePtr ownedSv) = 0;
 158
 159     /**
 160      * Remove from sequence list and delete all OSVs which are purgable.
 161      * OSVs which can be purged are items which are outside the ReadRange and
 162      * are Stale.
 163      *
 164      * @return The number of items purged from the sequence list (and hence
 165      *         deleted).
 166      */
 167     virtual size_t purgeTombstones() = 0;
 168
 169     /**
 170      * Updates the number of deleted items in the sequence list whenever
 171      * an item is modified.
 172      *
 173      * @param oldDeleted Was the old item deleted?
 174      * @param newDeleted Was the new item replacing it deleted?
 175      */
 176     virtual void updateNumDeletedItems(bool oldDeleted, bool newDeleted) = 0;
 177
 178     /**
 179      * Returns the number of stale items in the list.
 180      *
 181      * @return count of stale items
 182      */
 183     virtual uint64_t getNumStaleItems() const = 0;
 184
 185     /**
 186      * Return the count of bytes of the values of stale items in the list.
 187      */
 188     virtual size_t getStaleValueBytes() const = 0;
 189
 190     /**
 191      * Return the count of bytes of the metadata of stale items in the list.
 192      */
 193     virtual size_t getStaleMetadataBytes() const = 0;
 194
 195     /**
 196      * Returns the number of deleted items in the list.
 197      *
 198      * @return count of deleted items
 199      */
 200     virtual uint64_t getNumDeletedItems() const = 0;
 201
 202     /**
 203      * Returns the number of items in the list.
 204      *
 205      * @return count of items
 206      */
 207     virtual uint64_t getNumItems() const = 0;
 208
 209     /**
 210      * Returns the highSeqno in the list.
 211      */
 212     virtual uint64_t getHighSeqno() const = 0;
 213
 214     /**
 215      * Returns the highest de-duplicated sequence number in the list.
 216      */
 217     virtual uint64_t getHighestDedupedSeqno() const = 0;
 218
 219     /**
 220      * Returns the highest purged Deleted sequence number in the list.
 221      */
 222     virtual seqno_t getHighestPurgedDeletedSeqno() const = 0;
 223
 224     /**
 225      * Returns the current range read begin sequence number.
 226      */
 227     virtual uint64_t getRangeReadBegin() const = 0;
 228
 229     /**
 230      * Returns the current range read end sequence number.
 231      */
 232     virtual uint64_t getRangeReadEnd() const = 0;
 233
 234     /**
 235      * Returns the lock which must be held to modify the highSeqno or the
 236      * highestDedupedSeqno
 237      */
 238     virtual std::mutex& getHighSeqnosLock() const = 0;
 239
 240     /**
 241      * Debug - prints a representation of the list to stderr.
 242      */
 243     virtual void dump() const = 0;
 244 };