96d5315989e78c709b3dc4a656782c9c6267cd0c
[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 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 };