New GC implementation (#459)

- Feature: New garbage collection implementation, still in evaluation mode. Enabled by `--gc-v2` command line option

1 files changed, 308 insertions, 18 deletions

diff --git a/src/zenstore/gc.cpp b/src/zenstore/gc.cpp
index 9743eabf0..e09f46063 100644
--- a/src/zenstore/gc.cpp
+++ b/src/zenstore/gc.cpp
@@ -327,6 +327,280 @@ GcManager::~GcManager()
 {
 }
 
+//////// Begin New GC WIP
+
+void
+GcManager::AddGcReferencer(GcReferencer& Referencer)
+{
+	RwLock::ExclusiveLockScope _(m_Lock);
+	m_GcReferencers.push_back(&Referencer);
+}
+void
+GcManager::RemoveGcReferencer(GcReferencer& Referencer)
+{
+	RwLock::ExclusiveLockScope _(m_Lock);
+	std::erase_if(m_GcReferencers, [&](GcReferencer* $) { return $ == &Referencer; });
+}
+
+void
+GcManager::AddGcReferenceStore(GcReferenceStore& ReferenceStore)
+{
+	RwLock::ExclusiveLockScope _(m_Lock);
+	m_GcReferenceStores.push_back(&ReferenceStore);
+}
+void
+GcManager::RemoveGcReferenceStore(GcReferenceStore& ReferenceStore)
+{
+	RwLock::ExclusiveLockScope _(m_Lock);
+	std::erase_if(m_GcReferenceStores, [&](GcReferenceStore* $) { return $ == &ReferenceStore; });
+}
+
+GcResult
+GcManager::CollectGarbage(const GcSettings& Settings)
+{
+	GcCtx Ctx{.Settings = Settings};
+
+	Stopwatch TotalTimer;
+	auto	  __ = MakeGuard([&]() {
+		 ZEN_INFO(
+			 "GC: Removed {} items out of {}, deleted {} out of {}. Pruned {} Cid entries out of {}, compacted {} Cid entries out of {}, "
+				 "freed "
+				 "{} on disk and {} of memory in {}",
+			 Ctx.ExpiredItems.load(),
+			 Ctx.Items.load(),
+			 Ctx.DeletedItems.load(),
+			 Ctx.ExpiredItems.load(),
+			 Ctx.PrunedReferences.load(),
+			 Ctx.References.load(),
+			 Ctx.CompactedReferences.load(),
+			 Ctx.PrunedReferences.load(),
+			 NiceBytes(Ctx.RemovedDiskSpace.load()),
+			 NiceBytes(Ctx.RemovedMemory.load()),
+			 NiceTimeSpanMs(TotalTimer.GetElapsedTimeMs()));
+	 });
+
+	RwLock::SharedLockScope GcLock(m_Lock);
+
+	static const bool SingleThread =
+#if ZEN_BUILD_DEBUG
+		true
+#else
+		false
+#endif
+		;
+	WorkerThreadPool ThreadPool(SingleThread ? 0 : 8);
+
+	if (!m_GcReferencers.empty())
+	{
+		Latch WorkLeft(1);
+		// First remove any cache keys that may own references
+		Stopwatch Timer;
+		auto	  _ = MakeGuard([&]() { ZEN_INFO("GC: Removed expired data in {}", NiceTimeSpanMs(Timer.GetElapsedTimeMs())) });
+		for (GcReferencer* Owner : m_GcReferencers)
+		{
+			WorkLeft.AddCount(1);
+			ThreadPool.ScheduleWork([&Ctx, Owner, &WorkLeft]() {
+				auto _ = MakeGuard([&WorkLeft]() { WorkLeft.CountDown(); });
+				Owner->RemoveExpiredData(Ctx);
+			});
+		}
+		WorkLeft.CountDown();
+		WorkLeft.Wait();
+	}
+
+	if (Ctx.Settings.SkipCidDelete)
+	{
+		return GcResult{.Items				 = Ctx.Items.load(),
+						.ExpiredItems		 = Ctx.ExpiredItems.load(),
+						.DeletedItems		 = Ctx.DeletedItems.load(),
+						.References			 = Ctx.References.load(),
+						.PrunedReferences	 = Ctx.PrunedReferences.load(),
+						.CompactedReferences = Ctx.CompactedReferences.load(),
+						.RemovedDiskSpace	 = Ctx.RemovedDiskSpace.load(),
+						.RemovedMemory		 = Ctx.RemovedMemory.load()};
+	}
+
+	std::vector<std::unique_ptr<GcReferencePruner>> ReferencePruners;
+	if (!m_GcReferenceStores.empty())
+	{
+		ReferencePruners.reserve(m_GcReferenceStores.size());
+		Latch  WorkLeft(1);
+		RwLock ReferencePrunersLock;
+		// Easy to go wide, CreateReferencePruner is usually not very heavy but big data sets change that
+		Stopwatch Timer;
+		auto	  _ = MakeGuard([&]() { ZEN_INFO("GC: Created Cid pruners in {}", NiceTimeSpanMs(Timer.GetElapsedTimeMs())) });
+		for (GcReferenceStore* CidStore : m_GcReferenceStores)
+		{
+			WorkLeft.AddCount(1);
+			ThreadPool.ScheduleWork([&Ctx, CidStore, &WorkLeft, &ReferencePrunersLock, &ReferencePruners]() {
+				auto _ = MakeGuard([&WorkLeft]() { WorkLeft.CountDown(); });
+				// The CidStore will pick a list of CId entries to check, returning a collector
+				std::unique_ptr<GcReferencePruner> ReferencePruner(CidStore->CreateReferencePruner(Ctx));
+				if (ReferencePruner)
+				{
+					RwLock::ExclusiveLockScope __(ReferencePrunersLock);
+					ReferencePruners.emplace_back(std::move(ReferencePruner));
+				}
+			});
+		}
+		WorkLeft.CountDown();
+		WorkLeft.Wait();
+	}
+
+	std::vector<std::unique_ptr<GcReferenceChecker>> ReferenceCheckers;
+	if (!m_GcReferencers.empty())
+	{
+		ReferenceCheckers.reserve(m_GcReferencers.size());
+		Latch	  WorkLeft(1);
+		RwLock	  ReferenceCheckersLock;
+		Stopwatch Timer;
+		auto	  _ = MakeGuard([&]() { ZEN_INFO("GC: Created Cid checkers in {}", NiceTimeSpanMs(Timer.GetElapsedTimeMs())) });
+		// Easy to go wide, CreateReferenceCheckers is potentially heavy
+		// Lock all reference owners from changing the reference data and get access to check for referenced data
+		for (GcReferencer* Referencer : m_GcReferencers)
+		{
+			WorkLeft.AddCount(1);
+			ThreadPool.ScheduleWork([&Ctx, &WorkLeft, Referencer, &ReferenceCheckersLock, &ReferenceCheckers]() {
+				auto _ = MakeGuard([&WorkLeft]() { WorkLeft.CountDown(); });
+				// The Referencer will create a reference checker that guarrantees that the references do not change as long as it lives
+				std::vector<GcReferenceChecker*> Checkers = Referencer->CreateReferenceCheckers(Ctx);
+				try
+				{
+					if (!Checkers.empty())
+					{
+						RwLock::ExclusiveLockScope __(ReferenceCheckersLock);
+						for (auto& Checker : Checkers)
+						{
+							ReferenceCheckers.emplace_back(std::unique_ptr<GcReferenceChecker>(Checker));
+							Checker = nullptr;
+						}
+					}
+				}
+				catch (std::exception&)
+				{
+					while (!Checkers.empty())
+					{
+						delete Checkers.back();
+						Checkers.pop_back();
+					}
+					throw;
+				}
+			});
+		}
+		WorkLeft.CountDown();
+		WorkLeft.Wait();
+	}
+
+	Stopwatch LockStateTimer;
+	if (!ReferenceCheckers.empty())
+	{
+		// Easy to go wide, locking all references checkers so we hafve a stead state of which references are used
+		// From this point we have block all writes to all References (DiskBucket/ProjectStore) until we do delete the ReferenceCheckers
+		Latch WorkLeft(1);
+
+		Stopwatch Timer;
+		auto	  _ = MakeGuard([&]() { ZEN_INFO("GC: Locked Cid checkers in {}", NiceTimeSpanMs(Timer.GetElapsedTimeMs())) });
+		for (std::unique_ptr<GcReferenceChecker>& ReferenceChecker : ReferenceCheckers)
+		{
+			GcReferenceChecker* Checker = ReferenceChecker.get();
+			WorkLeft.AddCount(1);
+			ThreadPool.ScheduleWork([&Ctx, Checker, &WorkLeft, &ReferenceCheckers]() {
+				auto _ = MakeGuard([&WorkLeft]() { WorkLeft.CountDown(); });
+				Checker->LockState(Ctx);
+			});
+		}
+		WorkLeft.CountDown();
+		WorkLeft.Wait();
+	}
+
+	std::vector<std::unique_ptr<GcReferenceStoreCompactor>> ReferenceStoreCompactors;
+	ReferenceStoreCompactors.reserve(ReferencePruners.size());
+	if (!ReferencePruners.empty())
+	{
+		const auto GetUnusedReferences = [&ReferenceCheckers, &Ctx](std::span<IoHash> References) -> std::vector<IoHash> {
+			HashSet UnusedCids(References.begin(), References.end());
+			for (const std::unique_ptr<GcReferenceChecker>& ReferenceChecker : ReferenceCheckers)
+			{
+				ReferenceChecker->RemoveUsedReferencesFromSet(Ctx, UnusedCids);
+				if (UnusedCids.empty())
+				{
+					return {};
+				}
+			}
+			return std::vector<IoHash>(UnusedCids.begin(), UnusedCids.end());
+		};
+
+		// Easy to go wide, checking all Cids agains references in cache
+		// Ask stores to remove data that the ReferenceCheckers says are not references - this should be a lightweight operation that
+		// only updates in-memory index, actual disk changes should be done by the ReferenceStoreCompactors
+
+		Latch  WorkLeft(1);
+		RwLock ReferenceStoreCompactorsLock;
+
+		Stopwatch Timer;
+		auto	  _ = MakeGuard([&]() { ZEN_INFO("GC: Pruned unreferenced Cid data in {}", NiceTimeSpanMs(Timer.GetElapsedTimeMs())) });
+		for (std::unique_ptr<GcReferencePruner>& ReferencePruner : ReferencePruners)
+		{
+			GcReferencePruner* Pruner = ReferencePruner.get();
+			WorkLeft.AddCount(1);
+			ThreadPool.ScheduleWork(
+				[&Ctx, Pruner, &WorkLeft, &GetUnusedReferences, &ReferenceStoreCompactorsLock, &ReferenceStoreCompactors]() {
+					auto _ = MakeGuard([&WorkLeft]() { WorkLeft.CountDown(); });
+					// Go through all the ReferenceCheckers to see if the list of Cids the collector selected are referenced or not.
+					std::unique_ptr<GcReferenceStoreCompactor> ReferenceCompactor(Pruner->RemoveUnreferencedData(Ctx, GetUnusedReferences));
+					if (ReferenceCompactor)
+					{
+						RwLock::ExclusiveLockScope __(ReferenceStoreCompactorsLock);
+						ReferenceStoreCompactors.emplace_back(std::move(ReferenceCompactor));
+					}
+				});
+		}
+		WorkLeft.CountDown();
+		WorkLeft.Wait();
+	}
+	// Let the GcReferencers add new data, we will only change on-disk data at this point, adding new data is allowed
+	ReferenceCheckers.clear();
+	ZEN_INFO("GC: Writes blocked for {}", NiceTimeSpanMs(LockStateTimer.GetElapsedTimeMs()))
+
+	// Let go of the pruners
+	ReferencePruners.clear();
+
+	if (!ReferenceStoreCompactors.empty())
+	{
+		Latch WorkLeft(1);
+
+		// Easy to go wide
+		// Remove the stuff we deemed unreferenced from disk - may be heavy operation
+		Stopwatch Timer;
+		auto	  _ = MakeGuard([&]() { ZEN_INFO("GC: Compacted Cid stores in {}", NiceTimeSpanMs(Timer.GetElapsedTimeMs())) });
+		for (std::unique_ptr<GcReferenceStoreCompactor>& StoreCompactor : ReferenceStoreCompactors)
+		{
+			GcReferenceStoreCompactor* Compactor = StoreCompactor.get();
+			WorkLeft.AddCount(1);
+			ThreadPool.ScheduleWork([&Ctx, Compactor, &WorkLeft]() {
+				auto _ = MakeGuard([&WorkLeft]() { WorkLeft.CountDown(); });
+				// Go through all the ReferenceCheckers to see if the list of Cids the collector selected are referenced or not.
+				Compactor->CompactReferenceStore(Ctx);
+			});
+		}
+		WorkLeft.CountDown();
+		WorkLeft.Wait();
+	}
+
+	ReferenceStoreCompactors.clear();
+
+	return GcResult{.Items				 = Ctx.Items.load(),
+					.ExpiredItems		 = Ctx.ExpiredItems.load(),
+					.DeletedItems		 = Ctx.DeletedItems.load(),
+					.References			 = Ctx.References.load(),
+					.PrunedReferences	 = Ctx.PrunedReferences.load(),
+					.CompactedReferences = Ctx.CompactedReferences.load(),
+					.RemovedDiskSpace	 = Ctx.RemovedDiskSpace.load(),
+					.RemovedMemory		 = Ctx.RemovedMemory.load()};
+}
+
+//////// End New GC WIP
+
 void
 GcManager::AddGcContributor(GcContributor* Contributor)
 {
@@ -645,23 +919,19 @@ GcScheduler::Shutdown()
 bool
 GcScheduler::TriggerGc(const GcScheduler::TriggerGcParams& Params)
 {
-	if (m_Config.Enabled)
+	std::unique_lock Lock(m_GcMutex);
+	if (static_cast<uint32_t>(GcSchedulerStatus::kIdle) == m_Status)
 	{
-		std::unique_lock Lock(m_GcMutex);
-		if (static_cast<uint32_t>(GcSchedulerStatus::kIdle) == m_Status)
-		{
-			m_TriggerGcParams  = Params;
-			uint32_t IdleState = static_cast<uint32_t>(GcSchedulerStatus::kIdle);
+		m_TriggerGcParams  = Params;
+		uint32_t IdleState = static_cast<uint32_t>(GcSchedulerStatus::kIdle);
 
-			if (m_Status.compare_exchange_strong(/* expected */ IdleState,
-												 /* desired */ static_cast<uint32_t>(GcSchedulerStatus::kRunning)))
-			{
-				m_GcSignal.notify_one();
-				return true;
-			}
+		if (m_Status.compare_exchange_strong(/* expected */ IdleState,
+											 /* desired */ static_cast<uint32_t>(GcSchedulerStatus::kRunning)))
+		{
+			m_GcSignal.notify_one();
+			return true;
 		}
 	}
-
 	return false;
 }
 
@@ -806,7 +1076,7 @@ GcScheduler::SchedulerThread()
 			break;
 		}
 
-		if (!m_Config.Enabled && !m_TriggerScrubParams)
+		if (!m_Config.Enabled && !m_TriggerScrubParams && !m_TriggerGcParams)
 		{
 			WaitTime = std::chrono::seconds::max();
 			continue;
@@ -830,6 +1100,7 @@ GcScheduler::SchedulerThread()
 			std::chrono::seconds MaxProjectStoreDuration = m_Config.MaxProjectStoreDuration;
 			uint64_t			 DiskSizeSoftLimit		 = m_Config.DiskSizeSoftLimit;
 			bool				 SkipCid				 = false;
+			GcVersion			 UseGCVersion			 = m_Config.UseGCVersion;
 
 			bool DiskSpaceGCTriggered = false;
 			bool TimeBasedGCTriggered = false;
@@ -863,6 +1134,8 @@ GcScheduler::SchedulerThread()
 				{
 					DoDelete = false;
 				}
+				UseGCVersion = TriggerParams.ForceGCVersion.value_or(UseGCVersion);
+				DoGc		 = true;
 			}
 
 			if (m_TriggerScrubParams)
@@ -1067,7 +1340,7 @@ GcScheduler::SchedulerThread()
 				}
 			}
 
