New GC implementation (#459)

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

1 files changed, 190 insertions, 0 deletions

diff --git a/src/zenstore/blockstore.cpp b/src/zenstore/blockstore.cpp
index 02ee204ad..837185201 100644
--- a/src/zenstore/blockstore.cpp
+++ b/src/zenstore/blockstore.cpp
@@ -957,6 +957,196 @@ BlockStore::IterateChunks(const std::vector<BlockStoreLocation>& ChunkLocations,
 	}
 }
 
+void
+BlockStore::CompactBlocks(const BlockStoreCompactState&	  CompactState,
+						  uint64_t						  PayloadAlignment,
+						  const CompactCallback&		  ChangeCallback,
+						  const ClaimDiskReserveCallback& DiskReserveCallback)
+{
+	uint64_t DeletedSize = 0;
+	uint64_t MovedCount	 = 0;
+	uint64_t MovedSize	 = 0;
+
+	Stopwatch  TotalTimer;
+	const auto _ = MakeGuard([&] {
+		ZEN_DEBUG("compact blocks for '{}' DONE after {}, deleted {} and moved {} chunks ({}) ",
+				  m_BlocksBasePath,
+				  NiceTimeSpanMs(TotalTimer.GetElapsedTimeMs()),
+				  NiceBytes(DeletedSize),
+				  MovedCount,
+				  NiceBytes(MovedSize));
+	});
+
+	uint64_t		 WriteOffset   = m_MaxBlockSize + 1u;  // Force detect a new block
+	uint32_t		 NewBlockIndex = 0;
+	MovedChunksArray MovedChunks;
+
+	uint64_t RemovedSize = 0;
+
+	Ref<BlockStoreFile> NewBlockFile;
+	auto				NewBlockFileGuard = MakeGuard([&]() {
+		   if (NewBlockFile)
+		   {
+			   ZEN_DEBUG("dropping incomplete cas block store file '{}'", NewBlockFile->GetPath());
+			   {
+				   RwLock::ExclusiveLockScope _l(m_InsertLock);
+				   if (m_ChunkBlocks[NewBlockIndex] == NewBlockFile)
+				   {
+					   m_ChunkBlocks.erase(NewBlockIndex);
+				   }
+			   }
+			   NewBlockFile->MarkAsDeleteOnClose();
+		   }
+	   });
+
+	std::vector<uint32_t> RemovedBlocks;
+
+	CompactState.IterateBlocks(
+		[&](uint32_t BlockIndex, const std::vector<size_t>& KeepChunkIndexes, const std::vector<BlockStoreLocation>& ChunkLocations) {
+			ZEN_ASSERT(BlockIndex != m_WriteBlockIndex.load());
+
+			Ref<BlockStoreFile> OldBlockFile;
+			{
+				RwLock::SharedLockScope _(m_InsertLock);
+				auto					It = m_ChunkBlocks.find(BlockIndex);
+				if (It == m_ChunkBlocks.end())
+				{
+					// This block has unknown, we can't move anything. Report error?
+					return;
+				}
+				if (!It->second)
+				{
+					// This block has been removed, we can't move anything. Report error?
+					return;
+				}
+				OldBlockFile = It->second;
+			}
+			ZEN_ASSERT(OldBlockFile);
+
+			uint64_t OldBlockSize = OldBlockFile->FileSize();
+
+			// TODO: Add heuristics for determining if it is worth to compact a block (if only a very small part is removed)
+
+			std::vector<uint8_t> Chunk;
+			for (const size_t& ChunkIndex : KeepChunkIndexes)
+			{
+				const BlockStoreLocation ChunkLocation = ChunkLocations[ChunkIndex];
+				Chunk.resize(ChunkLocation.Size);
+				OldBlockFile->Read(Chunk.data(), Chunk.size(), ChunkLocation.Offset);
+
+				if ((WriteOffset + Chunk.size()) > m_MaxBlockSize)
+				{
+					if (NewBlockFile)
+					{
+						NewBlockFile->Flush();
+						MovedSize += NewBlockFile->FileSize();
+						NewBlockFile = nullptr;
+
+						ZEN_ASSERT(!MovedChunks.empty() || RemovedSize > 0);  // We should not have a new block if we haven't moved anything
+
+						ChangeCallback(MovedChunks, RemovedSize);
+						DeletedSize += RemovedSize;
+						RemovedSize = 0;
+						MovedCount += MovedChunks.size();
+						MovedChunks.clear();
+					}
+
+					uint32_t NextBlockIndex = m_WriteBlockIndex.load(std::memory_order_relaxed);
+					{
+						RwLock::ExclusiveLockScope InsertLock(m_InsertLock);
+						std::filesystem::path	   NewBlockPath;
+						NextBlockIndex = GetFreeBlockIndex(NextBlockIndex, InsertLock, NewBlockPath);
+						if (NextBlockIndex == (uint32_t)m_MaxBlockCount)
+						{
+							ZEN_ERROR("unable to allocate a new block in '{}', count limit {} exeeded",
+									  m_BlocksBasePath,
+									  static_cast<uint64_t>(std::numeric_limits<uint32_t>::max()) + 1);
+							return;
+						}
+
+						NewBlockFile				  = new BlockStoreFile(NewBlockPath);
+						m_ChunkBlocks[NextBlockIndex] = NewBlockFile;
+					}
+					ZEN_ASSERT(NewBlockFile);
+
+					std::error_code Error;
+					DiskSpace		Space = DiskSpaceInfo(m_BlocksBasePath, Error);
+					if (Error)
+					{
+						ZEN_ERROR("get disk space in '{}' FAILED, reason: '{}'", m_BlocksBasePath, Error.message());
+						return;
+					}
+
+					if (Space.Free < m_MaxBlockSize)
+					{
+						uint64_t ReclaimedSpace = DiskReserveCallback();
+						if (Space.Free + ReclaimedSpace < m_MaxBlockSize)
+						{
+							ZEN_WARN("garbage collect for '{}' FAILED, required disk space {}, free {}",
+									 m_BlocksBasePath,
+									 m_MaxBlockSize,
+									 NiceBytes(Space.Free + ReclaimedSpace));
+							{
+								RwLock::ExclusiveLockScope _l(m_InsertLock);
+								ZEN_ASSERT(m_ChunkBlocks[NextBlockIndex] == NewBlockFile);
+								m_ChunkBlocks.erase(NextBlockIndex);
+							}
+							NewBlockFile->MarkAsDeleteOnClose();
+							return;
+						}
+
+						ZEN_INFO("using gc reserve for '{}', reclaimed {}, disk free {}",
+								 m_BlocksBasePath,
+								 ReclaimedSpace,
+								 NiceBytes(Space.Free + ReclaimedSpace));
+					}
+					NewBlockFile->Create(m_MaxBlockSize);
+					NewBlockIndex = NextBlockIndex;
+					WriteOffset	  = 0;
+				}
+
+				NewBlockFile->Write(Chunk.data(), Chunk.size(), WriteOffset);
+				MovedChunks.push_back({ChunkIndex, {.BlockIndex = NewBlockIndex, .Offset = WriteOffset, .Size = Chunk.size()}});
+				WriteOffset = RoundUp(WriteOffset + Chunk.size(), PayloadAlignment);
+			}
+			Chunk.clear();
+
+			// Report what we have moved so we can purge the old block
+			if (!MovedChunks.empty() || RemovedSize > 0)
+			{
+				ChangeCallback(MovedChunks, RemovedSize);
+				DeletedSize += RemovedSize;
+				RemovedSize = 0;
+				MovedCount += MovedChunks.size();
+				MovedChunks.clear();
+			}
+
+			{
+				RwLock::ExclusiveLockScope InsertLock(m_InsertLock);
+				ZEN_DEBUG("marking cas block store file '{}' for delete, block #{}", OldBlockFile->GetPath(), BlockIndex);
+				OldBlockFile->MarkAsDeleteOnClose();
+				m_ChunkBlocks.erase(BlockIndex);
+				m_TotalSize.fetch_sub(OldBlockSize);
+				RemovedSize += OldBlockSize;
+			}
+		});
+	if (NewBlockFile)
+	{
+		NewBlockFile->Flush();
+		MovedSize += NewBlockFile->FileSize();
+		NewBlockFile = nullptr;
+	}
+
+	if (!MovedChunks.empty() || RemovedSize > 0)
+	{
+		ChangeCallback(MovedChunks, RemovedSize);
+		DeletedSize += RemovedSize;
+		RemovedSize = 0;
+		MovedCount += MovedChunks.size();
+		MovedChunks.clear();
+	}
+}
+
 const char*
 BlockStore::GetBlockFileExtension()
 {