MB-24151: Implement general range read iterator in seqlist
[ep-engine.git] / 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 };