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 * Ephemeral Bucket Tombstone Purger tasks
20 *
21 * Ephemeral buckets need to store tombstones (records of deleted documents) in
22 * memory (unlike EP buckets which can store on disk). Such tombstones have a
23 * finite lifetime, so we don't end up filling up all of RAM with them.
24 * To handle this, there are a set of background tasks which run
25 * periodically to purge tombstones which have reached a certain age.
26 *
27 * The high level process is simple - identify tombstones which are older than
28 * ephemeral_metadata_purge_age, and remove them from memory. However,
29 * the implementation is a little more complicated, due to the interaction
30 * between the HashTable and SequenceList which are used to access
31 * OrderedStoredValues:
32 *
33 * To purge OSVs we must remove them from both data-structures. For a HashTable
34 * alone this would be straightforward - iterate across it identifying
35 * tombstones we wish to purge, and remove from the HashTable (under the HTLock
36 * for that particular item).
37 * The SequenceList complicates things - the SeqList is non-owning (it only
38 * holds ptrs to OSVs), and a range read may be in progress by
39 * another actor. As such, we cannot actually delete (from HashTable) items
40 * which are within an in-flight range read, as that would break DCP
41 * invariants (if we've already told a downstream client that we have items in
42 * range [A,Z], we cannot delete item M before it has been read).
43 *
44 * Therefore, purging is handled with a two-phase approach, with each phase
45 * done by a different Task:
46 *
47 * 1. EphTombstoneHTCleaner - visit the HashTable for deleted items exceeding
48 *    ephemeral_metadata_purge_age. For such items, unlink from the HashTable
49 *    (but don't delete the object), and mark the item as stale.
50 *    Such item can no longer be located via the HashTable, but are still in
51 *    the SequenceList, hence in-progress range reads are safe to continue.
52 *
53 * 2. EphTombstoneStaleItemDeleter - iterate the SequenceList in order
54 *    looking for stale OSVs. For such items unlink from the SequenceList and
55 *    delete the OSV.
56 *
57 * Note that items can also become stale if they have been replaced with a newer
58 * revision - this occurs when an item needs to be modified but the existing
59 * revision is being read by a rangeRead and hence we cannot simply update the
60 * existing item. As such, EphTombstoneStaleItemDeleter task deletes stale
61 * items created in both situations, and isn't strictly limited to purging
62 * tombstones.
63 */
64#pragma once
65
66#include "ephemeral_vb.h"
67#include "kv_bucket_iface.h"
68#include "progress_tracker.h"
69#include "vb_visitors.h"
70
71class EphemeralBucket;
72class EphTombstoneStaleItemDeleter;
73
74/**
75 * HashTable Tombstone Purger visitor
76 *
77 * Visitor which is responsible for removing deleted items from the HashTable
78 * which are past their permitted lifetime.
79 *
80 * Ownership of such items is transferred to the SequenceList as 'stale' items;
81 * cleanup of the SequenceList is handled seperately (see
82 * SequenceList::purgeTombstones).
83*/
84class EphemeralVBucket::HTTombstonePurger : public VBucketAwareHTVisitor {
85public:
86    HTTombstonePurger(rel_time_t purgeAge);
87
88    // Set the deadline at which point the visitor will pause visiting.
89    void setDeadline(std::chrono::steady_clock::time_point deadline);
90
91    void setCurrentVBucket(VBucket& vb) override;
92
93    bool visit(const HashTable::HashBucketLock& lh, StoredValue& v) override;
94
95    /// Return the number of items visited in the HashTable.
96    size_t getVisitedCount() const {
97        return numVisitedItems;
98    }
99
100    /// Return the number of items purged from the HashTable.
101    size_t getNumItemsMarkedStale() const {
102        return numPurgedItems;
103    }
104
105    void clearStats();
106
107protected:
108    /// VBucket being visited.
109    EphemeralVBucket* vbucket;
110
111    /// Time point the purge is running at. Set to ep_real_time in object
112    /// creation.
113    const time_t now;
114
115    /// Items older than this age are purged. "Age" is defined as:
116    ///    now - delete_time.
117    const rel_time_t purgeAge;
118
119    /// Estimates how far we have got, and when we should pause.
120    ProgressTracker progressTracker;
121
122    /// Count of how many items have been visited.
123    size_t numVisitedItems;
124
125    /// Count of how many items have been purged.
126    size_t numPurgedItems;
127};
128
129/**
130 * Task responsible for identifying tombstones (deleted item markers) which
131 * are too old, and removing from the Ephemeral buckets' HashTable.
132 */
133class EphTombstoneHTCleaner : public GlobalTask {
134public:
135    EphTombstoneHTCleaner(EventuallyPersistentEngine* e,
136                          EphemeralBucket& bucket);
137
138    bool run() override;
139
140    std::string getDescription() override;
141
142    std::chrono::microseconds maxExpectedDuration() override;
143
144private:
145    /// How long should each chunk of HT cleaning run for?
146    std::chrono::milliseconds getChunkDuration() const;
147
148    /// Duration (in seconds) task should sleep for between runs.
149    size_t getSleepTime() const;
150
151    /// Age (in seconds) which deleted items will be purged after.
152    size_t getDeletedPurgeAge() const;
153
154    /// Returns the underlying VBTombstonePurger instance.
155    EphemeralVBucket::HTTombstonePurger& getPurgerVisitor();
156
157    /// The bucket we are associated with.
158    EphemeralBucket& bucket;
159
160    /// Opaque marker indicating how far through the KVBucket we have visited.
161    KVBucketIface::Position bucketPosition;
162
163    /**
164     * Visitor adapter which supports pausing & resuming (records how far
165     * though a VBucket is has got). unique_ptr as we re-create it for each
166     * complete pass.
167     */
168    std::unique_ptr<PauseResumeVBAdapter> prAdapter;
169
170    /// Second paired task which deletes stale items from the sequenceList.
171    std::shared_ptr<EphTombstoneStaleItemDeleter> staleItemDeleterTask;
172
173    /// TaskId for StaleItemDeleter registered with executorpool.
174    size_t staleItemDeleterTaskId;
175};
176
177/**
178 * Task responsible for deleting stale items from Ephemeral buckets'
179 * SequenceLists.
180 *
181 * Works in conjunction with EphTombstoneCleanupHashTable.
182 */
183class EphTombstoneStaleItemDeleter : public GlobalTask {
184public:
185    EphTombstoneStaleItemDeleter(EventuallyPersistentEngine* e,
186                                 EphemeralBucket& bucket);
187
188    bool run() override;
189
190    std::string getDescription() override;
191
192    std::chrono::microseconds maxExpectedDuration() override;
193
194private:
195    /// How long should each chunk of stale item deleter run for?
196    std::chrono::milliseconds getChunkDuration() const;
197
198    /// The bucket we are associated with.
199    EphemeralBucket& bucket;
200
201    /// Opaque marker indicating how far through the KVBucket we have visited.
202    KVBucketIface::Position bucketPosition;
203
204    /// Vb visitor instance that deletes the stale items by visiting all
205    /// vbuckets one by one
206    std::unique_ptr<EphemeralVBucket::StaleItemDeleter>
207            staleItemDeleteVbVisitor;
208};
209