-			CollectGarbage(CacheExpireTime, ProjectStoreExpireTime, DoDelete, CollectSmallObjects, SkipCid);
+			CollectGarbage(CacheExpireTime, ProjectStoreExpireTime, DoDelete, CollectSmallObjects, SkipCid, UseGCVersion);
 
 			uint32_t RunningState = static_cast<uint32_t>(GcSchedulerStatus::kRunning);
 			if (!m_Status.compare_exchange_strong(RunningState, static_cast<uint32_t>(GcSchedulerStatus::kIdle)))
@@ -1148,7 +1421,8 @@ GcScheduler::CollectGarbage(const GcClock::TimePoint& CacheExpireTime,
 							const GcClock::TimePoint& ProjectStoreExpireTime,
 							bool					  Delete,
 							bool					  CollectSmallObjects,
-							bool					  SkipCid)
+							bool					  SkipCid,
+							GcVersion				  UseGCVersion)
 {
 	ZEN_TRACE_CPU("GcScheduler::CollectGarbage");
 
@@ -1195,10 +1469,26 @@ GcScheduler::CollectGarbage(const GcClock::TimePoint& CacheExpireTime,
 		Stopwatch  Timer;
 		const auto __ = MakeGuard([&] { ZEN_INFO("garbage collection DONE in {}", NiceTimeSpanMs(Timer.GetElapsedTimeMs())); });
 
-		GcStorageSize Diff = m_GcManager.CollectGarbage(GcCtx);
+		GcStorageSize Diff;
+		switch (UseGCVersion)
+		{
+			case GcVersion::kV1:
+				Diff = m_GcManager.CollectGarbage(GcCtx);
+				break;
+			case GcVersion::kV2:
+				{
+					GcResult Result = m_GcManager.CollectGarbage({.CacheExpireTime		  = CacheExpireTime,
+																  .ProjectStoreExpireTime = ProjectStoreExpireTime,
+																  .CollectSmallObjects	  = CollectSmallObjects,
+																  .IsDeleteMode			  = Delete,
+																  .SkipCidDelete		  = SkipCid});
+					Diff.DiskSize	= Result.RemovedDiskSpace;
+					Diff.MemorySize = Result.RemovedMemory;
+				}
+				break;
+		}
 
 		std::chrono::milliseconds ElapsedMS = std::chrono::milliseconds(Timer.GetElapsedTimeMs());
-
 		if (SkipCid)
 		{
 			m_LastLightweightGcTime		= GcClock::Now();