diff options
Diffstat (limited to 'src/mongo')
| -rw-r--r-- | src/mongo/db/catalog/SConscript | 2 | ||||
| -rw-r--r-- | src/mongo/db/catalog/catalog_control.cpp | 2 | ||||
| -rw-r--r-- | src/mongo/db/catalog/collection_catalog.cpp | 527 | ||||
| -rw-r--r-- | src/mongo/db/catalog/collection_catalog.h | 106 | ||||
| -rw-r--r-- | src/mongo/db/catalog/collection_catalog_test.cpp | 796 | ||||
| -rw-r--r-- | src/mongo/db/catalog/historical_catalogid_tracker.cpp | 695 | ||||
| -rw-r--r-- | src/mongo/db/catalog/historical_catalogid_tracker.h | 179 | ||||
| -rw-r--r-- | src/mongo/db/catalog/historical_catalogid_tracker_test.cpp | 1018 | ||||
| -rw-r--r-- | src/mongo/db/storage/storage_engine_impl.cpp | 7 |
9 files changed, 1950 insertions, 1382 deletions
diff --git a/src/mongo/db/catalog/SConscript b/src/mongo/db/catalog/SConscript index e254e684b5c..0cbf81433f2 100644 --- a/src/mongo/db/catalog/SConscript +++ b/src/mongo/db/catalog/SConscript @@ -293,6 +293,7 @@ env.Library( target='collection_catalog', source=[ 'collection_catalog.cpp', + 'historical_catalogid_tracker.cpp', 'uncommitted_catalog_updates.cpp', 'uncommitted_multikey.cpp', 'views_for_database.cpp', @@ -679,6 +680,7 @@ if wiredtiger: 'create_collection_test.cpp', 'database_test.cpp', 'drop_database_test.cpp', + 'historical_catalogid_tracker_test.cpp', 'index_build_entry_test.cpp', 'index_builds_manager_test.cpp', 'index_key_validate_test.cpp', diff --git a/src/mongo/db/catalog/catalog_control.cpp b/src/mongo/db/catalog/catalog_control.cpp index 5fb437bfbfd..3e94b7db845 100644 --- a/src/mongo/db/catalog/catalog_control.cpp +++ b/src/mongo/db/catalog/catalog_control.cpp @@ -212,7 +212,7 @@ void openCatalog(OperationContext* opCtx, // Remove catalogId mappings for larger timestamp than 'stableTimestamp'. CollectionCatalog::write(opCtx, [stableTimestamp](CollectionCatalog& catalog) { - catalog.cleanupForCatalogReopen(stableTimestamp); + catalog.catalogIdTracker().rollback(stableTimestamp); }); // Ignore orphaned idents because this function is used during rollback and not at diff --git a/src/mongo/db/catalog/collection_catalog.cpp b/src/mongo/db/catalog/collection_catalog.cpp index 6ba7c1b8894..d89e4f90797 100644 --- a/src/mongo/db/catalog/collection_catalog.cpp +++ b/src/mongo/db/catalog/collection_catalog.cpp @@ -52,13 +52,6 @@ namespace mongo { namespace { -// Sentinel id for marking a catalogId mapping range as unknown. Must use an invalid RecordId. -static RecordId kUnknownRangeMarkerId = RecordId::minLong(); -// Maximum number of entries in catalogId mapping when inserting catalogId missing at timestamp. -// Used to avoid quadratic behavior when inserting entries at the beginning. When threshold is -// reached we will fall back to more durable catalog scans. -static constexpr int kMaxCatalogIdMappingLengthForMissingInsert = 1000; - constexpr auto kNumDurableCatalogScansDueToMissingMapping = "numScansDueToMissingMapping"_sd; struct LatestCollectionCatalog { @@ -101,18 +94,6 @@ void assertViewCatalogValid(const ViewsForDatabase& viewsForDb) { const auto maxUuid = UUID::parse("FFFFFFFF-FFFF-FFFF-FFFF-FFFFFFFFFFFF").getValue(); const auto minUuid = UUID::parse("00000000-0000-0000-0000-000000000000").getValue(); - - -// Copy existing value from immutable data structure or default-construct if not existing -template <typename Container, typename Key> -auto copyIfExists(const Container& container, const Key& key) { - const auto* value = container.find(key); - if (value) { - return *value; - } - return typename Container::mapped_type(); -} - } // namespace /** @@ -259,7 +240,7 @@ public: resourceCatalog.remove({RESOURCE_COLLECTION, from}, from); resourceCatalog.add({RESOURCE_COLLECTION, to}, to); - catalog._pushCatalogIdForRename(from, to, commitTime); + catalog._catalogIdTracker.rename(from, to, commitTime); }); break; } @@ -302,7 +283,7 @@ public: if (commitTime) { coll->setMinimumValidSnapshot(commitTime.value()); } - catalog._pushCatalogIdForNSSAndUUID( + catalog._catalogIdTracker.create( coll->ns(), coll->uuid(), coll->getCatalogId(), commitTime); catalog._pendingCommitNamespaces = @@ -1095,76 +1076,48 @@ const Collection* CollectionCatalog::_openCollectionAtPointInTimeByNamespaceOrUU return nullptr; } -CollectionCatalog::CatalogIdLookup CollectionCatalog::_checkWithOldestCatalogIdTimestampMaintained( - boost::optional<Timestamp> ts) const { - // If the request was with a time prior to the oldest maintained time it is unknown, otherwise - // we know it is not existing. - return {RecordId{}, - ts && *ts < _oldestCatalogIdTimestampMaintained - ? CollectionCatalog::CatalogIdLookup::Existence::kUnknown - : CollectionCatalog::CatalogIdLookup::Existence::kNotExists}; -} - -CollectionCatalog::CatalogIdLookup CollectionCatalog::_findCatalogIdInRange( - boost::optional<Timestamp> ts, const std::vector<TimestampedCatalogId>& range) const { - if (!ts) { - auto catalogId = range.back().id; - if (catalogId) { - return {*catalogId, CatalogIdLookup::Existence::kExists}; - } - return {RecordId{}, CatalogIdLookup::Existence::kNotExists}; - } - - auto rangeIt = - std::upper_bound(range.begin(), range.end(), *ts, [](const auto& ts, const auto& entry) { - return ts < entry.ts; - }); - if (rangeIt == range.begin()) { - return _checkWithOldestCatalogIdTimestampMaintained(ts); - } - // Upper bound returns an iterator to the first entry with a larger timestamp. Decrement the - // iterator to get the last entry where the time is less or equal. - auto catalogId = (--rangeIt)->id; - if (catalogId) { - if (*catalogId != kUnknownRangeMarkerId) { - return {*catalogId, CatalogIdLookup::Existence::kExists}; - } else { - return {RecordId{}, CatalogIdLookup::Existence::kUnknown}; - } - } - return {RecordId{}, CatalogIdLookup::Existence::kNotExists}; -} - boost::optional<DurableCatalogEntry> CollectionCatalog::_fetchPITCatalogEntry( OperationContext* opCtx, const NamespaceStringOrUUID& nssOrUUID, boost::optional<Timestamp> readTimestamp) const { auto [catalogId, result] = nssOrUUID.nss() - ? lookupCatalogIdByNSS(*nssOrUUID.nss(), readTimestamp) - : lookupCatalogIdByUUID(*nssOrUUID.uuid(), readTimestamp); - if (result == CatalogIdLookup::Existence::kNotExists) { + ? _catalogIdTracker.lookup(*nssOrUUID.nss(), readTimestamp) + : _catalogIdTracker.lookup(*nssOrUUID.uuid(), readTimestamp); + if (result == HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists) { return boost::none; } auto writeCatalogIdAfterScan = [&](const boost::optional<DurableCatalogEntry>& catalogEntry) { + if (!catalogEntry) { + if (const boost::optional<NamespaceString>& ns = nssOrUUID.nss()) { + if (!_catalogIdTracker.canRecordNonExisting(*ns)) { + return; + } + } else { + if (!_catalogIdTracker.canRecordNonExisting(*nssOrUUID.uuid())) { + return; + } + } + } + CollectionCatalog::write(opCtx, [&](CollectionCatalog& catalog) { - // Convert from 'const boost::optional<NamespaceString>&' to 'boost::optional<const - // NamespaceString&>' without copy. - auto nss = [&]() -> boost::optional<const NamespaceString&> { - if (const boost::optional<NamespaceString>& ns = nssOrUUID.nss()) - return ns.value(); - return boost::none; - }(); // Insert catalogId for both the namespace and UUID if the catalog entry is found. - catalog._insertCatalogIdForNSSAndUUIDAfterScan( - catalogEntry ? catalogEntry->metadata->nss : nss, - catalogEntry ? catalogEntry->metadata->options.uuid : nssOrUUID.uuid(), - catalogEntry ? boost::make_optional(catalogEntry->catalogId) : boost::none, - *readTimestamp); + if (catalogEntry) { + catalog._catalogIdTracker.recordExistingAtTime( + catalogEntry->metadata->nss, + *catalogEntry->metadata->options.uuid, + catalogEntry->catalogId, + *readTimestamp); + } else if (const boost::optional<NamespaceString>& ns = nssOrUUID.nss()) { + catalog._catalogIdTracker.recordNonExistingAtTime(*ns, *readTimestamp); + } else { + catalog._catalogIdTracker.recordNonExistingAtTime(*nssOrUUID.uuid(), + *readTimestamp); + } }); }; - if (result == CatalogIdLookup::Existence::kUnknown) { + if (result == HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown) { // We shouldn't receive kUnknown when we don't have a timestamp since no timestamp means // we're operating on the latest. invariant(readTimestamp); @@ -1718,22 +1671,6 @@ bool CollectionCatalog::containsCollection(OperationContext* opCtx, return coll->get() == collection; } -CollectionCatalog::CatalogIdLookup CollectionCatalog::lookupCatalogIdByNSS( - const NamespaceString& nss, boost::optional<Timestamp> ts) const { - if (const std::vector<TimestampedCatalogId>* mapping = _nssCatalogIds.find(nss)) { - return _findCatalogIdInRange(ts, *mapping); - } - return _checkWithOldestCatalogIdTimestampMaintained(ts); -} - -CollectionCatalog::CatalogIdLookup CollectionCatalog::lookupCatalogIdByUUID( - const UUID& uuid, boost::optional<Timestamp> ts) const { - if (const std::vector<TimestampedCatalogId>* mapping = _uuidCatalogIds.find(uuid)) { - return _findCatalogIdInRange(ts, *mapping); - } - return _checkWithOldestCatalogIdTimestampMaintained(ts); -} - void CollectionCatalog::iterateViews( OperationContext* opCtx, const DatabaseName& dbName, @@ -2011,7 +1948,7 @@ void CollectionCatalog::_registerCollection(OperationContext* opCtx, // When restarting from standalone mode to a replica set, the stable timestamp may be null. // We still need to register the nss and UUID with the catalog. - _pushCatalogIdForNSSAndUUID(nss, uuid, coll->getCatalogId(), commitTime); + _catalogIdTracker.create(nss, uuid, coll->getCatalogId(), commitTime); } @@ -2085,7 +2022,7 @@ std::shared_ptr<Collection> CollectionCatalog::deregisterCollection( // Push drop unless this is a rollback of a create if (coll->isCommitted()) { - _pushCatalogIdForNSSAndUUID(ns, uuid, boost::none, commitTime); + _catalogIdTracker.drop(ns, uuid, commitTime); } if (!ns.isOnInternalDb() && !ns.isSystem()) { @@ -2166,264 +2103,6 @@ void CollectionCatalog::_ensureNamespaceDoesNotExist(OperationContext* opCtx, } } -void CollectionCatalog::_pushCatalogIdForNSSAndUUID(const NamespaceString& nss, - const UUID& uuid, - boost::optional<RecordId> catalogId, - boost::optional<Timestamp> ts) { - auto doPushCatalogId = [this, &ts, &catalogId](auto& catalogIdsContainer, - auto& catalogIdChangesContainer, - const auto& key) { - auto ids = copyIfExists(catalogIdsContainer, key); - - // Helper to write updated id mapping back into container at scope exit - ScopeGuard scopedGuard([&] { - // Make sure we erase mapping for namespace or UUID if the list is left empty as - // lookups expect at least one entry for existing namespaces or UUIDs. - if (ids.empty()) { - catalogIdsContainer = catalogIdsContainer.erase(key); - } else { - catalogIdsContainer = catalogIdsContainer.set(key, std::move(ids)); - } - }); - - if (!ts) { - // Make sure untimestamped writes have a single entry in mapping. If we're mixing - // timestamped with untimestamped (such as repair). Ignore the untimestamped writes as - // an untimestamped deregister will correspond with an untimestamped register. We should - // leave the mapping as-is in this case. - if (ids.empty() && catalogId) { - // This namespace or UUID was added due to an untimestamped write, add an entry - // with min timestamp - ids.push_back(TimestampedCatalogId{catalogId, Timestamp::min()}); - } else if (ids.size() == 1 && !catalogId) { - // This namespace or UUID was removed due to an untimestamped write, clear entries. - ids.clear(); - } else if (ids.size() > 1 && catalogId && !storageGlobalParams.repair) { - // This namespace or UUID was added due to an untimestamped write. But this - // namespace or UUID already had some timestamped writes performed. In this case, we - // re-write the history. The only known area that does this today is when profiling - // is enabled (untimestamped collection creation), followed by dropping the database - // (timestamped collection drop). - // TODO SERVER-75740: Remove this branch. - invariant(!ids.back().ts.isNull()); - - ids.clear(); - ids.push_back(TimestampedCatalogId{catalogId, Timestamp::min()}); - } - - return; - } - - // An entry could exist already if concurrent writes are performed, keep the latest change - // in that case. - if (!ids.empty() && ids.back().ts == *ts) { - ids.back().id = catalogId; - return; - } - - // Otherwise, push new entry at the end. Timestamp is always increasing - invariant(ids.empty() || ids.back().ts < *ts); - // If the catalogId is the same as last entry, there's nothing we need to do. This can - // happen when the catalog is reopened. - if (!ids.empty() && ids.back().id == catalogId) { - return; - } - - // A drop entry can't be pushed in the container if it's empty. This is because we cannot - // initialize the namespace or UUID with a single drop. - invariant(!ids.empty() || catalogId); - - ids.push_back(TimestampedCatalogId{catalogId, *ts}); - - auto changes = catalogIdChangesContainer.transient(); - _markForCatalogIdCleanupIfNeeded(key, changes, ids); - catalogIdChangesContainer = changes.persistent(); - }; - - doPushCatalogId(_nssCatalogIds, _nssCatalogIdChanges, nss); - doPushCatalogId(_uuidCatalogIds, _uuidCatalogIdChanges, uuid); -} - -void CollectionCatalog::_pushCatalogIdForRename(const NamespaceString& from, - const NamespaceString& to, - boost::optional<Timestamp> ts) { - // Get 'toIds' first, it may need to instantiate in the container which invalidates all - // references. - auto idsWriter = _nssCatalogIds.transient(); - auto changesWriter = _nssCatalogIdChanges.transient(); - auto toIds = copyIfExists(idsWriter, to); - auto fromIds = copyIfExists(idsWriter, from); - invariant(!fromIds.empty()); - - // Helper to write updated id mappings back into containers at scope exit - ScopeGuard scopedGuard([&] { - // Make sure we erase mapping for namespace or UUID if the list is left empty as - // lookups expect at least one entry for existing namespaces or UUIDs. - idsWriter.set(to, std::move(toIds)); - if (fromIds.empty()) { - idsWriter.erase(from); - } else { - idsWriter.set(from, std::move(fromIds)); - } - _nssCatalogIds = idsWriter.persistent(); - _nssCatalogIdChanges = changesWriter.persistent(); - }); - - // Make sure untimestamped writes have a single entry in mapping. We move the single entry from - // 'from' to 'to'. We do not have to worry about mixing timestamped and untimestamped like - // _pushCatalogId. - if (!ts) { - // We should never perform rename in a mixed-mode environment. 'from' should contain a - // single entry and there should be nothing in 'to' . - invariant(fromIds.size() == 1); - invariant(toIds.empty()); - toIds.push_back(TimestampedCatalogId{fromIds.back().id, Timestamp::min()}); - fromIds.clear(); - return; - } - - // An entry could exist already if concurrent writes are performed, keep the latest change in - // that case. - if (!toIds.empty() && toIds.back().ts == *ts) { - toIds.back().id = fromIds.back().id; - } else { - invariant(toIds.empty() || toIds.back().ts < *ts); - toIds.push_back(TimestampedCatalogId{fromIds.back().id, *ts}); - _markForCatalogIdCleanupIfNeeded(to, changesWriter, toIds); - } - - // Re-write latest entry if timestamp match (multiple changes occured in this transaction), - // otherwise push at end - if (!fromIds.empty() && fromIds.back().ts == *ts) { - fromIds.back().id = boost::none; - } else { - invariant(fromIds.empty() || fromIds.back().ts < *ts); - fromIds.push_back(TimestampedCatalogId{boost::none, *ts}); - _markForCatalogIdCleanupIfNeeded(from, changesWriter, fromIds); - } -} - -void CollectionCatalog::_insertCatalogIdForNSSAndUUIDAfterScan( - boost::optional<const NamespaceString&> nss, - boost::optional<UUID> uuid, - boost::optional<RecordId> catalogId, - Timestamp ts) { - auto doInsert = [this, &catalogId, &ts](auto& catalogIdsContainer, - auto& catalogIdChangesContainer, - const auto& key) { - auto changesWriter = catalogIdChangesContainer.transient(); - auto ids = copyIfExists(catalogIdsContainer, key); - - // Helper to write updated id mapping back into container at scope exit - ScopeGuard scopedGuard([&] { - // Make sure we erase mapping for namespace or UUID if the list is left empty as - // lookups expect at least one entry for existing namespaces or UUIDs. - if (ids.empty()) { - catalogIdsContainer = catalogIdsContainer.erase(key); - } else { - catalogIdsContainer = catalogIdsContainer.set(key, std::move(ids)); - } - catalogIdChangesContainer = changesWriter.persistent(); - }); - - // Binary search for to the entry with same or larger timestamp - auto it = std::lower_bound( - ids.begin(), ids.end(), ts, [](const auto& entry, const Timestamp& ts) { - return entry.ts < ts; - }); - - // The logic of what we need to do differs whether we are inserting a valid catalogId or - // not. - if (catalogId) { - if (it != ids.end()) { - // An entry could exist already if concurrent writes are performed, keep the latest - // change in that case. - if (it->ts == ts) { - it->id = catalogId; - return; - } - - // If next element has same catalogId, we can adjust its timestamp to cover a longer - // range - if (it->id == catalogId) { - it->ts = ts; - _markForCatalogIdCleanupIfNeeded(key, changesWriter, ids); - return; - } - } - - // Otherwise insert new entry at timestamp - ids.insert(it, TimestampedCatalogId{catalogId, ts}); - _markForCatalogIdCleanupIfNeeded(key, changesWriter, ids); - return; - } - - // Avoid inserting missing mapping when the list has grown past the threshold. Will cause - // the system to fall back to scanning the durable catalog. - if (ids.size() >= kMaxCatalogIdMappingLengthForMissingInsert) { - return; - } - - if (it != ids.end() && it->ts == ts) { - // An entry could exist already if concurrent writes are performed, keep the latest - // change in that case. - it->id = boost::none; - } else { - // Otherwise insert new entry - it = ids.insert(it, TimestampedCatalogId{boost::none, ts}); - } - - // The iterator is positioned on the added/modified element above, reposition it to the next - // entry - ++it; - - // We don't want to assume that the namespace or UUID remains not existing until the next - // entry, as there can be times where the namespace or UUID actually does exist. To make - // sure we trigger the scanning of the durable catalog in this range we will insert a bogus - // entry using an invalid RecordId at the next timestamp. This will treat the range forward - // as unknown. - auto nextTs = ts + 1; - - // If the next entry is on the next timestamp already, we can skip adding the bogus entry. - // If this function is called for a previously unknown namespace or UUID, we may not have - // any future valid entries and the iterator would be positioned at and at this point. - if (it == ids.end() || it->ts != nextTs) { - ids.insert(it, TimestampedCatalogId{kUnknownRangeMarkerId, nextTs}); - } - - _markForCatalogIdCleanupIfNeeded(key, changesWriter, ids); - }; - - if (nss) { - doInsert(_nssCatalogIds, _nssCatalogIdChanges, *nss); - } - - if (uuid) { - doInsert(_uuidCatalogIds, _uuidCatalogIdChanges, *uuid); - } -} - -template <class Key, class CatalogIdChangesContainer> -void CollectionCatalog::_markForCatalogIdCleanupIfNeeded( - const Key& key, - CatalogIdChangesContainer& catalogIdChangesContainer, - const std::vector<TimestampedCatalogId>& ids) { - - auto markForCleanup = [this, &key, &catalogIdChangesContainer](Timestamp ts) { - catalogIdChangesContainer.insert(key); - if (ts < _lowestCatalogIdTimestampForCleanup) { - _lowestCatalogIdTimestampForCleanup = ts; - } - }; - - // Cleanup may occur if we have more than one entry for the namespace. - if (ids.size() > 1) { - // When we have multiple entries, use the time at the second entry as the cleanup time, - // when the oldest timestamp advances past this we no longer need the first entry. - markForCleanup(ids.at(1).ts); - } -} - void CollectionCatalog::deregisterAllCollectionsAndViews(ServiceContext* svcCtx) { LOGV2(20282, "Deregistering all the collections"); for (auto& entry : _catalog) { @@ -2495,141 +2174,6 @@ CollectionCatalog::iterator CollectionCatalog::end(OperationContext* opCtx) cons return iterator(opCtx, _orderedCollections.end(), *this); } -bool CollectionCatalog::needsCleanupForOldestTimestamp(Timestamp oldest) const { - return _lowestCatalogIdTimestampForCleanup <= oldest; -} - -void CollectionCatalog::cleanupForOldestTimestampAdvanced(Timestamp oldest) { - Timestamp nextLowestCleanupTimestamp = Timestamp::max(); - // Helper to calculate the smallest entry that needs to be kept and its timestamp - auto assignLowestCleanupTimestamp = [&nextLowestCleanupTimestamp](const auto& range) { - // The second entry is cleanup time as at that point the first entry is no longer needed. - // The input range have at a minimum two entries. - auto it = range.begin() + 1; - nextLowestCleanupTimestamp = std::min(nextLowestCleanupTimestamp, it->ts); - }; - - auto doCleanup = [this, &oldest, &assignLowestCleanupTimestamp]( - auto& catalogIdsContainer, auto& catalogIdChangesContainer) { - // Batch all changes together - auto ids = catalogIdsContainer.transient(); - auto changes = catalogIdChangesContainer.transient(); - - for (auto it = catalogIdChangesContainer.begin(), end = catalogIdChangesContainer.end(); - it != end;) { - auto range = ids[*it]; - - // Binary search for next larger timestamp - auto rangeIt = std::upper_bound( - range.begin(), range.end(), oldest, [](const auto& ts, const auto& entry) { - return ts < entry.ts; - }); - - // Continue if there is nothing to cleanup for this timestamp yet - if (rangeIt == range.begin()) { - // There should always be at least two entries in the range when we hit this - // branch. For the namespace to be put in '_nssCatalogIdChanges' we normally - // need at least two entries. The namespace could require cleanup with just a - // single entry if 'cleanupForCatalogReopen' leaves a single drop entry in the - // range. But because we cannot initialize the namespace with a single drop - // there must have been a non-drop entry earlier that got cleaned up in a - // previous call to 'cleanupForOldestTimestampAdvanced', which happens when the - // oldest timestamp advances past the drop timestamp. This guarantees that the - // oldest timestamp is larger than the timestamp in the single drop entry - // resulting in this branch cannot be taken when we only have a drop in the - // range. - invariant(range.size() > 1); - assignLowestCleanupTimestamp(range); - ++it; - continue; - } - - // The iterator is positioned to the closest entry that has a larger timestamp, - // decrement to get a lower or equal timestamp - --rangeIt; - - // Erase range, we will leave at least one element due to the decrement above - range.erase(range.begin(), rangeIt); - - // If more changes are needed for this namespace, keep it in the set and keep track - // of lowest timestamp. - if (range.size() > 1) { - assignLowestCleanupTimestamp(range); - ids.set(*it, std::move(range)); - ++it; - continue; - } - // If the last remaining element is a drop earlier than the oldest timestamp, we can - // remove tracking this namespace - if (range.back().id == boost::none) { - ids.erase(*it); - } else { - ids.set(*it, std::move(range)); - } - - // Unmark this namespace or UUID for needing changes. - changes.erase(*it); - ++it; - } - - // Write back all changes to main container - catalogIdChangesContainer = changes.persistent(); - catalogIdsContainer = ids.persistent(); - }; - - // Iterate over all namespaces and UUIDs that is marked that they need cleanup - doCleanup(_nssCatalogIds, _nssCatalogIdChanges); - doCleanup(_uuidCatalogIds, _uuidCatalogIdChanges); - - _lowestCatalogIdTimestampForCleanup = nextLowestCleanupTimestamp; - _oldestCatalogIdTimestampMaintained = std::max(_oldestCatalogIdTimestampMaintained, oldest); -} - -void CollectionCatalog::cleanupForCatalogReopen(Timestamp stable) { - _nssCatalogIdChanges = {}; - _uuidCatalogIdChanges = {}; - _lowestCatalogIdTimestampForCleanup = Timestamp::max(); - _oldestCatalogIdTimestampMaintained = std::min(_oldestCatalogIdTimestampMaintained, stable); - - auto removeLargerTimestamps = [this, &stable](auto& catalogIdsContainer, - auto& catalogIdChangesContainer) { - // Batch all changes together - auto idsWriter = catalogIdsContainer.transient(); - auto changesWriter = catalogIdChangesContainer.transient(); - - for (auto it = catalogIdsContainer.begin(); it != catalogIdsContainer.end();) { - auto ids = it->second; - - // Remove all larger timestamps in this range - ids.erase( - std::upper_bound(ids.begin(), - ids.end(), - stable, - [](Timestamp ts, const auto& entry) { return ts < entry.ts; }), - ids.end()); - - // Remove namespace or UUID if there are no entries left - if (ids.empty()) { - idsWriter.erase(it->first); - ++it; - continue; - } - - // Calculate when this namespace needs to be cleaned up next - _markForCatalogIdCleanupIfNeeded(it->first, changesWriter, ids); - idsWriter.set(it->first, std::move(ids)); - ++it; - } - - // Write back all changes to main container - catalogIdChangesContainer = changesWriter.persistent(); - catalogIdsContainer = idsWriter.persistent(); - }; - - removeLargerTimestamps(_nssCatalogIds, _nssCatalogIdChanges); - removeLargerTimestamps(_uuidCatalogIds, _uuidCatalogIdChanges); -} - void CollectionCatalog::invariantHasExclusiveAccessToCollection(OperationContext* opCtx, const NamespaceString& nss) { invariant(hasExclusiveAccessToCollection(opCtx, nss), nss.toStringForErrorMsg()); @@ -2668,6 +2212,13 @@ void CollectionCatalog::_replaceViewsForDatabase(const DatabaseName& dbName, _viewsForDatabase = _viewsForDatabase.set(dbName, std::move(views)); } +const HistoricalCatalogIdTracker& CollectionCatalog::catalogIdTracker() const { + return _catalogIdTracker; +} +HistoricalCatalogIdTracker& CollectionCatalog::catalogIdTracker() { + return _catalogIdTracker; +} + bool CollectionCatalog::_isCatalogBatchWriter() const { return ongoingBatchedWrite.load() && batchedCatalogWriteInstance.get() == this; } diff --git a/src/mongo/db/catalog/collection_catalog.h b/src/mongo/db/catalog/collection_catalog.h index 3a2f53f985e..265103f49f6 100644 --- a/src/mongo/db/catalog/collection_catalog.h +++ b/src/mongo/db/catalog/collection_catalog.h @@ -34,6 +34,7 @@ #include <set> #include "mongo/db/catalog/collection.h" +#include "mongo/db/catalog/historical_catalogid_tracker.h" #include "mongo/db/catalog/views_for_database.h" #include "mongo/db/database_name.h" #include "mongo/db/profile_filter.h" @@ -446,27 +447,6 @@ public: bool containsCollection(OperationContext* opCtx, const Collection* collection) const; /** - * Returns the CatalogId for a given 'nss' or 'uuid' at timestamp 'ts'. - */ - struct CatalogIdLookup { - enum class Existence { - // Namespace or UUID exists at time 'ts' and catalogId set in 'id'. - kExists, - // Namespace or UUID does not exist at time 'ts'. - kNotExists, - // Namespace or UUID existence at time 'ts' is unknown. The durable catalog must be - // scanned to determine. - kUnknown - }; - RecordId id; - Existence result; - }; - CatalogIdLookup lookupCatalogIdByNSS(const NamespaceString& nss, - boost::optional<Timestamp> ts = boost::none) const; - CatalogIdLookup lookupCatalogIdByUUID(const UUID& uuid, - boost::optional<Timestamp> ts = boost::none) const; - - /** * Iterates through the views in the catalog associated with database `dbName`, applying * 'callback' to each view. If the 'callback' returns false, the iterator exits early. * @@ -656,29 +636,19 @@ public: iterator end(OperationContext* opCtx) const; /** - * Checks if 'cleanupForOldestTimestampAdvanced' should be called when the oldest timestamp - * advanced. Used to avoid a potentially expensive call to 'cleanupForOldestTimestampAdvanced' - * if no write is needed. - */ - bool needsCleanupForOldestTimestamp(Timestamp oldest) const; - - /** - * Cleans up internal structures when the oldest timestamp advances - */ - void cleanupForOldestTimestampAdvanced(Timestamp oldest); - - /** - * Cleans up internal structures after catalog reopen - */ - void cleanupForCatalogReopen(Timestamp stable); - - /** * Ensures we have a MODE_X lock on a collection or MODE_IX lock for newly created collections. */ static void invariantHasExclusiveAccessToCollection(OperationContext* opCtx, const NamespaceString& nss); static bool hasExclusiveAccessToCollection(OperationContext* opCtx, const NamespaceString& nss); + /** + * Returns HistoricalCatalogIdTracker for historical namespace/uuid mappings to catalogId based + * on timestamp. + */ + const HistoricalCatalogIdTracker& catalogIdTracker() const; + HistoricalCatalogIdTracker& catalogIdTracker(); + private: friend class CollectionCatalog::iterator; class PublishCatalogUpdates; @@ -786,43 +756,6 @@ private: NamespaceType type) const; /** - * CatalogId with Timestamp - */ - struct TimestampedCatalogId { - boost::optional<RecordId> id; - Timestamp ts; - }; - - // Push a catalogId for namespace and UUID at given Timestamp. Timestamp needs to be larger than - // other entries for this namespace and UUID. boost::none for catalogId represent drop, - // boost::none for timestamp turns this operation into a no-op. - void _pushCatalogIdForNSSAndUUID(const NamespaceString& nss, - const UUID& uuid, - boost::optional<RecordId> catalogId, - boost::optional<Timestamp> ts); - - // Push a catalogId for 'from' and 'to' for a rename operation at given Timestamp. Timestamp - // needs to be larger than other entries for these namespaces. boost::none for timestamp turns - // this operation into a no-op. - void _pushCatalogIdForRename(const NamespaceString& from, - const NamespaceString& to, - boost::optional<Timestamp> ts); - - // Inserts a catalogId for namespace and UUID at given Timestamp, if not boost::none. Used after - // scanning the durable catalog for a correct mapping at the given timestamp. - void _insertCatalogIdForNSSAndUUIDAfterScan(boost::optional<const NamespaceString&> nss, - boost::optional<UUID> uuid, - boost::optional<RecordId> catalogId, - Timestamp ts); - - // Helper to calculate if a namespace or UUID needs to be marked for cleanup for a set of - // timestamped catalogIds - template <class Key, class CatalogIdChangesContainer> - void _markForCatalogIdCleanupIfNeeded(const Key& key, - CatalogIdChangesContainer& catalogIdChangesContainer, - const std::vector<TimestampedCatalogId>& ids); - - /** * Returns true if catalog information about this namespace or UUID should be looked up from the * durable catalog rather than using the in-memory state of the catalog. * @@ -857,12 +790,6 @@ private: const NamespaceStringOrUUID& nssOrUUID, Timestamp readTimestamp) const; - // Helpers for 'lookupCatalogIdByNSS' and 'lookupCatalogIdByUUID'. - CatalogIdLookup _checkWithOldestCatalogIdTimestampMaintained( - boost::optional<Timestamp> ts) const; - CatalogIdLookup _findCatalogIdInRange(boost::optional<Timestamp> ts, - const std::vector<TimestampedCatalogId>& range) const; - /** * When present, indicates that the catalog is in closed state, and contains a map from UUID * to pre-close NSS. See also onCloseCatalog. @@ -890,21 +817,8 @@ private: immutable::unordered_map<NamespaceString, std::shared_ptr<Collection>> _pendingCommitNamespaces; immutable::unordered_map<UUID, std::shared_ptr<Collection>, UUID::Hash> _pendingCommitUUIDs; - // CatalogId mappings for all known namespaces and UUIDs for the CollectionCatalog. The vector - // is sorted on timestamp. UUIDs will have at most two entries. One for the create and another - // for the drop. UUIDs stay the same across collection renames. - immutable::unordered_map<NamespaceString, std::vector<TimestampedCatalogId>> _nssCatalogIds; - immutable::unordered_map<UUID, std::vector<TimestampedCatalogId>, UUID::Hash> _uuidCatalogIds; - // Set of namespaces and UUIDs that need cleanup when the oldest timestamp advances - // sufficiently. - immutable::unordered_set<NamespaceString> _nssCatalogIdChanges; - immutable::unordered_set<UUID, UUID::Hash> _uuidCatalogIdChanges; - // Point at which the oldest timestamp need to advance for there to be any catalogId namespace - // that can be cleaned up - Timestamp _lowestCatalogIdTimestampForCleanup = Timestamp::max(); - // The oldest timestamp at which the catalog maintains catalogId mappings. Anything older than - // this is unknown and must be discovered by scanning the durable catalog. - Timestamp _oldestCatalogIdTimestampMaintained = Timestamp::max(); + // Provides functionality to lookup catalogId by namespace/uuid for a given timestamp. + HistoricalCatalogIdTracker _catalogIdTracker; // Map of database names to their corresponding views and other associated state. ViewsForDatabaseMap _viewsForDatabase; diff --git a/src/mongo/db/catalog/collection_catalog_test.cpp b/src/mongo/db/catalog/collection_catalog_test.cpp index 0d8cba73d7c..7533a220c1b 100644 --- a/src/mongo/db/catalog/collection_catalog_test.cpp +++ b/src/mongo/db/catalog/collection_catalog_test.cpp @@ -889,19 +889,6 @@ public: return uuid; } - CollectionCatalog::CatalogIdLookup lookupCatalogId(const NamespaceString& nss, - const UUID& uuid, - boost::optional<Timestamp> ts) { - // Verify that lookups and NSS and UUID yield the same result. - CollectionCatalog::CatalogIdLookup nssLookup = catalog()->lookupCatalogIdByNSS(nss, ts); - CollectionCatalog::CatalogIdLookup uuidLookup = catalog()->lookupCatalogIdByUUID(uuid, ts); - - ASSERT_EQ(nssLookup.result, uuidLookup.result); - ASSERT_EQ(nssLookup.id, uuidLookup.id); - - return nssLookup; - } - void dropCollection(OperationContext* opCtx, const NamespaceString& nss, Timestamp timestamp) { _setupDDLOperation(opCtx, timestamp); WriteUnitOfWork wuow(opCtx); @@ -2128,713 +2115,6 @@ TEST_F(CollectionCatalogTimestampTest, OpenNewCollectionAndIndexesWithReaper) { } } -TEST_F(CollectionCatalogTimestampTest, CatalogIdMappingCreate) { - NamespaceString nss = NamespaceString::createNamespaceString_forTest("a.b"); - - // Initialize the oldest timestamp to (1, 1) - CollectionCatalog::write(opCtx.get(), [](CollectionCatalog& catalog) { - catalog.cleanupForOldestTimestampAdvanced(Timestamp(1, 1)); - }); - - // Create collection and extract the catalogId - UUID uuid = createCollection(opCtx.get(), nss, Timestamp(1, 2)); - RecordId rid = catalog()->lookupCollectionByNamespace(opCtx.get(), nss)->getCatalogId(); - - // Lookup without timestamp returns latest catalogId - ASSERT_EQ(lookupCatalogId(nss, uuid, boost::none).id, rid); - // Lookup before create returns unknown if looking before oldest - ASSERT_EQ(lookupCatalogId(nss, uuid, Timestamp(1, 0)).result, - CollectionCatalog::CatalogIdLookup::Existence::kUnknown); - // Lookup before create returns not exists if looking after oldest - ASSERT_EQ(lookupCatalogId(nss, uuid, Timestamp(1, 1)).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); - // Lookup at create returns catalogId - ASSERT_EQ(lookupCatalogId(nss, uuid, Timestamp(1, 2)).id, rid); - // Lookup after create returns catalogId - ASSERT_EQ(lookupCatalogId(nss, uuid, Timestamp(1, 3)).id, rid); -} - -TEST_F(CollectionCatalogTimestampTest, CatalogIdMappingDrop) { - NamespaceString nss = NamespaceString::createNamespaceString_forTest("a.b"); - - // Initialize the oldest timestamp to (1, 1) - CollectionCatalog::write(opCtx.get(), [](CollectionCatalog& catalog) { - catalog.cleanupForOldestTimestampAdvanced(Timestamp(1, 1)); - }); - - // Create and drop collection. We have a time window where the namespace exists - UUID uuid = createCollection(opCtx.get(), nss, Timestamp(1, 5)); - RecordId rid = catalog()->lookupCollectionByNamespace(opCtx.get(), nss)->getCatalogId(); - dropCollection(opCtx.get(), nss, Timestamp(1, 10)); - - // Lookup without timestamp returns none - ASSERT_EQ(lookupCatalogId(nss, uuid, boost::none).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); - // Lookup before create and oldest returns unknown - ASSERT_EQ(lookupCatalogId(nss, uuid, Timestamp(1, 0)).result, - CollectionCatalog::CatalogIdLookup::Existence::kUnknown); - // Lookup before create returns not exists - ASSERT_EQ(lookupCatalogId(nss, uuid, Timestamp(1, 4)).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); - // Lookup at create returns catalogId - ASSERT_EQ(lookupCatalogId(nss, uuid, Timestamp(1, 5)).id, rid); - // Lookup after create returns catalogId - ASSERT_EQ(lookupCatalogId(nss, uuid, Timestamp(1, 6)).id, rid); - // Lookup at drop returns none - ASSERT_EQ(lookupCatalogId(nss, uuid, Timestamp(1, 10)).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); - // Lookup after drop returns none - ASSERT_EQ(lookupCatalogId(nss, uuid, Timestamp(1, 20)).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); -} - -TEST_F(CollectionCatalogTimestampTest, CatalogIdMappingRename) { - NamespaceString from = NamespaceString::createNamespaceString_forTest("a.b"); - NamespaceString to = NamespaceString::createNamespaceString_forTest("a.c"); - - // Initialize the oldest timestamp to (1, 1) - CollectionCatalog::write(opCtx.get(), [](CollectionCatalog& catalog) { - catalog.cleanupForOldestTimestampAdvanced(Timestamp(1, 1)); - }); - - // Create and rename collection. We have two windows where the collection exists but for - // different namespaces - UUID uuid = createCollection(opCtx.get(), from, Timestamp(1, 5)); - RecordId rid = catalog()->lookupCollectionByNamespace(opCtx.get(), from)->getCatalogId(); - renameCollection(opCtx.get(), from, to, Timestamp(1, 10)); - - // Lookup without timestamp on 'from' returns none. By 'uuid' returns catalogId - ASSERT_EQ(catalog()->lookupCatalogIdByNSS(from, boost::none).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); - ASSERT_EQ(catalog()->lookupCatalogIdByUUID(uuid, boost::none).id, rid); - // Lookup before create and oldest returns unknown - ASSERT_EQ(lookupCatalogId(from, uuid, Timestamp(1, 0)).result, - CollectionCatalog::CatalogIdLookup::Existence::kUnknown); - // Lookup before create returns not exists - ASSERT_EQ(lookupCatalogId(from, uuid, Timestamp(1, 4)).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); - // Lookup at create returns catalogId - ASSERT_EQ(lookupCatalogId(from, uuid, Timestamp(1, 5)).id, rid); - // Lookup after create returns catalogId - ASSERT_EQ(lookupCatalogId(from, uuid, Timestamp(1, 6)).id, rid); - // Lookup at rename on 'from' returns none. By 'uuid' returns catalogId - ASSERT_EQ(catalog()->lookupCatalogIdByNSS(from, Timestamp(1, 10)).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); - ASSERT_EQ(catalog()->lookupCatalogIdByUUID(uuid, Timestamp(1, 10)).id, rid); - // Lookup after rename on 'from' returns none. By 'uuid' returns catalogId - ASSERT_EQ(catalog()->lookupCatalogIdByNSS(from, Timestamp(1, 20)).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); - ASSERT_EQ(catalog()->lookupCatalogIdByUUID(uuid, Timestamp(1, 20)).id, rid); - - // Lookup without timestamp on 'to' returns catalogId - ASSERT_EQ(lookupCatalogId(to, uuid, boost::none).id, rid); - // Lookup before rename and oldest on 'to' returns unknown - ASSERT_EQ(lookupCatalogId(to, uuid, Timestamp(1, 0)).result, - CollectionCatalog::CatalogIdLookup::Existence::kUnknown); - // Lookup before rename on 'to' returns not exists. By 'uuid' returns catalogId - ASSERT_EQ(catalog()->lookupCatalogIdByNSS(to, Timestamp(1, 9)).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); - ASSERT_EQ(catalog()->lookupCatalogIdByUUID(uuid, Timestamp(1, 9)).id, rid); - // Lookup at rename on 'to' returns catalogId - ASSERT_EQ(lookupCatalogId(to, uuid, Timestamp(1, 10)).id, rid); - // Lookup after rename on 'to' returns catalogId - ASSERT_EQ(lookupCatalogId(to, uuid, Timestamp(1, 20)).id, rid); -} - -TEST_F(CollectionCatalogTimestampTest, CatalogIdMappingRenameDropTarget) { - NamespaceString from = NamespaceString::createNamespaceString_forTest("a.b"); - NamespaceString to = NamespaceString::createNamespaceString_forTest("a.c"); - - // Initialize the oldest timestamp to (1, 1) - CollectionCatalog::write(opCtx.get(), [](CollectionCatalog& catalog) { - catalog.cleanupForOldestTimestampAdvanced(Timestamp(1, 1)); - }); - - // Create collections. The 'to' namespace will exist for one collection from Timestamp(1, 6) - // until it is dropped by the rename at Timestamp(1, 10), after which the 'to' namespace will - // correspond to the renamed collection. - UUID uuid = createCollection(opCtx.get(), from, Timestamp(1, 5)); - UUID originalUUID = createCollection(opCtx.get(), to, Timestamp(1, 6)); - RecordId rid = catalog()->lookupCollectionByNamespace(opCtx.get(), from)->getCatalogId(); - RecordId originalToRid = - catalog()->lookupCollectionByNamespace(opCtx.get(), to)->getCatalogId(); - renameCollection(opCtx.get(), from, to, Timestamp(1, 10)); - - // Lookup without timestamp on 'to' and 'uuid' returns latest catalog id. By 'originalUUID' - // returns not exists as the target was dropped. - ASSERT_EQ(lookupCatalogId(to, uuid, boost::none).id, rid); - ASSERT_EQ(catalog()->lookupCatalogIdByUUID(originalUUID, boost::none).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); - // Lookup before rename and oldest on 'to' returns unknown - ASSERT_EQ(lookupCatalogId(to, uuid, Timestamp(1, 0)).result, - CollectionCatalog::CatalogIdLookup::Existence::kUnknown); - ASSERT_EQ(lookupCatalogId(to, originalUUID, Timestamp(1, 0)).result, - CollectionCatalog::CatalogIdLookup::Existence::kUnknown); - // Lookup before rename on 'to' returns the original rid - ASSERT_EQ(lookupCatalogId(to, originalUUID, Timestamp(1, 9)).id, originalToRid); - // Lookup before rename on 'from' returns the rid - ASSERT_EQ(lookupCatalogId(from, uuid, Timestamp(1, 9)).id, rid); - // Lookup at rename timestamp on 'to' and 'uuid' returns catalogId - ASSERT_EQ(lookupCatalogId(to, uuid, Timestamp(1, 10)).id, rid); - // Lookup at rename timestamp on 'originalUUID' returns not exists as it was dropped during the - // rename. - ASSERT_EQ(catalog()->lookupCatalogIdByUUID(originalUUID, Timestamp(1, 10)).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); - // Lookup after rename on 'to' and 'uuid' returns catalogId - ASSERT_EQ(lookupCatalogId(to, uuid, Timestamp(1, 20)).id, rid); - // Lookup after rename timestamp on 'originalUUID' returns not exists as it was dropped during - // the rename. - ASSERT_EQ(catalog()->lookupCatalogIdByUUID(originalUUID, Timestamp(1, 20)).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); -} - -TEST_F(CollectionCatalogTimestampTest, CatalogIdMappingDropCreate) { - NamespaceString nss = NamespaceString::createNamespaceString_forTest("a.b"); - - // Create, drop and recreate collection on the same namespace. We have different catalogId. - UUID firstUUID = createCollection(opCtx.get(), nss, Timestamp(1, 5)); - RecordId rid1 = catalog()->lookupCollectionByNamespace(opCtx.get(), nss)->getCatalogId(); - dropCollection(opCtx.get(), nss, Timestamp(1, 10)); - UUID secondUUID = createCollection(opCtx.get(), nss, Timestamp(1, 15)); - RecordId rid2 = catalog()->lookupCollectionByNamespace(opCtx.get(), nss)->getCatalogId(); - - // Lookup without timestamp returns latest catalogId - ASSERT_EQ(lookupCatalogId(nss, secondUUID, boost::none).id, rid2); - ASSERT_EQ(catalog()->lookupCatalogIdByUUID(firstUUID, boost::none).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); - // Lookup before first create returns not exists - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 4)).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); - ASSERT_EQ(lookupCatalogId(nss, secondUUID, Timestamp(1, 4)).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); - // Lookup at first create returns first catalogId - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 5)).id, rid1); - ASSERT_EQ(catalog()->lookupCatalogIdByUUID(secondUUID, Timestamp(1, 5)).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); - // Lookup after first create returns first catalogId - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 6)).id, rid1); - ASSERT_EQ(catalog()->lookupCatalogIdByUUID(secondUUID, Timestamp(1, 6)).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); - // Lookup at drop returns none - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 10)).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); - ASSERT_EQ(lookupCatalogId(nss, secondUUID, Timestamp(1, 10)).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); - // Lookup after drop returns none - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 13)).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); - ASSERT_EQ(lookupCatalogId(nss, secondUUID, Timestamp(1, 13)).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); - // Lookup at second create returns second catalogId - ASSERT_EQ(lookupCatalogId(nss, secondUUID, Timestamp(1, 15)).id, rid2); - ASSERT_EQ(catalog()->lookupCatalogIdByUUID(firstUUID, Timestamp(1, 15)).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); - // Lookup after second create returns second catalogId - ASSERT_EQ(lookupCatalogId(nss, secondUUID, Timestamp(1, 20)).id, rid2); - ASSERT_EQ(catalog()->lookupCatalogIdByUUID(firstUUID, Timestamp(1, 20)).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); -} - -TEST_F(CollectionCatalogTimestampTest, CatalogIdMappingCleanupEqDrop) { - NamespaceString nss = NamespaceString::createNamespaceString_forTest("a.b"); - - // Create collection and verify we have nothing to cleanup - UUID firstUUID = createCollection(opCtx.get(), nss, Timestamp(1, 5)); - ASSERT_FALSE(catalog()->needsCleanupForOldestTimestamp(Timestamp(1, 1))); - - // Drop collection and verify we have nothing to cleanup as long as the oldest timestamp is - // before the drop - dropCollection(opCtx.get(), nss, Timestamp(1, 10)); - ASSERT_FALSE(catalog()->needsCleanupForOldestTimestamp(Timestamp(1, 1))); - ASSERT_FALSE(catalog()->needsCleanupForOldestTimestamp(Timestamp(1, 5))); - ASSERT_TRUE(catalog()->needsCleanupForOldestTimestamp(Timestamp(1, 10))); - - // Create new collection and nothing changed with answers to needsCleanupForOldestTimestamp. - UUID secondUUID = createCollection(opCtx.get(), nss, Timestamp(1, 15)); - ASSERT_FALSE(catalog()->needsCleanupForOldestTimestamp(Timestamp(1, 1))); - ASSERT_FALSE(catalog()->needsCleanupForOldestTimestamp(Timestamp(1, 5))); - ASSERT_FALSE(catalog()->needsCleanupForOldestTimestamp(Timestamp(1, 7))); - ASSERT_TRUE(catalog()->needsCleanupForOldestTimestamp(Timestamp(1, 10))); - - // We can lookup the old catalogId before we advance the oldest timestamp and cleanup - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 5)).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - ASSERT_EQ(catalog()->lookupCatalogIdByUUID(secondUUID, Timestamp(1, 5)).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); - - // Cleanup at drop timestamp - CollectionCatalog::write(opCtx.get(), [&](CollectionCatalog& c) { - c.cleanupForOldestTimestampAdvanced(Timestamp(1, 10)); - }); - // After cleanup, we cannot find the old catalogId anymore. Also verify that we don't need - // anymore cleanup - ASSERT_FALSE(catalog()->needsCleanupForOldestTimestamp(Timestamp(1, 10))); - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 5)).result, - CollectionCatalog::CatalogIdLookup::Existence::kUnknown); - ASSERT_EQ(lookupCatalogId(nss, secondUUID, Timestamp(1, 5)).result, - CollectionCatalog::CatalogIdLookup::Existence::kUnknown); - ASSERT_EQ(lookupCatalogId(nss, secondUUID, Timestamp(1, 15)).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - ASSERT_EQ(catalog()->lookupCatalogIdByUUID(firstUUID, Timestamp(1, 15)).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); -} - -TEST_F(CollectionCatalogTimestampTest, CatalogIdMappingCleanupGtDrop) { - NamespaceString nss = NamespaceString::createNamespaceString_forTest("a.b"); - - // Create collection and verify we have nothing to cleanup - UUID firstUUID = createCollection(opCtx.get(), nss, Timestamp(1, 5)); - ASSERT_FALSE(catalog()->needsCleanupForOldestTimestamp(Timestamp(1, 1))); - - // Drop collection and verify we have nothing to cleanup as long as the oldest timestamp is - // before the drop - dropCollection(opCtx.get(), nss, Timestamp(1, 10)); - ASSERT_FALSE(catalog()->needsCleanupForOldestTimestamp(Timestamp(1, 1))); - ASSERT_FALSE(catalog()->needsCleanupForOldestTimestamp(Timestamp(1, 5))); - ASSERT_TRUE(catalog()->needsCleanupForOldestTimestamp(Timestamp(1, 10))); - - // Create new collection and nothing changed with answers to needsCleanupForOldestTimestamp. - UUID secondUUID = createCollection(opCtx.get(), nss, Timestamp(1, 15)); - ASSERT_FALSE(catalog()->needsCleanupForOldestTimestamp(Timestamp(1, 1))); - ASSERT_FALSE(catalog()->needsCleanupForOldestTimestamp(Timestamp(1, 5))); - ASSERT_FALSE(catalog()->needsCleanupForOldestTimestamp(Timestamp(1, 7))); - ASSERT_TRUE(catalog()->needsCleanupForOldestTimestamp(Timestamp(1, 12))); - - // We can lookup the old catalogId before we advance the oldest timestamp and cleanup - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 5)).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - ASSERT_EQ(catalog()->lookupCatalogIdByUUID(secondUUID, Timestamp(1, 5)).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); - - // Cleanup after the drop timestamp - CollectionCatalog::write(opCtx.get(), [&](CollectionCatalog& c) { - c.cleanupForOldestTimestampAdvanced(Timestamp(1, 12)); - }); - - // After cleanup, we cannot find the old catalogId anymore. Also verify that we don't need - // anymore cleanup - ASSERT_FALSE(catalog()->needsCleanupForOldestTimestamp(Timestamp(1, 12))); - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 5)).result, - CollectionCatalog::CatalogIdLookup::Existence::kUnknown); - ASSERT_EQ(lookupCatalogId(nss, secondUUID, Timestamp(1, 5)).result, - CollectionCatalog::CatalogIdLookup::Existence::kUnknown); - ASSERT_EQ(lookupCatalogId(nss, secondUUID, Timestamp(1, 15)).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - ASSERT_EQ(catalog()->lookupCatalogIdByUUID(firstUUID, Timestamp(1, 15)).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); -} - -TEST_F(CollectionCatalogTimestampTest, CatalogIdMappingCleanupGtRecreate) { - NamespaceString nss = NamespaceString::createNamespaceString_forTest("a.b"); - - // Create collection and verify we have nothing to cleanup - UUID firstUUID = createCollection(opCtx.get(), nss, Timestamp(1, 5)); - ASSERT_FALSE(catalog()->needsCleanupForOldestTimestamp(Timestamp(1, 1))); - - // Drop collection and verify we have nothing to cleanup as long as the oldest timestamp is - // before the drop - dropCollection(opCtx.get(), nss, Timestamp(1, 10)); - ASSERT_FALSE(catalog()->needsCleanupForOldestTimestamp(Timestamp(1, 1))); - ASSERT_FALSE(catalog()->needsCleanupForOldestTimestamp(Timestamp(1, 5))); - ASSERT_TRUE(catalog()->needsCleanupForOldestTimestamp(Timestamp(1, 10))); - - // Create new collection and nothing changed with answers to needsCleanupForOldestTimestamp. - UUID secondUUID = createCollection(opCtx.get(), nss, Timestamp(1, 15)); - ASSERT_FALSE(catalog()->needsCleanupForOldestTimestamp(Timestamp(1, 1))); - ASSERT_FALSE(catalog()->needsCleanupForOldestTimestamp(Timestamp(1, 5))); - ASSERT_FALSE(catalog()->needsCleanupForOldestTimestamp(Timestamp(1, 7))); - ASSERT_TRUE(catalog()->needsCleanupForOldestTimestamp(Timestamp(1, 20))); - - // We can lookup the old catalogId before we advance the oldest timestamp and cleanup - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 5)).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - ASSERT_EQ(catalog()->lookupCatalogIdByUUID(secondUUID, Timestamp(1, 5)).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); - - // Cleanup after the recreate timestamp - CollectionCatalog::write(opCtx.get(), [&](CollectionCatalog& c) { - c.cleanupForOldestTimestampAdvanced(Timestamp(1, 20)); - }); - - // After cleanup, we cannot find the old catalogId anymore. Also verify that we don't need - // anymore cleanup - ASSERT_FALSE(catalog()->needsCleanupForOldestTimestamp(Timestamp(1, 20))); - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 5)).result, - CollectionCatalog::CatalogIdLookup::Existence::kUnknown); - ASSERT_EQ(lookupCatalogId(nss, secondUUID, Timestamp(1, 5)).result, - CollectionCatalog::CatalogIdLookup::Existence::kUnknown); - ASSERT_EQ(lookupCatalogId(nss, secondUUID, Timestamp(1, 15)).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - ASSERT_EQ(catalog()->lookupCatalogIdByUUID(firstUUID, Timestamp(1, 15)).result, - CollectionCatalog::CatalogIdLookup::Existence::kUnknown); -} - -TEST_F(CollectionCatalogTimestampTest, CatalogIdMappingCleanupMultiple) { - NamespaceString nss = NamespaceString::createNamespaceString_forTest("a.b"); - - // Create and drop multiple namespace on the same namespace - UUID firstUUID = createCollection(opCtx.get(), nss, Timestamp(1, 5)); - dropCollection(opCtx.get(), nss, Timestamp(1, 10)); - UUID secondUUID = createCollection(opCtx.get(), nss, Timestamp(1, 15)); - dropCollection(opCtx.get(), nss, Timestamp(1, 20)); - UUID thirdUUID = createCollection(opCtx.get(), nss, Timestamp(1, 25)); - dropCollection(opCtx.get(), nss, Timestamp(1, 30)); - UUID fourthUUID = createCollection(opCtx.get(), nss, Timestamp(1, 35)); - dropCollection(opCtx.get(), nss, Timestamp(1, 40)); - - // Lookup can find all four collections - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 5)).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - ASSERT_EQ(lookupCatalogId(nss, secondUUID, Timestamp(1, 15)).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - ASSERT_EQ(lookupCatalogId(nss, thirdUUID, Timestamp(1, 25)).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - ASSERT_EQ(lookupCatalogId(nss, fourthUUID, Timestamp(1, 35)).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - - // Cleanup oldest - CollectionCatalog::write(opCtx.get(), [&](CollectionCatalog& c) { - c.cleanupForOldestTimestampAdvanced(Timestamp(1, 10)); - }); - - // Lookup can find the three remaining collections - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 5)).result, - CollectionCatalog::CatalogIdLookup::Existence::kUnknown); - ASSERT_EQ(lookupCatalogId(nss, secondUUID, Timestamp(1, 15)).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - ASSERT_EQ(lookupCatalogId(nss, thirdUUID, Timestamp(1, 25)).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - ASSERT_EQ(lookupCatalogId(nss, fourthUUID, Timestamp(1, 35)).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - - // Cleanup - CollectionCatalog::write(opCtx.get(), [&](CollectionCatalog& c) { - c.cleanupForOldestTimestampAdvanced(Timestamp(1, 21)); - }); - - // Lookup can find the two remaining collections - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 5)).result, - CollectionCatalog::CatalogIdLookup::Existence::kUnknown); - ASSERT_EQ(lookupCatalogId(nss, secondUUID, Timestamp(1, 15)).result, - CollectionCatalog::CatalogIdLookup::Existence::kUnknown); - ASSERT_EQ(lookupCatalogId(nss, thirdUUID, Timestamp(1, 25)).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - ASSERT_EQ(lookupCatalogId(nss, fourthUUID, Timestamp(1, 35)).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - - // Cleanup - CollectionCatalog::write(opCtx.get(), [&](CollectionCatalog& c) { - c.cleanupForOldestTimestampAdvanced(Timestamp(1, 32)); - }); - - // Lookup can find the last remaining collections - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 5)).result, - CollectionCatalog::CatalogIdLookup::Existence::kUnknown); - ASSERT_EQ(lookupCatalogId(nss, secondUUID, Timestamp(1, 15)).result, - CollectionCatalog::CatalogIdLookup::Existence::kUnknown); - ASSERT_EQ(lookupCatalogId(nss, thirdUUID, Timestamp(1, 25)).result, - CollectionCatalog::CatalogIdLookup::Existence::kUnknown); - ASSERT_EQ(lookupCatalogId(nss, fourthUUID, Timestamp(1, 35)).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - - // Cleanup - CollectionCatalog::write(opCtx.get(), [&](CollectionCatalog& c) { - c.cleanupForOldestTimestampAdvanced(Timestamp(1, 50)); - }); - - // Lookup now result in unknown as the oldest timestamp has advanced where mapping has been - // removed - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 5)).result, - CollectionCatalog::CatalogIdLookup::Existence::kUnknown); - ASSERT_EQ(lookupCatalogId(nss, secondUUID, Timestamp(1, 15)).result, - CollectionCatalog::CatalogIdLookup::Existence::kUnknown); - ASSERT_EQ(lookupCatalogId(nss, thirdUUID, Timestamp(1, 25)).result, - CollectionCatalog::CatalogIdLookup::Existence::kUnknown); - ASSERT_EQ(lookupCatalogId(nss, fourthUUID, Timestamp(1, 35)).result, - CollectionCatalog::CatalogIdLookup::Existence::kUnknown); -} - -TEST_F(CollectionCatalogTimestampTest, CatalogIdMappingCleanupMultipleSingleCall) { - NamespaceString nss = NamespaceString::createNamespaceString_forTest("a.b"); - - // Create and drop multiple namespace on the same namespace - UUID firstUUID = createCollection(opCtx.get(), nss, Timestamp(1, 5)); - dropCollection(opCtx.get(), nss, Timestamp(1, 10)); - UUID secondUUID = createCollection(opCtx.get(), nss, Timestamp(1, 15)); - dropCollection(opCtx.get(), nss, Timestamp(1, 20)); - UUID thirdUUID = createCollection(opCtx.get(), nss, Timestamp(1, 25)); - dropCollection(opCtx.get(), nss, Timestamp(1, 30)); - UUID fourthUUID = createCollection(opCtx.get(), nss, Timestamp(1, 35)); - dropCollection(opCtx.get(), nss, Timestamp(1, 40)); - - // Lookup can find all four collections - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 5)).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - ASSERT_EQ(lookupCatalogId(nss, secondUUID, Timestamp(1, 15)).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - ASSERT_EQ(lookupCatalogId(nss, thirdUUID, Timestamp(1, 25)).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - ASSERT_EQ(lookupCatalogId(nss, fourthUUID, Timestamp(1, 35)).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - - // Cleanup all - CollectionCatalog::write(opCtx.get(), [&](CollectionCatalog& c) { - c.cleanupForOldestTimestampAdvanced(Timestamp(1, 50)); - }); - - // Lookup now result in unknown as the oldest timestamp has advanced where mapping has been - // removed - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 5)).result, - CollectionCatalog::CatalogIdLookup::Existence::kUnknown); - ASSERT_EQ(lookupCatalogId(nss, secondUUID, Timestamp(1, 15)).result, - CollectionCatalog::CatalogIdLookup::Existence::kUnknown); - ASSERT_EQ(lookupCatalogId(nss, thirdUUID, Timestamp(1, 25)).result, - CollectionCatalog::CatalogIdLookup::Existence::kUnknown); - ASSERT_EQ(lookupCatalogId(nss, fourthUUID, Timestamp(1, 35)).result, - CollectionCatalog::CatalogIdLookup::Existence::kUnknown); -} - -TEST_F(CollectionCatalogTimestampTest, CatalogIdMappingRollback) { - NamespaceString a = NamespaceString::createNamespaceString_forTest("b.a"); - NamespaceString b = NamespaceString::createNamespaceString_forTest("b.b"); - NamespaceString c = NamespaceString::createNamespaceString_forTest("b.c"); - NamespaceString d = NamespaceString::createNamespaceString_forTest("b.d"); - NamespaceString e = NamespaceString::createNamespaceString_forTest("b.e"); - - // Create and drop multiple namespace on the same namespace - UUID firstUUID = createCollection(opCtx.get(), a, Timestamp(1, 1)); - dropCollection(opCtx.get(), a, Timestamp(1, 2)); - UUID secondUUID = createCollection(opCtx.get(), a, Timestamp(1, 3)); - UUID thirdUUID = createCollection(opCtx.get(), b, Timestamp(1, 5)); - UUID fourthUUID = createCollection(opCtx.get(), c, Timestamp(1, 7)); - UUID fifthUUID = createCollection(opCtx.get(), d, Timestamp(1, 8)); - UUID sixthUUID = createCollection(opCtx.get(), e, Timestamp(1, 9)); - dropCollection(opCtx.get(), b, Timestamp(1, 10)); - - // Rollback to Timestamp(1, 8) - CollectionCatalog::write( - opCtx.get(), [&](CollectionCatalog& c) { c.cleanupForCatalogReopen(Timestamp(1, 8)); }); - - ASSERT_EQ(lookupCatalogId(e, firstUUID, boost::none).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); - ASSERT_EQ(lookupCatalogId(a, secondUUID, boost::none).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - ASSERT_EQ(lookupCatalogId(b, thirdUUID, boost::none).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - ASSERT_EQ(lookupCatalogId(c, fourthUUID, boost::none).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - ASSERT_EQ(lookupCatalogId(d, fifthUUID, boost::none).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - ASSERT_EQ(lookupCatalogId(e, sixthUUID, boost::none).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); -} - -TEST_F(CollectionCatalogTimestampTest, CatalogIdMappingInsert) { - NamespaceString nss = NamespaceString::createNamespaceString_forTest("a.b"); - - // Create a collection on the namespace - UUID firstUUID = createCollection(opCtx.get(), nss, Timestamp(1, 10)); - dropCollection(opCtx.get(), nss, Timestamp(1, 20)); - UUID secondUUID = createCollection(opCtx.get(), nss, Timestamp(1, 30)); - - auto rid1 = lookupCatalogId(nss, firstUUID, Timestamp(1, 10)).id; - auto rid2 = lookupCatalogId(nss, secondUUID, Timestamp(1, 30)).id; - - // Simulate startup where we have a range [oldest, stable] by creating and dropping collections - // and then advancing the oldest timestamp and then reading behind it. - CollectionCatalog::write(opCtx.get(), [](CollectionCatalog& catalog) { - catalog.cleanupForOldestTimestampAdvanced(Timestamp(1, 40)); - }); - - // Confirm that the mappings have been cleaned up - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 15)).result, - CollectionCatalog::CatalogIdLookup::Existence::kUnknown); - ASSERT_EQ(lookupCatalogId(nss, secondUUID, Timestamp(1, 15)).result, - CollectionCatalog::CatalogIdLookup::Existence::kUnknown); - - { - OneOffRead oor(opCtx.get(), Timestamp(1, 17)); - Lock::GlobalLock globalLock(opCtx.get(), MODE_IS); - CollectionCatalog::get(opCtx.get()) - ->establishConsistentCollection(opCtx.get(), nss, Timestamp(1, 17)); - CollectionCatalog::get(opCtx.get()) - ->establishConsistentCollection( - opCtx.get(), {nss.dbName(), firstUUID}, Timestamp(1, 17)); - CollectionCatalog::get(opCtx.get()) - ->establishConsistentCollection( - opCtx.get(), {nss.dbName(), secondUUID}, Timestamp(1, 17)); - - // Lookups before the inserted timestamp is still unknown - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 11)).result, - CollectionCatalog::CatalogIdLookup::Existence::kUnknown); - ASSERT_EQ(lookupCatalogId(nss, secondUUID, Timestamp(1, 11)).result, - CollectionCatalog::CatalogIdLookup::Existence::kUnknown); - - // Lookups at or after the inserted timestamp is found, even if they don't match with WT - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 17)).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 17)).id, rid1); - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 19)).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 19)).id, rid1); - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 25)).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 25)).id, rid1); - // The entry at Timestamp(1, 30) is unaffected - ASSERT_EQ(lookupCatalogId(nss, secondUUID, Timestamp(1, 30)).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - ASSERT_EQ(lookupCatalogId(nss, secondUUID, Timestamp(1, 30)).id, rid2); - } - - { - OneOffRead oor(opCtx.get(), Timestamp(1, 12)); - Lock::GlobalLock globalLock(opCtx.get(), MODE_IS); - - CollectionCatalog::get(opCtx.get()) - ->establishConsistentCollection(opCtx.get(), nss, Timestamp(1, 12)); - CollectionCatalog::get(opCtx.get()) - ->establishConsistentCollection( - opCtx.get(), {nss.dbName(), firstUUID}, Timestamp(1, 12)); - CollectionCatalog::get(opCtx.get()) - ->establishConsistentCollection( - opCtx.get(), {nss.dbName(), secondUUID}, Timestamp(1, 12)); - - // We should now have extended the range from Timestamp(1, 17) to Timestamp(1, 12) - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 12)).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 12)).id, rid1); - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 16)).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 16)).id, rid1); - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 17)).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 17)).id, rid1); - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 19)).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 19)).id, rid1); - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 25)).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 25)).id, rid1); - // The entry at Timestamp(1, 30) is unaffected - ASSERT_EQ(lookupCatalogId(nss, secondUUID, Timestamp(1, 30)).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - ASSERT_EQ(lookupCatalogId(nss, secondUUID, Timestamp(1, 30)).id, rid2); - } - - { - OneOffRead oor(opCtx.get(), Timestamp(1, 25)); - Lock::GlobalLock globalLock(opCtx.get(), MODE_IS); - CollectionCatalog::get(opCtx.get()) - ->establishConsistentCollection(opCtx.get(), nss, Timestamp(1, 25)); - CollectionCatalog::get(opCtx.get()) - ->establishConsistentCollection( - opCtx.get(), {nss.dbName(), firstUUID}, Timestamp(1, 25)); - CollectionCatalog::get(opCtx.get()) - ->establishConsistentCollection( - opCtx.get(), {nss.dbName(), secondUUID}, Timestamp(1, 25)); - - // Check the entries, most didn't change - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 17)).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 17)).id, rid1); - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 19)).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 19)).id, rid1); - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 22)).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 22)).id, rid1); - // At Timestamp(1, 25) we now return kNotExists - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 25)).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); - ASSERT_EQ(lookupCatalogId(nss, secondUUID, Timestamp(1, 25)).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); - // But next timestamp returns unknown - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 26)).result, - CollectionCatalog::CatalogIdLookup::Existence::kUnknown); - ASSERT_EQ(lookupCatalogId(nss, secondUUID, Timestamp(1, 26)).result, - CollectionCatalog::CatalogIdLookup::Existence::kUnknown); - // The entry at Timestamp(1, 30) is unaffected - ASSERT_EQ(lookupCatalogId(nss, secondUUID, Timestamp(1, 30)).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - ASSERT_EQ(lookupCatalogId(nss, secondUUID, Timestamp(1, 30)).id, rid2); - } - - { - OneOffRead oor(opCtx.get(), Timestamp(1, 25)); - Lock::GlobalLock globalLock(opCtx.get(), MODE_IS); - CollectionCatalog::get(opCtx.get()) - ->establishConsistentCollection(opCtx.get(), nss, Timestamp(1, 26)); - CollectionCatalog::get(opCtx.get()) - ->establishConsistentCollection( - opCtx.get(), {nss.dbName(), firstUUID}, Timestamp(1, 26)); - CollectionCatalog::get(opCtx.get()) - ->establishConsistentCollection( - opCtx.get(), {nss.dbName(), secondUUID}, Timestamp(1, 26)); - - // We should not have re-written the existing entry at Timestamp(1, 26) - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 17)).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 17)).id, rid1); - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 19)).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 19)).id, rid1); - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 22)).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 22)).id, rid1); - // At Timestamp(1, 25) we now return kNotExists - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 25)).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); - ASSERT_EQ(lookupCatalogId(nss, secondUUID, Timestamp(1, 25)).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); - // But next timestamp returns unknown - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 26)).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); - ASSERT_EQ(lookupCatalogId(nss, secondUUID, Timestamp(1, 26)).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 27)).result, - CollectionCatalog::CatalogIdLookup::Existence::kUnknown); - ASSERT_EQ(lookupCatalogId(nss, secondUUID, Timestamp(1, 27)).result, - CollectionCatalog::CatalogIdLookup::Existence::kUnknown); - // The entry at Timestamp(1, 30) is unaffected - ASSERT_EQ(lookupCatalogId(nss, secondUUID, Timestamp(1, 30)).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - ASSERT_EQ(lookupCatalogId(nss, secondUUID, Timestamp(1, 30)).id, rid2); - } - - - // Clean up, check so we are back to the original state - CollectionCatalog::write(opCtx.get(), [](CollectionCatalog& catalog) { - catalog.cleanupForOldestTimestampAdvanced(Timestamp(1, 41)); - }); - - ASSERT_EQ(lookupCatalogId(nss, firstUUID, Timestamp(1, 15)).result, - CollectionCatalog::CatalogIdLookup::Existence::kUnknown); - ASSERT_EQ(lookupCatalogId(nss, secondUUID, Timestamp(1, 15)).result, - CollectionCatalog::CatalogIdLookup::Existence::kUnknown); -} - -TEST_F(CollectionCatalogTimestampTest, CatalogIdMappingInsertUnknown) { - NamespaceString nss = NamespaceString::createNamespaceString_forTest("a.b"); - - // Simulate startup where we have a range [oldest, stable] by advancing the oldest timestamp and - // then reading behind it. - CollectionCatalog::write(opCtx.get(), [](CollectionCatalog& catalog) { - catalog.cleanupForOldestTimestampAdvanced(Timestamp(1, 40)); - }); - - // Reading before the oldest is unknown - ASSERT_EQ(catalog()->lookupCatalogIdByNSS(nss, Timestamp(1, 15)).result, - CollectionCatalog::CatalogIdLookup::Existence::kUnknown); - - // Try to instantiate a non existing collection at this timestamp. - CollectionCatalog::get(opCtx.get()) - ->establishConsistentCollection(opCtx.get(), nss, Timestamp(1, 15)); - - // Lookup should now be not existing - ASSERT_EQ(catalog()->lookupCatalogIdByNSS(nss, Timestamp(1, 15)).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); -} - TEST_F(CollectionCatalogTimestampTest, CollectionLifetimeTiedToStorageTransactionLifetime) { const NamespaceString nss = NamespaceString::createNamespaceString_forTest("a.b"); const Timestamp createCollectionTs = Timestamp(10, 10); @@ -2919,76 +2199,6 @@ TEST_F(CollectionCatalogTimestampTest, CollectionLifetimeTiedToStorageTransactio } } -TEST_F(CollectionCatalogNoTimestampTest, CatalogIdMappingNoTimestamp) { - NamespaceString nss = NamespaceString::createNamespaceString_forTest("a.b"); - - // Create a collection on the namespace and confirm that we can lookup - UUID uuid = createCollection(opCtx.get(), nss, Timestamp()); - ASSERT_EQ(lookupCatalogId(nss, uuid, boost::none).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - - // Drop the collection and confirm it is also removed from mapping - dropCollection(opCtx.get(), nss, Timestamp()); - ASSERT_EQ(lookupCatalogId(nss, uuid, boost::none).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); -} - -TEST_F(CollectionCatalogNoTimestampTest, CatalogIdMappingNoTimestampRename) { - NamespaceString a = NamespaceString::createNamespaceString_forTest("a.a"); - NamespaceString b = NamespaceString::createNamespaceString_forTest("a.b"); - - // Create a collection on the namespace and confirm that we can lookup - UUID uuid = createCollection(opCtx.get(), a, Timestamp()); - ASSERT_EQ(lookupCatalogId(a, uuid, boost::none).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - ASSERT_EQ(catalog()->lookupCatalogIdByNSS(b).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); - - // Rename the collection and check lookup behavior - renameCollection(opCtx.get(), a, b, Timestamp()); - ASSERT_EQ(catalog()->lookupCatalogIdByNSS(a).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); - ASSERT_EQ(lookupCatalogId(b, uuid, boost::none).result, - CollectionCatalog::CatalogIdLookup::Existence::kExists); - - // Drop the collection and confirm it is also removed from mapping - dropCollection(opCtx.get(), b, Timestamp()); - ASSERT_EQ(lookupCatalogId(a, uuid, boost::none).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); - ASSERT_EQ(lookupCatalogId(b, uuid, boost::none).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); -} - -TEST_F(CollectionCatalogNoTimestampTest, CatalogIdMappingNoTimestampRenameDropTarget) { - NamespaceString a = NamespaceString::createNamespaceString_forTest("a.a"); - NamespaceString b = NamespaceString::createNamespaceString_forTest("a.b"); - - // Create collections on the namespaces and confirm that we can lookup - UUID uuidA = createCollection(opCtx.get(), a, Timestamp()); - UUID uuidB = createCollection(opCtx.get(), b, Timestamp()); - auto [aId, aResult] = lookupCatalogId(a, uuidA, boost::none); - auto [bId, bResult] = lookupCatalogId(b, uuidB, boost::none); - ASSERT_EQ(aResult, CollectionCatalog::CatalogIdLookup::Existence::kExists); - ASSERT_EQ(bResult, CollectionCatalog::CatalogIdLookup::Existence::kExists); - - // Rename the collection and check lookup behavior - renameCollection(opCtx.get(), a, b, Timestamp()); - auto [aIdAfter, aResultAfter] = catalog()->lookupCatalogIdByNSS(a, boost::none); - auto [bIdAfter, bResultAfter] = lookupCatalogId(b, uuidA, boost::none); - ASSERT_EQ(aResultAfter, CollectionCatalog::CatalogIdLookup::Existence::kNotExists); - ASSERT_EQ(bResultAfter, CollectionCatalog::CatalogIdLookup::Existence::kExists); - // Verify that the the recordId on b is now what was on a. We performed a rename with - // dropTarget=true. - ASSERT_EQ(aId, bIdAfter); - - // Drop the collection and confirm it is also removed from mapping - dropCollection(opCtx.get(), b, Timestamp()); - ASSERT_EQ(lookupCatalogId(a, uuidA, boost::none).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); - ASSERT_EQ(lookupCatalogId(b, uuidB, boost::none).result, - CollectionCatalog::CatalogIdLookup::Existence::kNotExists); -} - DEATH_TEST_F(CollectionCatalogTimestampTest, OpenCollectionInWriteUnitOfWork, "invariant") { const NamespaceString nss = NamespaceString::createNamespaceString_forTest("a.b"); const Timestamp createCollectionTs = Timestamp(10, 10); @@ -3826,7 +3036,7 @@ TEST_F(CollectionCatalogTimestampTest, MixedModeWrites) { // Initialize the oldest timestamp. CollectionCatalog::write(opCtx.get(), [](CollectionCatalog& catalog) { - catalog.cleanupForOldestTimestampAdvanced(Timestamp(1, 1)); + catalog.catalogIdTracker().cleanup(Timestamp(1, 1)); }); // Create and drop the collection. We have a time window where the namespace exists. @@ -3838,7 +3048,7 @@ TEST_F(CollectionCatalogTimestampTest, MixedModeWrites) { // Perform collection catalog cleanup. CollectionCatalog::write(opCtx.get(), [](CollectionCatalog& catalog) { - catalog.cleanupForOldestTimestampAdvanced(Timestamp(20, 20)); + catalog.catalogIdTracker().cleanup(Timestamp(20, 20)); }); // Drop the re-created collection. @@ -3846,7 +3056,7 @@ TEST_F(CollectionCatalogTimestampTest, MixedModeWrites) { // Cleanup again. CollectionCatalog::write(opCtx.get(), [](CollectionCatalog& catalog) { - catalog.cleanupForOldestTimestampAdvanced(Timestamp(25, 25)); + catalog.catalogIdTracker().cleanup(Timestamp(25, 25)); }); } } // namespace diff --git a/src/mongo/db/catalog/historical_catalogid_tracker.cpp b/src/mongo/db/catalog/historical_catalogid_tracker.cpp new file mode 100644 index 00000000000..901f9704906 --- /dev/null +++ b/src/mongo/db/catalog/historical_catalogid_tracker.cpp @@ -0,0 +1,695 @@ +/** + * Copyright (C) 2023-present MongoDB, Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the Server Side Public License, version 1, + * as published by MongoDB, Inc. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * Server Side Public License for more details. + * + * You should have received a copy of the Server Side Public License + * along with this program. If not, see + * <http://www.mongodb.com/licensing/server-side-public-license>. + * + * As a special exception, the copyright holders give permission to link the + * code of portions of this program with the OpenSSL library under certain + * conditions as described in each individual source file and distribute + * linked combinations including the program with the OpenSSL library. You + * must comply with the Server Side Public License in all respects for + * all of the code used other than as permitted herein. If you modify file(s) + * with this exception, you may extend this exception to your version of the + * file(s), but you are not obligated to do so. If you do not wish to do so, + * delete this exception statement from your version. If you delete this + * exception statement from all source files in the program, then also delete + * it in the license file. + */ + +#include "mongo/db/catalog/historical_catalogid_tracker.h" +#include "mongo/db/storage/storage_options.h" + +namespace mongo { +namespace { +// Sentinel id for marking a catalogId mapping range as unknown. Must use an invalid RecordId. +static RecordId kUnknownRangeMarkerId = RecordId::minLong(); +// Maximum number of entries in catalogId mapping when inserting catalogId missing at timestamp. +// Used to avoid quadratic behavior when inserting entries at the beginning. When threshold is +// reached we will fall back to more durable catalog scans. +static constexpr int kMaxCatalogIdMappingLengthForMissingInsert = 1000; + +// Copy existing value from immutable data structure or default-construct if not existing +template <class Container, class Key> +auto copyIfExists(const Container& container, const Key& key) { + const auto* value = container.find(key); + if (value) { + return *value; + } + return typename Container::mapped_type(); +} + +// Returns true if cleanup is needed for a catalogId range +bool needsCleanup(const std::vector<HistoricalCatalogIdTracker::TimestampedCatalogId>& ids) { + // Cleanup may occur if we have more than one entry for the namespace. + return ids.size() > 1; +} + +// Returns the lowest time a catalogId range may be cleaned up. needsCleanup() needs to have been +// checked prior to calling this function +Timestamp cleanupTime(const std::vector<HistoricalCatalogIdTracker::TimestampedCatalogId>& ids) { + // When we have multiple entries, use the time at the second entry as the cleanup time, + // when the oldest timestamp advances past this we no longer need the first entry. + return ids.at(1).ts; +} + +// Converts a not found lookup timestamp to a LookupResult based on the oldest maintained timestamp +HistoricalCatalogIdTracker::LookupResult resultForNotFound(boost::optional<Timestamp> ts, + Timestamp oldestMaintained) { + // If the request was with a time prior to the oldest maintained time it is unknown, otherwise + // we know it is not existing. + return {RecordId{}, + ts && *ts < oldestMaintained + ? HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown + : HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists}; +} + +// Converts a catalogId range into a lookup result that represents the latest state +HistoricalCatalogIdTracker::LookupResult latestInRange( + const std::vector<HistoricalCatalogIdTracker::TimestampedCatalogId>& range) { + auto catalogId = range.back().id; + if (catalogId) { + return {*catalogId, HistoricalCatalogIdTracker::LookupResult::Existence::kExists}; + } + return {RecordId{}, HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists}; +} + +HistoricalCatalogIdTracker::LookupResult findInRange( + Timestamp ts, + const std::vector<HistoricalCatalogIdTracker::TimestampedCatalogId>& range, + Timestamp oldestMaintained) { + // The algorithm is as follows for an input range of the following format that is sorted on + // timestamp: (ts1, id1), (ts2, id2), ..., (tsN, idN). + // + // We use upper_bound to perform binary search to the timestamp that is strictly larger than our + // query timestamp ts. The iterator can then be decremented to get the entry where the time is + // less or equal, this is the entry we are looking for. If upper_bound returns begin() or the + // 'id' in our found entry is the unknown marker the lookup result is unknown. + auto rangeIt = + std::upper_bound(range.begin(), range.end(), ts, [](const auto& ts, const auto& entry) { + return ts < entry.ts; + }); + if (rangeIt == range.begin()) { + return resultForNotFound(ts, oldestMaintained); + } + // Upper bound returns an iterator to the first entry with a larger timestamp. Decrement the + // iterator to get the last entry where the time is less or equal. + auto catalogId = (--rangeIt)->id; + if (catalogId) { + if (*catalogId != kUnknownRangeMarkerId) { + return {*catalogId, HistoricalCatalogIdTracker::LookupResult::Existence::kExists}; + } else { + return {RecordId{}, HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown}; + } + } + return {RecordId{}, HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists}; +} +} // namespace + +HistoricalCatalogIdTracker::LookupResult HistoricalCatalogIdTracker::lookup( + const NamespaceString& nss, boost::optional<Timestamp> ts) const { + if (const std::vector<TimestampedCatalogId>* mapping = _nss.find(nss)) { + // Mapping found for namespace, get result depending on timestamp. + if (ts) { + return findInRange(*ts, *mapping, _oldestTimestampMaintained); + } + return latestInRange(*mapping); + } + // No mapping found for namespace, result is either not found or unknown depending on timestamp + return resultForNotFound(ts, _oldestTimestampMaintained); +} + + +HistoricalCatalogIdTracker::LookupResult HistoricalCatalogIdTracker::lookup( + const UUID& uuid, boost::optional<Timestamp> ts) const { + if (const std::vector<TimestampedCatalogId>* mapping = _uuid.find(uuid)) { + // Mapping found for namespace, get result depending on timestamp. + if (ts) { + return findInRange(*ts, *mapping, _oldestTimestampMaintained); + } + return latestInRange(*mapping); + } + + // No mapping found for namespace, result is either not found or unknown depending on timestamp + return resultForNotFound(ts, _oldestTimestampMaintained); +} + +void HistoricalCatalogIdTracker::create(const NamespaceString& nss, + const UUID& uuid, + RecordId catalogId, + boost::optional<Timestamp> ts) { + + if (!ts) { + _createNoTimestamp(nss, uuid, catalogId); + return; + } + + _createTimestamp(nss, uuid, catalogId, *ts); +} + +void HistoricalCatalogIdTracker::drop(const NamespaceString& nss, + const UUID& uuid, + boost::optional<Timestamp> ts) { + if (!ts) { + _dropNoTimestamp(nss, uuid); + return; + } + + _dropTimestamp(nss, uuid, *ts); +} + +void HistoricalCatalogIdTracker::rename(const NamespaceString& from, + const NamespaceString& to, + boost::optional<Timestamp> ts) { + if (!ts) { + _renameNoTimestamp(from, to); + return; + } + + _renameTimestamp(from, to, *ts); +} + +bool HistoricalCatalogIdTracker::canRecordNonExisting(const NamespaceString& nss) const { + // recordNonExistingAtTime can use a lot of entries because of the unknown marker that is + // needed. Constrain the memory usage. + if (const std::vector<TimestampedCatalogId>* ids = _nss.find(nss)) { + return ids->size() < kMaxCatalogIdMappingLengthForMissingInsert; + } + return true; +} + +bool HistoricalCatalogIdTracker::canRecordNonExisting(const UUID& uuid) const { + // recordNonExistingAtTime can use a lot of entries because of the unknown marker that is + // needed. Constrain the memory usage. + if (const std::vector<TimestampedCatalogId>* ids = _uuid.find(uuid)) { + return ids->size() < kMaxCatalogIdMappingLengthForMissingInsert; + } + return true; +} + +void HistoricalCatalogIdTracker::recordExistingAtTime(const NamespaceString& nss, + const UUID& uuid, + RecordId catalogId, + Timestamp ts) { + + // Helper lambda to perform the operation on both namespace and UUID + auto doRecord = + [this, &catalogId, &ts](auto& idsContainer, auto& changesContainer, const auto& key) { + // Helper to update the cleanup time after we've performed an insert. + auto markForCleanupIfNeeded = [&](const auto& ids) { + if (!needsCleanup(ids)) { + return; + } + + changesContainer = changesContainer.insert(key); + _recordCleanupTime(cleanupTime(ids)); + }; + + // Get copy of existing mapping, or default-construct new. + auto ids = copyIfExists(idsContainer, key); + // Helper to write updated id mapping back into container at scope exit. This allows us + // to write to 'ids' as if we were doing inplace updates to the container. + ScopeGuard scopedGuard([&] { idsContainer = idsContainer.set(key, std::move(ids)); }); + + // Binary search to the entry with same or larger timestamp. This represents the insert + // position in the container. + auto it = std::lower_bound( + ids.begin(), ids.end(), ts, [](const auto& entry, const Timestamp& ts) { + return entry.ts < ts; + }); + + if (it != ids.end()) { + // An entry could exist already if concurrent writes are performed, keep the latest + // change in that case. + if (it->ts == ts) { + it->id = catalogId; + return; + } + + // If next element has same catalogId, we can adjust its timestamp to cover a longer + // range + if (it->id == catalogId) { + it->ts = ts; + + markForCleanupIfNeeded(ids); + return; + } + } + + // Otherwise insert new entry at timestamp + ids.insert(it, {{catalogId, ts}}); + markForCleanupIfNeeded(ids); + }; + + // Apply the insert to both namespace and uuid. + doRecord(_nss, _nssChanges, nss); + doRecord(_uuid, _uuidChanges, uuid); +} + +void HistoricalCatalogIdTracker::recordNonExistingAtTime(const NamespaceString& nss, Timestamp ts) { + // Get copy of existing mapping, or default-construct new. + auto ids = copyIfExists(_nss, nss); + + // Avoid inserting missing mapping when the list has grown past the threshold. Will cause + // the system to fall back to scanning the durable catalog. + if (ids.size() >= kMaxCatalogIdMappingLengthForMissingInsert) { + return; + } + + // Helper to write updated id mapping back into container at scope exit + ScopeGuard scopedGuard([&] { _nss = _nss.set(nss, std::move(ids)); }); + + // Binary search to the entry with same or larger timestamp. This represents the insert position + // in the container. + auto it = + std::lower_bound(ids.begin(), ids.end(), ts, [](const auto& entry, const Timestamp& ts) { + return entry.ts < ts; + }); + + if (it != ids.end() && it->ts == ts) { + // An entry could exist already if concurrent writes are performed, keep the latest + // change in that case. + it->id = boost::none; + } else { + // Otherwise insert new entry + it = ids.insert(it, {boost::none, ts}); + } + + // The iterator is positioned on the added/modified element above, reposition it to the next + // entry + ++it; + + // We don't want to assume that the namespace remains not existing until the next entry, as + // there can be times where the namespace actually does exist. To make sure we trigger the + // scanning of the durable catalog in this range we will insert a bogus entry using an invalid + // RecordId at the next timestamp. This will treat the range forward as unknown. + auto nextTs = ts + 1; + + // If the next entry is on the next timestamp already, we can skip adding the bogus entry. + // If this function is called for a previously unknown namespace or UUID, we may not have + // any future valid entries and the iterator would be positioned at and at this point. + if (it == ids.end() || it->ts != nextTs) { + ids.insert(it, {kUnknownRangeMarkerId, nextTs}); + } + + // Update cleanup time if needed + if (!needsCleanup(ids)) { + return; + } + + _nssChanges = _nssChanges.insert(nss); + _recordCleanupTime(cleanupTime(ids)); +} + +void HistoricalCatalogIdTracker::recordNonExistingAtTime(const UUID& uuid, Timestamp ts) { + auto ids = copyIfExists(_uuid, uuid); + + // Avoid inserting missing mapping when the list has grown past the threshold. Will cause + // the system to fall back to scanning the durable catalog. + if (ids.size() >= kMaxCatalogIdMappingLengthForMissingInsert) { + return; + } + + // Helper to write updated id mapping back into container at scope exit + ScopeGuard scopedGuard([&] { _uuid = _uuid.set(uuid, std::move(ids)); }); + + // Binary search to the entry with same or larger timestamp. This represents the insert position + // in the container. + auto it = + std::lower_bound(ids.begin(), ids.end(), ts, [](const auto& entry, const Timestamp& ts) { + return entry.ts < ts; + }); + + if (it != ids.end() && it->ts == ts) { + // An entry could exist already if concurrent writes are performed, keep the latest + // change in that case. + it->id = boost::none; + } else { + // Otherwise insert new entry + it = ids.insert(it, {boost::none, ts}); + } + + // The iterator is positioned on the added/modified element above, reposition it to the next + // entry + ++it; + + // We don't want to assume that the namespace remains not existing until the next entry, as + // there can be times where the namespace actually does exist. To make sure we trigger the + // scanning of the durable catalog in this range we will insert a bogus entry using an invalid + // RecordId at the next timestamp. This will treat the range forward as unknown. + auto nextTs = ts + 1; + + // If the next entry is on the next timestamp already, we can skip adding the bogus entry. + // If this function is called for a previously unknown namespace or UUID, we may not have + // any future valid entries and the iterator would be positioned at and at this point. + if (it == ids.end() || it->ts != nextTs) { + ids.insert(it, {kUnknownRangeMarkerId, nextTs}); + } + + // Update cleanup time if needed + if (!needsCleanup(ids)) { + return; + } + + _uuidChanges = _uuidChanges.insert(uuid); + _recordCleanupTime(cleanupTime(ids)); +} + +bool HistoricalCatalogIdTracker::dirty(Timestamp oldest) const { + return _lowestTimestampForCleanup <= oldest; +} + +void HistoricalCatalogIdTracker::cleanup(Timestamp oldest) { + Timestamp nextLowestCleanupTimestamp = Timestamp::max(); + + // Helper lambda to perform the operation on both namespace and UUID + auto doCleanup = [this, &oldest, &nextLowestCleanupTimestamp](auto& idsContainer, + auto& changesContainer) { + // Batch all changes together + auto ids = idsContainer.transient(); + auto changes = changesContainer.transient(); + + for (auto&& key : changesContainer) { + // + auto range = ids.at(key); + + // Binary search for next larger timestamp + auto rangeIt = std::upper_bound( + range.begin(), range.end(), oldest, [](const auto& ts, const auto& entry) { + return ts < entry.ts; + }); + + // Continue if there is nothing to cleanup for this timestamp yet + if (rangeIt == range.begin()) { + // There should always be at least two entries in the range when we hit this + // branch. For the namespace to be put in '_nssChanges' we need at least two + // entries. + invariant(range.size() > 1); + nextLowestCleanupTimestamp = + std::min(nextLowestCleanupTimestamp, cleanupTime(range)); + continue; + } + + // The iterator is positioned to the closest entry that has a larger timestamp, + // decrement to get a lower or equal timestamp. This represents the first entry that we + // may not cleanup. + --rangeIt; + + // Erase range, we will leave at least one element due to the decrement above + range.erase(range.begin(), rangeIt); + + // If more changes are needed for this namespace, keep it in the set and keep track + // of lowest timestamp. + if (range.size() > 1) { + nextLowestCleanupTimestamp = + std::min(nextLowestCleanupTimestamp, cleanupTime(range)); + ids.set(key, std::move(range)); + continue; + } + // If the last remaining element is a drop earlier than the oldest timestamp, we can + // remove tracking this namespace + if (range.back().id == boost::none) { + ids.erase(key); + } else { + ids.set(key, std::move(range)); + } + + // Unmark this namespace or UUID for needing changes. + changes.erase(key); + } + + // Write back all changes to main container + changesContainer = changes.persistent(); + idsContainer = ids.persistent(); + }; + + // Iterate over all namespaces and UUIDs that is marked that they need cleanup + doCleanup(_nss, _nssChanges); + doCleanup(_uuid, _uuidChanges); + + _lowestTimestampForCleanup = nextLowestCleanupTimestamp; + _oldestTimestampMaintained = std::max(_oldestTimestampMaintained, oldest); +} + +void HistoricalCatalogIdTracker::rollback(Timestamp stable) { + _nssChanges = {}; + _uuidChanges = {}; + _lowestTimestampForCleanup = Timestamp::max(); + _oldestTimestampMaintained = std::min(_oldestTimestampMaintained, stable); + + // Helper lambda to perform the operation on both namespace and UUID + auto removeLargerTimestamps = [this, &stable](auto& idsContainer, auto& changesContainer) { + // Batch all changes together + auto idsWriter = idsContainer.transient(); + auto changesWriter = changesContainer.transient(); + + // Go through all known mappings and remove entries larger than input stable timestamp + for (const auto& [key, ids] : idsContainer) { + // Binary search to the first entry with a too large timestamp + auto end = std::upper_bound( + ids.begin(), ids.end(), stable, [](Timestamp ts, const auto& entry) { + return ts < entry.ts; + }); + + // Create a new range without the timestamps that are too large + std::vector<TimestampedCatalogId> removed(ids.begin(), end); + + // If the resulting range is empty, remove the key from the container + if (removed.empty()) { + idsWriter.erase(key); + continue; + } + + // Calculate when this namespace needs to be cleaned up next + if (needsCleanup(removed)) { + Timestamp cleanTime = cleanupTime(removed); + changesWriter.insert(key); + _recordCleanupTime(cleanTime); + } + idsWriter.set(key, std::move(removed)); + } + + // Write back all changes to main container + changesContainer = changesWriter.persistent(); + idsContainer = idsWriter.persistent(); + }; + + // Rollback on both namespace and uuid containers. + removeLargerTimestamps(_nss, _nssChanges); + removeLargerTimestamps(_uuid, _uuidChanges); +} + +void HistoricalCatalogIdTracker::_recordCleanupTime(Timestamp ts) { + if (ts < _lowestTimestampForCleanup) { + _lowestTimestampForCleanup = ts; + } +} + +void HistoricalCatalogIdTracker::_createTimestamp(const NamespaceString& nss, + const UUID& uuid, + RecordId catalogId, + Timestamp ts) { + // Helper lambda to perform the operation on both namespace and UUID + auto doCreate = [&catalogId, &ts](auto& idsContainer, const auto& key) { + // Make a copy of the vector stored at 'key' + auto ids = copyIfExists(idsContainer, key); + + // An entry could exist already if concurrent writes are performed, keep the latest + // change in that case. + if (!ids.empty() && ids.back().ts == ts) { + ids.back().id = catalogId; + idsContainer = idsContainer.set(key, std::move(ids)); + return; + } + + // Otherwise, push new entry at the end. Timestamp is always increasing + invariant(ids.empty() || ids.back().ts < ts); + // If the catalogId is the same as last entry, there's nothing we need to do. This can + // happen when the catalog is reopened. + if (!ids.empty() && ids.back().id == catalogId) { + return; + } + + // Push new mapping to the end and write back to the container. As this is a create, we do + // not need to update the cleanup time as a create can never yield an updated (lower) + // cleanup time for this namespace/uuid. + ids.push_back({catalogId, ts}); + idsContainer = idsContainer.set(key, std::move(ids)); + }; + + // Create on both namespace and uuid containers. + doCreate(_nss, nss); + doCreate(_uuid, uuid); +} + +void HistoricalCatalogIdTracker::_createNoTimestamp(const NamespaceString& nss, + const UUID& uuid, + RecordId catalogId) { + // Make sure untimestamped writes have a single entry in mapping. If we're mixing + // timestamped with untimestamped (such as repair). Ignore the untimestamped writes + // as an untimestamped deregister will correspond with an untimestamped register. We + // should leave the mapping as-is in this case. + + auto doCreate = [&catalogId](auto& idsContainer, const auto& key) { + const std::vector<TimestampedCatalogId>* ids = idsContainer.find(key); + if (!ids) { + // This namespace or UUID was added due to an untimestamped write, add an entry + // with min timestamp + idsContainer = idsContainer.set(key, {{catalogId, Timestamp::min()}}); + return; + } + + if (ids->size() > 1 && !storageGlobalParams.repair) { + // This namespace or UUID was added due to an untimestamped write. But this + // namespace or UUID already had some timestamped writes performed. In this + // case, we re-write the history. The only known area that does this today is + // when profiling is enabled (untimestamped collection creation), followed by + // dropping the database (timestamped collection drop). + // TODO SERVER-75740: Remove this branch. + invariant(!ids->back().ts.isNull()); + + idsContainer = idsContainer.set(key, {{catalogId, Timestamp::min()}}); + } + }; + + // Create on both namespace and uuid containers. + doCreate(_nss, nss); + doCreate(_uuid, uuid); +} + +void HistoricalCatalogIdTracker::_dropTimestamp(const NamespaceString& nss, + const UUID& uuid, + Timestamp ts) { + // Helper lambda to perform the operation on both namespace and UUID + auto doDrop = [this, &ts](auto& idsContainer, auto& changesContainer, const auto& key) { + // Make a copy of the vector stored at 'key' + auto ids = copyIfExists(idsContainer, key); + // An entry could exist already if concurrent writes are performed, keep the latest change + // in that case. + if (!ids.empty() && ids.back().ts == ts) { + ids.back().id = boost::none; + idsContainer = idsContainer.set(key, std::move(ids)); + return; + } + + // Otherwise, push new entry at the end. Timestamp is always increasing + invariant(ids.empty() || ids.back().ts < ts); + // If the catalogId is the same as last entry, there's nothing we need to do. This can + // happen when the catalog is reopened. + if (!ids.empty() && !ids.back().id.has_value()) { + return; + } + + // A drop entry can't be pushed in the container if it's empty. This is because we cannot + // initialize the namespace or UUID with a single drop. + invariant(!ids.empty()); + + // Push the drop at the end our or mapping + ids.push_back({boost::none, ts}); + + // This drop may result in the possibility of cleanup in the future + if (needsCleanup(ids)) { + Timestamp cleanTime = cleanupTime(ids); + changesContainer = changesContainer.insert(key); + _recordCleanupTime(cleanTime); + } + + // Write back the updated mapping into our container + idsContainer = idsContainer.set(key, std::move(ids)); + }; + + // Drop on both namespace and uuid containers + doDrop(_nss, _nssChanges, nss); + doDrop(_uuid, _uuidChanges, uuid); +} + +void HistoricalCatalogIdTracker::_dropNoTimestamp(const NamespaceString& nss, const UUID& uuid) { + // Make sure untimestamped writes have a single entry in mapping. If we're mixing + // timestamped with untimestamped (such as repair). Ignore the untimestamped writes as + // an untimestamped deregister will correspond with an untimestamped register. We should + // leave the mapping as-is in this case. + + auto doDrop = [](auto& idsContainer, const auto& key) { + const std::vector<TimestampedCatalogId>* ids = idsContainer.find(key); + if (ids && ids->size() == 1) { + // This namespace or UUID was removed due to an untimestamped write, clear entries. + idsContainer = idsContainer.erase(key); + } + }; + + // Drop on both namespace and uuid containers + doDrop(_nss, nss); + doDrop(_uuid, uuid); +} + +void HistoricalCatalogIdTracker::_renameTimestamp(const NamespaceString& from, + const NamespaceString& to, + Timestamp ts) { + // Make copies of existing mappings on these namespaces. + auto toIds = copyIfExists(_nss, to); + auto fromIds = copyIfExists(_nss, from); + + // First update 'to' mapping. This is similar to a 'create'. + if (!toIds.empty() && toIds.back().ts == ts) { + // An entry could exist already if concurrent writes are performed, keep the latest change + // in that case. + toIds.back().id = fromIds.back().id; + } else { + // Timestamps should always be increasing. + invariant(toIds.empty() || toIds.back().ts < ts); + + // Push to end, we can take the catalogId from 'from'. We don't need to check if timestamp + // needs to be cleaned up as this is equivalent of a 'create'. + toIds.push_back({fromIds.back().id, ts}); + } + + // Then, update 'from' mapping. This is similar to a 'drop'. + if (!fromIds.empty() && fromIds.back().ts == ts) { + // Re-write latest entry if timestamp match (multiple changes occured in this transaction), + // otherwise push at end. + fromIds.back().id = boost::none; + } else { + // Timestamps should always be increasing. + invariant(fromIds.empty() || fromIds.back().ts < ts); + // Push to end and calculate cleanup timestamp. + fromIds.push_back({boost::none, ts}); + if (needsCleanup(fromIds)) { + Timestamp cleanTime = cleanupTime(fromIds); + _nssChanges = std::move(_nssChanges).insert(from); + _recordCleanupTime(cleanTime); + } + } + + // Store updates mappings back into container. + auto writer = _nss.transient(); + writer.set(from, std::move(fromIds)); + writer.set(to, std::move(toIds)); + _nss = writer.persistent(); +} + +void HistoricalCatalogIdTracker::_renameNoTimestamp(const NamespaceString& from, + const NamespaceString& to) { + // We should never perform rename in a mixed-mode environment. 'from' should contain a + // single entry and there should be nothing in 'to' . + const std::vector<TimestampedCatalogId>* fromIds = _nss.find(from); + invariant(fromIds && fromIds->size() == 1); + invariant(!_nss.find(to)); + + auto writer = _nss.transient(); + // Take the last known catalogId from 'from'. + writer.set(to, {{fromIds->back().id, Timestamp::min()}}); + writer.erase(from); + _nss = writer.persistent(); +} + +} // namespace mongo diff --git a/src/mongo/db/catalog/historical_catalogid_tracker.h b/src/mongo/db/catalog/historical_catalogid_tracker.h new file mode 100644 index 00000000000..57478658624 --- /dev/null +++ b/src/mongo/db/catalog/historical_catalogid_tracker.h @@ -0,0 +1,179 @@ +/** + * Copyright (C) 2023-present MongoDB, Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the Server Side Public License, version 1, + * as published by MongoDB, Inc. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * Server Side Public License for more details. + * + * You should have received a copy of the Server Side Public License + * along with this program. If not, see + * <http://www.mongodb.com/licensing/server-side-public-license>. + * + * As a special exception, the copyright holders give permission to link the + * code of portions of this program with the OpenSSL library under certain + * conditions as described in each individual source file and distribute + * linked combinations including the program with the OpenSSL library. You + * must comply with the Server Side Public License in all respects for + * all of the code used other than as permitted herein. If you modify file(s) + * with this exception, you may extend this exception to your version of the + * file(s), but you are not obligated to do so. If you do not wish to do so, + * delete this exception statement from your version. If you delete this + * exception statement from all source files in the program, then also delete + * it in the license file. + */ + +#pragma once + +#include "mongo/db/namespace_string.h" +#include "mongo/db/record_id.h" +#include "mongo/util/immutable/unordered_map.h" +#include "mongo/util/immutable/unordered_set.h" +#include "mongo/util/uuid.h" + +namespace mongo { +/** + * Data structure to keep track of mappings between namespace or uuid to a catalogId. The mapping is + * maintained for a range of time [oldest, now) to mirror the time range the server can service + * queries. + * + * Uses immutable data structures internally to be cheap to copy. + */ +class HistoricalCatalogIdTracker { +public: + HistoricalCatalogIdTracker(Timestamp oldest = Timestamp::max()) + : _oldestTimestampMaintained(oldest) {} + + /** + * CatalogId with Timestamp + */ + struct TimestampedCatalogId { + boost::optional<RecordId> + id; // none represents non-existing at timestamp (due to drop or rename) + Timestamp ts; + }; + + /** + * Returns the CatalogId for a given 'nss' or 'uuid' at timestamp 'ts'. + */ + struct LookupResult { + enum class Existence { + // Namespace or UUID exists at time 'ts' and catalogId set in 'id'. + kExists, + // Namespace or UUID does not exist at time 'ts'. + kNotExists, + // Namespace or UUID existence at time 'ts' is unknown. The durable catalog must be + // scanned to determine existence. + kUnknown + }; + RecordId id; + Existence result; + }; + + /** + * Returns the CatalogId for a given 'nss' or 'uuid' at timestamp 'ts'. + * + * Timestamp 'none' returns mapping at latest. + */ + LookupResult lookup(const NamespaceString& nss, boost::optional<Timestamp> ts) const; + LookupResult lookup(const UUID& uuid, boost::optional<Timestamp> ts) const; + + /** + * Register that a namespace/uuid was created with given 'catalogId' at timestamp 'ts'. + * + * Timestamp 'none' indicates that the namespace was created without a timestamp. + */ + void create(const NamespaceString& nss, + const UUID& uuid, + RecordId catalogId, + boost::optional<Timestamp> ts); + + /** + * Register that a namespace/uuid was dropped at timestamp 'ts'. + * + * Timestamp 'none' indicates that the namespace was dropped without a timestamp. + */ + void drop(const NamespaceString& nss, const UUID& uuid, boost::optional<Timestamp> ts); + + /** + * Register that a namespace was renamed at timestamp 'ts'. + * + * Timestamp 'none' indicates that the namespace was renamed without a timestamp. + */ + void rename(const NamespaceString& from, + const NamespaceString& to, + boost::optional<Timestamp> ts); + + /** + * Records existence of a namespace at timestamp 'ts' that was previously unknown. + */ + void recordExistingAtTime(const NamespaceString& nss, + const UUID& uuid, + RecordId catalogId, + Timestamp ts); + + /** + * Records non-existence of a namespace at timestamp 'ts' that was previously unknown. + */ + void recordNonExistingAtTime(const NamespaceString& nss, Timestamp ts); + void recordNonExistingAtTime(const UUID& uuid, Timestamp ts); + + /** + * Returns true if the structure has space to record non-existence of a namespace/uuid. + */ + bool canRecordNonExisting(const NamespaceString& nss) const; + bool canRecordNonExisting(const UUID& uuid) const; + + /** + * Returns true if a call to 'cleanup' with the given timestemp would perform any cleanup. + */ + bool dirty(Timestamp oldest) const; + + /** + * Performs cleanup of historical data when the oldest timestamp advances. Should be performed + * regularly to free up data for time ranges that are no longer needed for lookups. + */ + void cleanup(Timestamp oldest); + + /** + * Rollback any mappings with larger timestamps than provided stable timestamp. Needs to be + * performed as part of replication rollback. + */ + void rollback(Timestamp stable); + +private: + void _recordCleanupTime(Timestamp ts); + + void _createTimestamp(const NamespaceString& nss, + const UUID& uuid, + RecordId catalogId, + Timestamp ts); + void _createNoTimestamp(const NamespaceString& nss, const UUID& uuid, RecordId catalogId); + void _dropTimestamp(const NamespaceString& nss, const UUID& uuid, Timestamp ts); + void _dropNoTimestamp(const NamespaceString& nss, const UUID& uuid); + void _renameTimestamp(const NamespaceString& from, const NamespaceString& to, Timestamp ts); + void _renameNoTimestamp(const NamespaceString& from, const NamespaceString& to); + + + // CatalogId mappings for all known namespaces and UUIDs for the CollectionCatalog. The vector + // is sorted on timestamp. UUIDs will have at most two entries. One for the create and another + // for the drop. UUIDs stay the same across collection renames. + immutable::unordered_map<NamespaceString, std::vector<TimestampedCatalogId>> _nss; + immutable::unordered_map<UUID, std::vector<TimestampedCatalogId>, UUID::Hash> _uuid; + // Set of namespaces and UUIDs that need cleanup when the oldest timestamp advances + // sufficiently. + immutable::unordered_set<NamespaceString> _nssChanges; + immutable::unordered_set<UUID, UUID::Hash> _uuidChanges; + // Point at which the oldest timestamp need to advance for there to be any catalogId namespace + // that can be cleaned up + Timestamp _lowestTimestampForCleanup = Timestamp::max(); + // The oldest timestamp at which the tracker maintains mappings. Anything older than this is + // unknown. + Timestamp _oldestTimestampMaintained; +}; + +} // namespace mongo diff --git a/src/mongo/db/catalog/historical_catalogid_tracker_test.cpp b/src/mongo/db/catalog/historical_catalogid_tracker_test.cpp new file mode 100644 index 00000000000..ae71b9f2320 --- /dev/null +++ b/src/mongo/db/catalog/historical_catalogid_tracker_test.cpp @@ -0,0 +1,1018 @@ +/** + * Copyright (C) 2023-present MongoDB, Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the Server Side Public License, version 1, + * as published by MongoDB, Inc. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * Server Side Public License for more details. + * + * You should have received a copy of the Server Side Public License + * along with this program. If not, see + * <http://www.mongodb.com/licensing/server-side-public-license>. + * + * As a special exception, the copyright holders give permission to link the + * code of portions of this program with the OpenSSL library under certain + * conditions as described in each individual source file and distribute + * linked combinations including the program with the OpenSSL library. You + * must comply with the Server Side Public License in all respects for + * all of the code used other than as permitted herein. If you modify file(s) + * with this exception, you may extend this exception to your version of the + * file(s), but you are not obligated to do so. If you do not wish to do so, + * delete this exception statement from your version. If you delete this + * exception statement from all source files in the program, then also delete + * it in the license file. + */ + +#include "mongo/db/catalog/historical_catalogid_tracker.h" +#include "mongo/unittest/unittest.h" + +namespace mongo { +namespace { + +TEST(HistoricalCatalogIdTrackerTest, Create) { + NamespaceString nss = NamespaceString::createNamespaceString_forTest("a.b"); + UUID uuid = UUID::gen(); + RecordId rid{1}; + + // Initialize the oldest timestamp to (1, 1) + HistoricalCatalogIdTracker tracker(Timestamp(1, 1)); + + // Create entry + tracker.create(nss, uuid, rid, Timestamp(1, 2)); + + // Lookup without timestamp returns latest catalogId + ASSERT_EQ(tracker.lookup(nss, boost::none).id, rid); + ASSERT_EQ(tracker.lookup(uuid, boost::none).id, rid); + // Lookup before create returns unknown if looking before oldest + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 0)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 0)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + // Lookup before create returns not exists if looking after oldest + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 1)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 1)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + // Lookup at create returns catalogId + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 2)).id, rid); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 2)).id, rid); + // Lookup after create returns catalogId + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 3)).id, rid); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 3)).id, rid); +} + +TEST(HistoricalCatalogIdTrackerTest, Drop) { + NamespaceString nss = NamespaceString::createNamespaceString_forTest("a.b"); + UUID uuid = UUID::gen(); + RecordId rid{1}; + + // Initialize the oldest timestamp to (1, 1) + HistoricalCatalogIdTracker tracker(Timestamp(1, 1)); + + // Create and drop collection. We have a time window where the namespace exists + tracker.create(nss, uuid, rid, Timestamp(1, 5)); + tracker.drop(nss, uuid, Timestamp(1, 10)); + + // Lookup without timestamp returns none + ASSERT_EQ(tracker.lookup(nss, boost::none).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + ASSERT_EQ(tracker.lookup(uuid, boost::none).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + // Lookup before create and oldest returns unknown + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 0)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 0)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + // Lookup before create returns not exists + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 4)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 4)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + // Lookup at create returns catalogId + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 5)).id, rid); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 5)).id, rid); + // Lookup after create returns catalogId + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 6)).id, rid); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 6)).id, rid); + // Lookup at drop returns none + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 10)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 10)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + // Lookup after drop returns none + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 20)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 20)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); +} + +TEST(HistoricalCatalogIdTrackerTest, Rename) { + NamespaceString from = NamespaceString::createNamespaceString_forTest("a.b"); + NamespaceString to = NamespaceString::createNamespaceString_forTest("a.c"); + UUID uuid = UUID::gen(); + RecordId rid{1}; + + // Initialize the oldest timestamp to (1, 1) + HistoricalCatalogIdTracker tracker(Timestamp(1, 1)); + + // Create and rename collection. We have two windows where the collection exists but for + // different namespaces + tracker.create(from, uuid, rid, Timestamp(1, 5)); + tracker.rename(from, to, Timestamp(1, 10)); + + // Lookup without timestamp on 'from' returns none. By 'uuid' returns catalogId + ASSERT_EQ(tracker.lookup(from, boost::none).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + ASSERT_EQ(tracker.lookup(uuid, boost::none).id, rid); + // Lookup before create and oldest returns unknown + ASSERT_EQ(tracker.lookup(from, Timestamp(1, 0)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 0)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + // Lookup before create returns not exists + ASSERT_EQ(tracker.lookup(from, Timestamp(1, 4)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 4)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + // Lookup at create returns catalogId + ASSERT_EQ(tracker.lookup(from, Timestamp(1, 5)).id, rid); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 5)).id, rid); + // Lookup after create returns catalogId + ASSERT_EQ(tracker.lookup(from, Timestamp(1, 6)).id, rid); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 6)).id, rid); + // Lookup at rename on 'from' returns none. By 'uuid' returns catalogId + ASSERT_EQ(tracker.lookup(from, Timestamp(1, 10)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 10)).id, rid); + // Lookup after rename on 'from' returns none. By 'uuid' returns catalogId + ASSERT_EQ(tracker.lookup(from, Timestamp(1, 20)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 20)).id, rid); + + // Lookup without timestamp on 'to' returns catalogId + ASSERT_EQ(tracker.lookup(to, boost::none).id, rid); + ASSERT_EQ(tracker.lookup(uuid, boost::none).id, rid); + // Lookup before rename and oldest on 'to' returns unknown + ASSERT_EQ(tracker.lookup(to, Timestamp(1, 0)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 0)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + // Lookup before rename on 'to' returns not exists. By 'uuid' returns catalogId + ASSERT_EQ(tracker.lookup(to, Timestamp(1, 9)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 9)).id, rid); + // Lookup at rename on 'to' returns catalogId + ASSERT_EQ(tracker.lookup(to, Timestamp(1, 10)).id, rid); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 10)).id, rid); + // Lookup after rename on 'to' returns catalogId + ASSERT_EQ(tracker.lookup(to, Timestamp(1, 20)).id, rid); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 20)).id, rid); +} + +TEST(HistoricalCatalogIdTrackerTest, RenameDropTarget) { + NamespaceString from = NamespaceString::createNamespaceString_forTest("a.b"); + NamespaceString to = NamespaceString::createNamespaceString_forTest("a.c"); + UUID uuid = UUID::gen(); + UUID originalUUID = UUID::gen(); + RecordId rid{1}; + RecordId originalToRid{2}; + + // Initialize the oldest timestamp to (1, 1) + HistoricalCatalogIdTracker tracker(Timestamp(1, 1)); + + // Create collections. The 'to' namespace will exist for one collection from Timestamp(1, 6) + // until it is dropped by the rename at Timestamp(1, 10), after which the 'to' namespace will + // correspond to the renamed collection. + tracker.create(from, uuid, rid, Timestamp(1, 5)); + tracker.create(to, originalUUID, originalToRid, Timestamp(1, 6)); + // Drop and rename with the same timestamp, this is the same as dropTarget=true + tracker.drop(to, originalUUID, Timestamp(1, 10)); + tracker.rename(from, to, Timestamp(1, 10)); + + // Lookup without timestamp on 'to' and 'uuid' returns latest catalog id. By 'originalUUID' + // returns not exists as the target was dropped. + ASSERT_EQ(tracker.lookup(to, boost::none).id, rid); + ASSERT_EQ(tracker.lookup(uuid, boost::none).id, rid); + ASSERT_EQ(tracker.lookup(originalUUID, boost::none).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + // Lookup before rename and oldest on 'to' returns unknown + ASSERT_EQ(tracker.lookup(to, Timestamp(1, 0)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 0)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(to, Timestamp(1, 0)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(originalUUID, Timestamp(1, 0)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + // Lookup before rename on 'to' returns the original rid + ASSERT_EQ(tracker.lookup(to, Timestamp(1, 9)).id, originalToRid); + ASSERT_EQ(tracker.lookup(originalUUID, Timestamp(1, 9)).id, originalToRid); + // Lookup before rename on 'from' returns the rid + ASSERT_EQ(tracker.lookup(from, Timestamp(1, 9)).id, rid); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 9)).id, rid); + // Lookup at rename timestamp on 'to' and 'uuid' returns catalogId + ASSERT_EQ(tracker.lookup(to, Timestamp(1, 10)).id, rid); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 10)).id, rid); + // Lookup at rename timestamp on 'originalUUID' returns not exists as it was dropped during the + // rename. + ASSERT_EQ(tracker.lookup(originalUUID, Timestamp(1, 10)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + // Lookup after rename on 'to' and 'uuid' returns catalogId + ASSERT_EQ(tracker.lookup(to, Timestamp(1, 20)).id, rid); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 20)).id, rid); + // Lookup after rename timestamp on 'originalUUID' returns not exists as it was dropped during + // the rename. + ASSERT_EQ(tracker.lookup(originalUUID, Timestamp(1, 20)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); +} + +TEST(HistoricalCatalogIdTrackerTest, DropCreate) { + NamespaceString nss = NamespaceString::createNamespaceString_forTest("a.b"); + UUID firstUUID = UUID::gen(); + UUID secondUUID = UUID::gen(); + RecordId rid1{1}; + RecordId rid2{2}; + + // Initialize the oldest timestamp to (1, 1) + HistoricalCatalogIdTracker tracker(Timestamp(1, 1)); + + // Create, drop and recreate collection on the same namespace. We have different catalogId. + tracker.create(nss, firstUUID, rid1, Timestamp(1, 5)); + tracker.drop(nss, firstUUID, Timestamp(1, 10)); + tracker.create(nss, secondUUID, rid2, Timestamp(1, 15)); + + // Lookup without timestamp returns latest catalogId + ASSERT_EQ(tracker.lookup(nss, boost::none).id, rid2); + ASSERT_EQ(tracker.lookup(secondUUID, boost::none).id, rid2); + ASSERT_EQ(tracker.lookup(firstUUID, boost::none).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + // Lookup before first create returns not exists + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 4)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + ASSERT_EQ(tracker.lookup(firstUUID, Timestamp(1, 4)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 4)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + ASSERT_EQ(tracker.lookup(secondUUID, Timestamp(1, 4)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + // Lookup at first create returns first catalogId + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 5)).id, rid1); + ASSERT_EQ(tracker.lookup(firstUUID, Timestamp(1, 5)).id, rid1); + ASSERT_EQ(tracker.lookup(secondUUID, Timestamp(1, 5)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + // Lookup after first create returns first catalogId + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 6)).id, rid1); + ASSERT_EQ(tracker.lookup(firstUUID, Timestamp(1, 6)).id, rid1); + ASSERT_EQ(tracker.lookup(secondUUID, Timestamp(1, 6)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + // Lookup at drop returns none + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 10)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + ASSERT_EQ(tracker.lookup(firstUUID, Timestamp(1, 10)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 10)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + ASSERT_EQ(tracker.lookup(secondUUID, Timestamp(1, 10)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + // Lookup after drop returns none + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 13)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + ASSERT_EQ(tracker.lookup(firstUUID, Timestamp(1, 13)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 13)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + ASSERT_EQ(tracker.lookup(secondUUID, Timestamp(1, 13)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + // Lookup at second create returns second catalogId + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 15)).id, rid2); + ASSERT_EQ(tracker.lookup(secondUUID, Timestamp(1, 15)).id, rid2); + ASSERT_EQ(tracker.lookup(firstUUID, Timestamp(1, 15)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + // Lookup after second create returns second catalogId + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 20)).id, rid2); + ASSERT_EQ(tracker.lookup(secondUUID, Timestamp(1, 20)).id, rid2); + ASSERT_EQ(tracker.lookup(firstUUID, Timestamp(1, 20)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); +} + +TEST(HistoricalCatalogIdTrackerTest, CleanupEqDrop) { + NamespaceString nss = NamespaceString::createNamespaceString_forTest("a.b"); + UUID firstUUID = UUID::gen(); + UUID secondUUID = UUID::gen(); + RecordId rid1{1}; + RecordId rid2{2}; + + // Initialize the oldest timestamp to (1, 1) + HistoricalCatalogIdTracker tracker(Timestamp(1, 1)); + + // Create collection and verify we have nothing to cleanup + tracker.create(nss, firstUUID, rid1, Timestamp(1, 5)); + ASSERT_FALSE(tracker.dirty(Timestamp(1, 1))); + + // Drop collection and verify we have nothing to cleanup as long as the oldest timestamp is + // before the drop + tracker.drop(nss, firstUUID, Timestamp(1, 10)); + ASSERT_FALSE(tracker.dirty(Timestamp(1, 1))); + ASSERT_FALSE(tracker.dirty(Timestamp(1, 5))); + ASSERT_TRUE(tracker.dirty(Timestamp(1, 10))); + + // Create new collection and nothing changed with answers to needsCleanupForOldestTimestamp. + tracker.create(nss, secondUUID, rid2, Timestamp(1, 15)); + ASSERT_FALSE(tracker.dirty(Timestamp(1, 1))); + ASSERT_FALSE(tracker.dirty(Timestamp(1, 5))); + ASSERT_FALSE(tracker.dirty(Timestamp(1, 7))); + ASSERT_TRUE(tracker.dirty(Timestamp(1, 10))); + + // We can lookup the old catalogId before we advance the oldest timestamp and cleanup + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 5)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(firstUUID, Timestamp(1, 5)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(secondUUID, Timestamp(1, 5)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + + // Cleanup at drop timestamp, advance the oldest timestamp + tracker.cleanup(Timestamp(1, 10)); + + // After cleanup, we cannot find the old catalogId anymore. Also verify that we don't need + // anymore cleanup + ASSERT_FALSE(tracker.dirty(Timestamp(1, 10))); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 5)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(firstUUID, Timestamp(1, 5)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 5)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(secondUUID, Timestamp(1, 5)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 15)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(secondUUID, Timestamp(1, 15)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(firstUUID, Timestamp(1, 15)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); +} + +TEST(HistoricalCatalogIdTrackerTest, CleanupGtDrop) { + NamespaceString nss = NamespaceString::createNamespaceString_forTest("a.b"); + UUID firstUUID = UUID::gen(); + UUID secondUUID = UUID::gen(); + RecordId rid1{1}; + RecordId rid2{2}; + + // Initialize the oldest timestamp to (1, 1) + HistoricalCatalogIdTracker tracker(Timestamp(1, 1)); + + // Create collection and verify we have nothing to cleanup + tracker.create(nss, firstUUID, rid1, Timestamp(1, 5)); + ASSERT_FALSE(tracker.dirty(Timestamp(1, 1))); + + // Drop collection and verify we have nothing to cleanup as long as the oldest timestamp is + // before the drop + tracker.drop(nss, firstUUID, Timestamp(1, 10)); + ASSERT_FALSE(tracker.dirty(Timestamp(1, 1))); + ASSERT_FALSE(tracker.dirty(Timestamp(1, 5))); + ASSERT_TRUE(tracker.dirty(Timestamp(1, 10))); + + // Create new collection and nothing changed with answers to needsCleanupForOldestTimestamp. + tracker.create(nss, secondUUID, rid2, Timestamp(1, 15)); + ASSERT_FALSE(tracker.dirty(Timestamp(1, 1))); + ASSERT_FALSE(tracker.dirty(Timestamp(1, 5))); + ASSERT_FALSE(tracker.dirty(Timestamp(1, 7))); + ASSERT_TRUE(tracker.dirty(Timestamp(1, 12))); + + // We can lookup the old catalogId before we advance the oldest timestamp and cleanup + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 5)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(firstUUID, Timestamp(1, 5)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(secondUUID, Timestamp(1, 5)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + + // Cleanup after the drop timestamp + tracker.cleanup(Timestamp(1, 12)); + + // After cleanup, we cannot find the old catalogId anymore. Also verify that we don't need + // anymore cleanup + ASSERT_FALSE(tracker.dirty(Timestamp(1, 12))); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 5)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(firstUUID, Timestamp(1, 5)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 5)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(secondUUID, Timestamp(1, 5)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 15)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(secondUUID, Timestamp(1, 15)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(firstUUID, Timestamp(1, 15)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); +} + +TEST(HistoricalCatalogIdTrackerTest, CleanupGtRecreate) { + NamespaceString nss = NamespaceString::createNamespaceString_forTest("a.b"); + UUID firstUUID = UUID::gen(); + UUID secondUUID = UUID::gen(); + RecordId rid1{1}; + RecordId rid2{2}; + + // Initialize the oldest timestamp to (1, 1) + HistoricalCatalogIdTracker tracker(Timestamp(1, 1)); + + // Create collection and verify we have nothing to cleanup + tracker.create(nss, firstUUID, rid1, Timestamp(1, 5)); + ASSERT_FALSE(tracker.dirty(Timestamp(1, 1))); + + // Drop collection and verify we have nothing to cleanup as long as the oldest timestamp is + // before the drop + tracker.drop(nss, firstUUID, Timestamp(1, 10)); + ASSERT_FALSE(tracker.dirty(Timestamp(1, 1))); + ASSERT_FALSE(tracker.dirty(Timestamp(1, 5))); + ASSERT_TRUE(tracker.dirty(Timestamp(1, 10))); + + // Create new collection and nothing changed with answers to needsCleanupForOldestTimestamp. + tracker.create(nss, secondUUID, rid2, Timestamp(1, 15)); + ASSERT_FALSE(tracker.dirty(Timestamp(1, 1))); + ASSERT_FALSE(tracker.dirty(Timestamp(1, 5))); + ASSERT_FALSE(tracker.dirty(Timestamp(1, 7))); + ASSERT_TRUE(tracker.dirty(Timestamp(1, 20))); + + // We can lookup the old catalogId before we advance the oldest timestamp and cleanup + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 5)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(firstUUID, Timestamp(1, 5)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(secondUUID, Timestamp(1, 5)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + + // Cleanup after the recreate timestamp + tracker.cleanup(Timestamp(1, 20)); + + // After cleanup, we cannot find the old catalogId anymore. Also verify that we don't need + // anymore cleanup + ASSERT_FALSE(tracker.dirty(Timestamp(1, 20))); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 5)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(firstUUID, Timestamp(1, 5)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 5)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(secondUUID, Timestamp(1, 5)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 15)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(secondUUID, Timestamp(1, 15)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(firstUUID, Timestamp(1, 15)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); +} + +TEST(HistoricalCatalogIdTrackerTest, CleanupMultiple) { + NamespaceString nss = NamespaceString::createNamespaceString_forTest("a.b"); + UUID firstUUID = UUID::gen(); + UUID secondUUID = UUID::gen(); + UUID thirdUUID = UUID::gen(); + UUID fourthUUID = UUID::gen(); + RecordId rid1{1}; + RecordId rid2{2}; + RecordId rid3{3}; + RecordId rid4{4}; + + // Initialize the oldest timestamp to (1, 1) + HistoricalCatalogIdTracker tracker(Timestamp(1, 1)); + + // Create and drop multiple namespace on the same namespace + tracker.create(nss, firstUUID, rid1, Timestamp(1, 5)); + tracker.drop(nss, firstUUID, Timestamp(1, 10)); + tracker.create(nss, secondUUID, rid2, Timestamp(1, 15)); + tracker.drop(nss, secondUUID, Timestamp(1, 20)); + tracker.create(nss, thirdUUID, rid3, Timestamp(1, 25)); + tracker.drop(nss, thirdUUID, Timestamp(1, 30)); + tracker.create(nss, fourthUUID, rid4, Timestamp(1, 35)); + tracker.drop(nss, fourthUUID, Timestamp(1, 40)); + + // Lookup can find all four collections + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 5)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(firstUUID, Timestamp(1, 5)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 15)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(secondUUID, Timestamp(1, 15)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 25)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(thirdUUID, Timestamp(1, 25)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 35)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(fourthUUID, Timestamp(1, 35)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + + // Cleanup oldest + tracker.cleanup(Timestamp(1, 10)); + + // Lookup can find the three remaining collections + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 5)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(firstUUID, Timestamp(1, 5)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 15)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(secondUUID, Timestamp(1, 15)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 25)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(thirdUUID, Timestamp(1, 25)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 35)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(fourthUUID, Timestamp(1, 35)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + + // Cleanup + tracker.cleanup(Timestamp(1, 21)); + + // Lookup can find the two remaining collections + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 5)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(firstUUID, Timestamp(1, 5)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 15)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(secondUUID, Timestamp(1, 15)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 25)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(thirdUUID, Timestamp(1, 25)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 35)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(fourthUUID, Timestamp(1, 35)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + + // Cleanup + tracker.cleanup(Timestamp(1, 32)); + + // Lookup can find the last remaining collections + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 5)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(firstUUID, Timestamp(1, 5)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 15)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(secondUUID, Timestamp(1, 15)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 25)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(thirdUUID, Timestamp(1, 25)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 35)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(fourthUUID, Timestamp(1, 35)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + + // Cleanup + tracker.cleanup(Timestamp(1, 50)); + + // Lookup now result in unknown as the oldest timestamp has advanced where mapping has been + // removed + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 5)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(firstUUID, Timestamp(1, 5)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 15)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(secondUUID, Timestamp(1, 15)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 25)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(thirdUUID, Timestamp(1, 25)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 35)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(fourthUUID, Timestamp(1, 35)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); +} + +TEST(HistoricalCatalogIdTrackerTest, CleanupMultipleSingleCall) { + NamespaceString nss = NamespaceString::createNamespaceString_forTest("a.b"); + UUID firstUUID = UUID::gen(); + UUID secondUUID = UUID::gen(); + UUID thirdUUID = UUID::gen(); + UUID fourthUUID = UUID::gen(); + RecordId rid1{1}; + RecordId rid2{2}; + RecordId rid3{3}; + RecordId rid4{4}; + + // Initialize the oldest timestamp to (1, 1) + HistoricalCatalogIdTracker tracker(Timestamp(1, 1)); + + // Create and drop multiple namespace on the same namespace + tracker.create(nss, firstUUID, rid1, Timestamp(1, 5)); + tracker.drop(nss, firstUUID, Timestamp(1, 10)); + tracker.create(nss, secondUUID, rid2, Timestamp(1, 15)); + tracker.drop(nss, secondUUID, Timestamp(1, 20)); + tracker.create(nss, thirdUUID, rid3, Timestamp(1, 25)); + tracker.drop(nss, thirdUUID, Timestamp(1, 30)); + tracker.create(nss, fourthUUID, rid4, Timestamp(1, 35)); + tracker.drop(nss, fourthUUID, Timestamp(1, 40)); + + // Lookup can find all four collections + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 5)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(firstUUID, Timestamp(1, 5)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 15)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(secondUUID, Timestamp(1, 15)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 25)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(thirdUUID, Timestamp(1, 25)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 35)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(fourthUUID, Timestamp(1, 35)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + + // Cleanup all + tracker.cleanup(Timestamp(1, 50)); + + // Lookup now result in unknown as the oldest timestamp has advanced where mapping has been + // removed + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 5)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(firstUUID, Timestamp(1, 5)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 15)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(secondUUID, Timestamp(1, 15)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 25)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(thirdUUID, Timestamp(1, 25)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 35)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(fourthUUID, Timestamp(1, 35)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); +} + +TEST(HistoricalCatalogIdTrackerTest, Rollback) { + NamespaceString a = NamespaceString::createNamespaceString_forTest("b.a"); + NamespaceString b = NamespaceString::createNamespaceString_forTest("b.b"); + NamespaceString c = NamespaceString::createNamespaceString_forTest("b.c"); + NamespaceString d = NamespaceString::createNamespaceString_forTest("b.d"); + NamespaceString e = NamespaceString::createNamespaceString_forTest("b.e"); + + UUID firstUUID = UUID::gen(); + UUID secondUUID = UUID::gen(); + UUID thirdUUID = UUID::gen(); + UUID fourthUUID = UUID::gen(); + UUID fifthUUID = UUID::gen(); + UUID sixthUUID = UUID::gen(); + RecordId rid1{1}; + RecordId rid2{2}; + RecordId rid3{3}; + RecordId rid4{4}; + RecordId rid5{5}; + RecordId rid6{6}; + + // Initialize the oldest timestamp to (1, 1) + HistoricalCatalogIdTracker tracker(Timestamp(1, 1)); + + // Create and drop multiple namespace on the same namespace + tracker.create(a, firstUUID, rid1, Timestamp(1, 1)); + tracker.drop(a, firstUUID, Timestamp(1, 2)); + tracker.create(a, secondUUID, rid2, Timestamp(1, 3)); + tracker.create(b, thirdUUID, rid3, Timestamp(1, 5)); + tracker.create(c, fourthUUID, rid4, Timestamp(1, 7)); + tracker.create(d, fifthUUID, rid5, Timestamp(1, 8)); + tracker.create(e, sixthUUID, rid6, Timestamp(1, 9)); + tracker.drop(b, thirdUUID, Timestamp(1, 10)); + + // Rollback to Timestamp(1, 8) + tracker.rollback(Timestamp(1, 8)); + + ASSERT_EQ(tracker.lookup(e, boost::none).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + ASSERT_EQ(tracker.lookup(firstUUID, boost::none).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + ASSERT_EQ(tracker.lookup(a, boost::none).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(secondUUID, boost::none).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(b, boost::none).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(thirdUUID, boost::none).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(c, boost::none).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(fourthUUID, boost::none).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(d, boost::none).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(fifthUUID, boost::none).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(e, boost::none).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + ASSERT_EQ(tracker.lookup(sixthUUID, boost::none).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); +} + +TEST(HistoricalCatalogIdTrackerTest, Insert) { + NamespaceString nss = NamespaceString::createNamespaceString_forTest("a.b"); + UUID uuid = UUID::gen(); + RecordId rid{1}; + + // Simulate startup where we have a range [oldest, stable] by initializing the oldest timestamp + // to something high and then insert mappings behind it where the range is unknown. + HistoricalCatalogIdTracker tracker(Timestamp(1, 40)); + + // Record that the collection is known to exist + tracker.recordExistingAtTime(nss, uuid, rid, Timestamp(1, 17)); + + // Lookups before the inserted timestamp is still unknown + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 11)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 11)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + + // Lookups at or after the inserted timestamp is found + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 17)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 17)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 17)).id, rid); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 17)).id, rid); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 19)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 19)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 19)).id, rid); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 19)).id, rid); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 25)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 25)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 25)).id, rid); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 25)).id, rid); + + // Record that the collection is known to exist at an even earlier timestamp + tracker.recordExistingAtTime(nss, uuid, rid, Timestamp(1, 12)); + + // We should now have extended the range from Timestamp(1, 17) to Timestamp(1, 12) + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 12)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 12)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 12)).id, rid); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 12)).id, rid); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 16)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 16)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 16)).id, rid); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 16)).id, rid); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 17)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 17)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 17)).id, rid); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 17)).id, rid); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 19)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 19)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 19)).id, rid); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 19)).id, rid); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 25)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 25)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 25)).id, rid); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 25)).id, rid); + + // Record that the collection is unknown to exist at an later timestamp + tracker.recordNonExistingAtTime(nss, Timestamp(1, 25)); + tracker.recordNonExistingAtTime(uuid, Timestamp(1, 25)); + + // Check the entries, most didn't change + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 17)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 17)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 17)).id, rid); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 17)).id, rid); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 19)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 19)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 19)).id, rid); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 19)).id, rid); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 22)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 22)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 22)).id, rid); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 22)).id, rid); + // At Timestamp(1, 25) we now return kNotExists + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 25)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 25)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + // But next timestamp returns unknown + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 26)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 26)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + + // Record that the collection is unknown to exist at the timestamp + tracker.recordNonExistingAtTime(nss, Timestamp(1, 26)); + tracker.recordNonExistingAtTime(uuid, Timestamp(1, 26)); + + // We should not have re-written the existing entry at Timestamp(1, 26) + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 17)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 17)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 17)).id, rid); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 17)).id, rid); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 19)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 19)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 19)).id, rid); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 19)).id, rid); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 22)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 22)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 22)).id, rid); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 22)).id, rid); + // At Timestamp(1, 25) we now return kNotExists + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 25)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 25)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + // But next timestamp returns unknown + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 26)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 26)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 27)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 27)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + + // Clean up, check so we are back to the original state + tracker.cleanup(Timestamp(1, 41)); + + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 15)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 15)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); +} + +TEST(HistoricalCatalogIdTrackerTest, InsertUnknown) { + NamespaceString nss = NamespaceString::createNamespaceString_forTest("a.b"); + UUID uuid = UUID::gen(); + + // Simulate startup where we have a range [oldest, stable] by initializing the oldest timestamp + // to something high and then insert mappings behind it where the range is unknown. + HistoricalCatalogIdTracker tracker(Timestamp(1, 40)); + + // Reading before the oldest is unknown + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 15)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 15)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kUnknown); + + // Record that the collection is unknown to exist at the timestamp + tracker.recordNonExistingAtTime(nss, Timestamp(1, 15)); + tracker.recordNonExistingAtTime(uuid, Timestamp(1, 15)); + + // Lookup should now be not existing + ASSERT_EQ(tracker.lookup(nss, Timestamp(1, 15)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + // Lookup should now be not existing + ASSERT_EQ(tracker.lookup(uuid, Timestamp(1, 15)).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); +} + +TEST(HistoricalCatalogIdTrackerTest, NoTimestamp) { + NamespaceString nss = NamespaceString::createNamespaceString_forTest("a.b"); + UUID uuid = UUID::gen(); + RecordId rid{1}; + + HistoricalCatalogIdTracker tracker; + + // Create a collection on the namespace and confirm that we can lookup + tracker.create(nss, uuid, rid, boost::none); + ASSERT_EQ(tracker.lookup(nss, boost::none).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(uuid, boost::none).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + + // Drop the collection and confirm it is also removed from mapping + tracker.drop(nss, uuid, boost::none); + ASSERT_EQ(tracker.lookup(nss, boost::none).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + ASSERT_EQ(tracker.lookup(uuid, boost::none).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); +} + +TEST(HistoricalCatalogIdTrackerTest, NoTimestampRename) { + NamespaceString a = NamespaceString::createNamespaceString_forTest("a.a"); + NamespaceString b = NamespaceString::createNamespaceString_forTest("a.b"); + UUID uuid = UUID::gen(); + RecordId rid{1}; + + HistoricalCatalogIdTracker tracker; + + // Create a collection on the namespace and confirm that we can lookup + tracker.create(a, uuid, rid, boost::none); + ASSERT_EQ(tracker.lookup(a, boost::none).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(uuid, boost::none).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(b, boost::none).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + + // Rename the collection and check lookup behavior + tracker.rename(a, b, boost::none); + ASSERT_EQ(tracker.lookup(a, boost::none).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + ASSERT_EQ(tracker.lookup(b, boost::none).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(tracker.lookup(uuid, boost::none).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + + + // Drop the collection and confirm it is also removed from mapping + tracker.drop(b, uuid, boost::none); + ASSERT_EQ(tracker.lookup(a, boost::none).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + ASSERT_EQ(tracker.lookup(b, boost::none).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + ASSERT_EQ(tracker.lookup(uuid, boost::none).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); +} + +TEST(HistoricalCatalogIdTrackerTest, NoTimestampRenameDropTarget) { + NamespaceString a = NamespaceString::createNamespaceString_forTest("a.a"); + NamespaceString b = NamespaceString::createNamespaceString_forTest("a.b"); + UUID uuidA = UUID::gen(); + UUID uuidB = UUID::gen(); + RecordId ridA{1}; + RecordId ridB{2}; + + HistoricalCatalogIdTracker tracker; + + // Create collections on the namespaces and confirm that we can lookup + tracker.create(a, uuidA, ridA, boost::none); + tracker.create(b, uuidB, ridB, boost::none); + auto [aId, aResult] = tracker.lookup(a, boost::none); + auto [bId, bResult] = tracker.lookup(b, boost::none); + ASSERT_EQ(aResult, HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(bResult, HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(aResult, tracker.lookup(uuidA, boost::none).result); + ASSERT_EQ(bResult, tracker.lookup(uuidB, boost::none).result); + ASSERT_EQ(aId, tracker.lookup(uuidA, boost::none).id); + ASSERT_EQ(bId, tracker.lookup(uuidB, boost::none).id); + + // Rename the collection and check lookup behavior + tracker.drop(b, uuidB, boost::none); + tracker.rename(a, b, boost::none); + auto [aIdAfter, aResultAfter] = tracker.lookup(a, boost::none); + auto [bIdAfter, bResultAfter] = tracker.lookup(b, boost::none); + ASSERT_EQ(aResultAfter, HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + ASSERT_EQ(bResultAfter, HistoricalCatalogIdTracker::LookupResult::Existence::kExists); + ASSERT_EQ(bResultAfter, tracker.lookup(uuidA, boost::none).result); + ASSERT_EQ(bIdAfter, tracker.lookup(uuidA, boost::none).id); + // Verify that the the recordId on b is now what was on a. We performed a rename with + // dropTarget=true. + ASSERT_EQ(aId, bIdAfter); + + // Drop the collection and confirm it is also removed from mapping + tracker.drop(b, uuidA, boost::none); + ASSERT_EQ(tracker.lookup(a, boost::none).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + ASSERT_EQ(tracker.lookup(uuidA, boost::none).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + ASSERT_EQ(tracker.lookup(b, boost::none).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); + ASSERT_EQ(tracker.lookup(uuidB, boost::none).result, + HistoricalCatalogIdTracker::LookupResult::Existence::kNotExists); +} + +} // namespace +} // namespace mongo diff --git a/src/mongo/db/storage/storage_engine_impl.cpp b/src/mongo/db/storage/storage_engine_impl.cpp index 3de218ecf49..4cfa38852c0 100644 --- a/src/mongo/db/storage/storage_engine_impl.cpp +++ b/src/mongo/db/storage/storage_engine_impl.cpp @@ -95,10 +95,9 @@ StorageEngineImpl::StorageEngineImpl(OperationContext* opCtx, // The global lock is held by the timestamp monitor while callbacks are executed, so // there can be no batched CollectionCatalog writer and we are thus safe to write // using the service context. - if (CollectionCatalog::latest(serviceContext) - ->needsCleanupForOldestTimestamp(timestamp)) { + if (CollectionCatalog::latest(serviceContext)->catalogIdTracker().dirty(timestamp)) { CollectionCatalog::write(serviceContext, [timestamp](CollectionCatalog& catalog) { - catalog.cleanupForOldestTimestampAdvanced(timestamp); + catalog.catalogIdTracker().cleanup(timestamp); }); } }), @@ -279,7 +278,7 @@ void StorageEngineImpl::loadCatalog(OperationContext* opCtx, Timestamp minValidTs = stableTs ? *stableTs : Timestamp::min(); CollectionCatalog::write(opCtx, [&minValidTs](CollectionCatalog& catalog) { // Let the CollectionCatalog know that we are maintaining timestamps from minValidTs - catalog.cleanupForCatalogReopen(minValidTs); + catalog.catalogIdTracker().rollback(minValidTs); }); for (DurableCatalog::EntryIdentifier entry : catalogEntries) { if (_options.forRestore) { |