reduce lock time for memcache trim (#171)

- Improvement: Faster memcache trimming
  - Reduce calculations while holding bucket lock for memcache trim analysis to reduce contention
  - When trimming memcache, evict 25% more than required to reduce frequency of trimming
  - When trimming memcache, don't repack memcache data vector, defer that to regular garbage collection
  - When trimming memcache, deallocate memcache buffers when not holding exclusive lock in bucket

1 files changed, 125 insertions, 101 deletions

diff --git a/src/zenstore/cache/cachedisklayer.cpp b/src/zenstore/cache/cachedisklayer.cpp
index 08cb346b2..a4aa497c4 100644
--- a/src/zenstore/cache/cachedisklayer.cpp
+++ b/src/zenstore/cache/cachedisklayer.cpp
@@ -1800,43 +1800,41 @@ ZenCacheDiskLayer::CacheBucket::MemCacheTrim(GcClock::TimePoint ExpireTime)
 	uint64_t	  Trimmed	  = 0;
 	GcClock::Tick ExpireTicks = ExpireTime.time_since_epoch().count();
 
-	RwLock::ExclusiveLockScope IndexLock(m_IndexLock);
-	uint32_t				   MemCachedCount = gsl::narrow<uint32_t>(m_MemCachedPayloads.size());
-	if (MemCachedCount == 0)
-	{
-		return 0;
-	}
+	std::vector<IoBuffer> PurgedBuffers;
 
-	uint32_t WriteIndex = 0;
-	for (uint32_t ReadIndex = 0; ReadIndex < MemCachedCount; ++ReadIndex)
 	{
-		MemCacheData& Data = m_MemCachedPayloads[ReadIndex];
-		if (!Data.Payload)
-		{
-			continue;
-		}
-		PayloadIndex Index = Data.OwnerIndex;
-		ZEN_ASSERT_SLOW(m_Payloads[Index].MemCached == MemCachedIndex(ReadIndex));
-		GcClock::Tick AccessTime = m_AccessTimes[Index];
-		if (AccessTime < ExpireTicks)
+		RwLock::ExclusiveLockScope IndexLock(m_IndexLock);
+		uint32_t				   MemCachedCount = gsl::narrow<uint32_t>(m_MemCachedPayloads.size());
+		if (MemCachedCount == 0)
 		{
-			size_t PayloadSize = Data.Payload.GetSize();
-			RemoveMemCacheUsage(EstimateMemCachePayloadMemory(PayloadSize));
-			Data						= {};
-			m_Payloads[Index].MemCached = {};
-			Trimmed += PayloadSize;
-			continue;
+			return 0;
 		}
-		if (ReadIndex > WriteIndex)
+		PurgedBuffers.reserve(MemCachedCount);
+
+		for (uint32_t ReadIndex = 0; ReadIndex < MemCachedCount; ++ReadIndex)
 		{
-			m_MemCachedPayloads[WriteIndex] = MemCacheData{.Payload = std::move(Data.Payload), .OwnerIndex = Index};
-			m_Payloads[Index].MemCached		= MemCachedIndex(WriteIndex);
+			MemCacheData& Data = m_MemCachedPayloads[ReadIndex];
+			if (!Data.Payload)
+			{
+				continue;
+			}
+			PayloadIndex Index = Data.OwnerIndex;
+			ZEN_ASSERT_SLOW(m_Payloads[Index].MemCached == MemCachedIndex(ReadIndex));
+			GcClock::Tick AccessTime = m_AccessTimes[Index];
+			if (AccessTime < ExpireTicks)
+			{
+				size_t PayloadSize = Data.Payload.GetSize();
+				RemoveMemCacheUsage(EstimateMemCachePayloadMemory(PayloadSize));
+				PurgedBuffers.emplace_back(std::move(Data.Payload));
+				Data.OwnerIndex = {};
+				//			Data						= {};
+				m_Payloads[Index].MemCached = {};
+				Trimmed += PayloadSize;
+				m_FreeMemCachedPayloads.push_back(MemCachedIndex(ReadIndex));
+			}
 		}
-		WriteIndex++;
 	}
-	m_MemCachedPayloads.resize(WriteIndex);
-	m_MemCachedPayloads.shrink_to_fit();
-	zen::Reset(m_FreeMemCachedPayloads);
+	PurgedBuffers.clear();
 	return Trimmed;
 }
 
@@ -1845,23 +1843,40 @@ ZenCacheDiskLayer::CacheBucket::GetUsageByAccess(GcClock::TimePoint Now, GcClock
 {
 	ZEN_TRACE_CPU("Z$::Bucket::GetUsageByAccess");
 
-	size_t					SlotCount = InOutUsageSlots.capacity();
-	RwLock::SharedLockScope _(m_IndexLock);
-	uint32_t				MemCachedCount = gsl::narrow<uint32_t>(m_MemCachedPayloads.size());
-	if (MemCachedCount == 0)
-	{
-		return;
-	}
-	for (uint32_t ReadIndex = 0; ReadIndex < MemCachedCount; ++ReadIndex)
+	std::vector<uint64_t>	PayloadSizes;
+	std::vector<AccessTime> AccessTimes;
+
+	size_t SlotCount = InOutUsageSlots.capacity();
+
 	{
-		MemCacheData& Data = m_MemCachedPayloads[ReadIndex];
-		if (!Data.Payload)
+		RwLock::SharedLockScope _(m_IndexLock);
+		uint32_t				MemCachedCount = gsl::narrow<uint32_t>(m_MemCachedPayloads.size());
+		if (MemCachedCount == 0)
 		{
-			continue;
+			return;
 		}
-		PayloadIndex Index = Data.OwnerIndex;
-		ZEN_ASSERT_SLOW(m_Payloads[Index].MemCached == MemCachedIndex(ReadIndex));
-		GcClock::TimePoint ItemAccessTime = GcClock::TimePointFromTick(GcClock::Tick(m_AccessTimes[Index]));
+		PayloadSizes.reserve(MemCachedCount);
+		AccessTimes.reserve(MemCachedCount);
+		for (uint32_t ReadIndex = 0; ReadIndex < MemCachedCount; ++ReadIndex)
+		{
+			MemCacheData& Data = m_MemCachedPayloads[ReadIndex];
+			if (!Data.Payload)
+			{
+				continue;
+			}
+			PayloadIndex Index = Data.OwnerIndex;
+			ZEN_ASSERT_SLOW(m_Payloads[Index].MemCached == MemCachedIndex(ReadIndex));
+			PayloadSizes.push_back(Data.Payload.GetSize());
+			AccessTimes.push_back(m_AccessTimes[Index]);
+		}
+	}
+
+	auto PayloadSizeIt = PayloadSizes.begin();
+	auto AccessTimeIt  = AccessTimes.begin();
+	for (PayloadSizeIt = PayloadSizes.begin(); PayloadSizeIt != PayloadSizes.end(); PayloadSizeIt++)
+	{
+		ZEN_ASSERT_SLOW(AccessTimeIt != AccessTimes.end());
+		GcClock::TimePoint ItemAccessTime = GcClock::TimePointFromTick(GcClock::Tick(*AccessTimeIt));
 		GcClock::Duration  Age			  = Now > ItemAccessTime ? Now - ItemAccessTime : GcClock::Duration(0);
 		size_t			   Slot = Age < MaxAge ? gsl::narrow<size_t>((Age.count() * SlotCount) / MaxAge.count()) : (SlotCount - 1);
 		ZEN_ASSERT_SLOW(Slot < SlotCount);
@@ -1869,7 +1884,8 @@ ZenCacheDiskLayer::CacheBucket::GetUsageByAccess(GcClock::TimePoint Now, GcClock
 		{
 			InOutUsageSlots.resize(Slot + 1, 0);
 		}
-		InOutUsageSlots[Slot] += EstimateMemCachePayloadMemory(Data.Payload.GetSize());
+		InOutUsageSlots[Slot] += EstimateMemCachePayloadMemory(*PayloadSizeIt);
+		AccessTimeIt++;
 	}
 }
 
@@ -4671,8 +4687,8 @@ ZenCacheDiskLayer::GetCapturedBuckets()
 	return {};
 }
 
-void
-ZenCacheDiskLayer::MemCacheTrim()
+bool
+ZenCacheDiskLayer::StartAsyncMemCacheTrim()
 {
 	ZEN_TRACE_CPU("Z$::MemCacheTrim");
 
@@ -4683,71 +4699,79 @@ ZenCacheDiskLayer::MemCacheTrim()
 	bool Expected = false;
 	if (!m_IsMemCacheTrimming.compare_exchange_strong(Expected, true))
 	{
-		return;
+		return false;
 	}
 
 	try
 	{
-		m_JobQueue.QueueJob("ZenCacheDiskLayer::MemCacheTrim", [this](JobContext&) {
-			ZEN_TRACE_CPU("Z$::ZenCacheDiskLayer::MemCacheTrim [Async]");
-
-			const std::chrono::seconds TrimInterval = std::chrono::seconds(m_Configuration.MemCacheTrimIntervalSeconds);
-			uint64_t				   TrimmedSize	= 0;
-			Stopwatch				   Timer;
-			const auto				   Guard = MakeGuard([&] {
-				ZEN_INFO("trimmed {} (remaining {}), from memory cache in {}",
-						 NiceBytes(TrimmedSize),
-						 NiceBytes(m_TotalMemCachedSize),
-						 NiceTimeSpanMs(Timer.GetElapsedTimeMs()));
-
-				const GcClock::Tick NowTick		 = GcClock::TickCount();
-				const GcClock::Tick NextTrimTick = NowTick + GcClock::Duration(TrimInterval).count();
-				m_NextAllowedTrimTick.store(NextTrimTick);
-				m_IsMemCacheTrimming.store(false);
-			});
+		m_JobQueue.QueueJob("ZenCacheDiskLayer::MemCacheTrim", [this](JobContext&) { MemCacheTrim(); });
+	}
+	catch (const std::exception& Ex)
+	{
+		ZEN_ERROR("Failed scheduling ZenCacheDiskLayer::MemCacheTrim. Reason: '{}'", Ex.what());
+		m_IsMemCacheTrimming.store(false);
+		return false;
+	}
+	return true;
+}
 
-			const std::chrono::seconds MaxAge = std::chrono::seconds(m_Configuration.MemCacheMaxAgeSeconds);
+void
+ZenCacheDiskLayer::MemCacheTrim()
+{
+	ZEN_TRACE_CPU("Z$::ZenCacheDiskLayer::MemCacheTrim");
+
+	const std::chrono::seconds TrimInterval = std::chrono::seconds(m_Configuration.MemCacheTrimIntervalSeconds);
+	uint64_t				   TrimmedSize	= 0;
+	Stopwatch				   Timer;
+	const auto				   Guard = MakeGuard([&] {
+		ZEN_INFO("trimmed {} (remaining {}), from memory cache in {}",
+				 NiceBytes(TrimmedSize),
+				 NiceBytes(m_TotalMemCachedSize),
+				 NiceTimeSpanMs(Timer.GetElapsedTimeMs()));
 
-			static const size_t	  UsageSlotCount = 2048;
-			std::vector<uint64_t> UsageSlots;
-			UsageSlots.reserve(UsageSlotCount);
+		const GcClock::Tick NowTick		 = GcClock::TickCount();
+		const GcClock::Tick NextTrimTick = NowTick + GcClock::Duration(TrimInterval).count();
+		m_NextAllowedTrimTick.store(NextTrimTick);
+		m_IsMemCacheTrimming.store(false);
+	});
 
-			std::vector<CacheBucket*> Buckets;
-			{
-				RwLock::SharedLockScope __(m_Lock);
-				Buckets.reserve(m_Buckets.size());
-				for (auto& Kv : m_Buckets)
-				{
-					Buckets.push_back(Kv.second.get());
-				}
-			}
+	const std::chrono::seconds MaxAge = std::chrono::seconds(m_Configuration.MemCacheMaxAgeSeconds);
 
-			const GcClock::TimePoint Now = GcClock::Now();
-			{
-				ZEN_TRACE_CPU("Z$::ZenCacheDiskLayer::MemCacheTrim GetUsageByAccess");
-				for (CacheBucket* Bucket : Buckets)
-				{
-					Bucket->GetUsageByAccess(Now, MaxAge, UsageSlots);
-				}
-			}
+	static const size_t	  UsageSlotCount = 2048;
+	std::vector<uint64_t> UsageSlots;
+	UsageSlots.reserve(UsageSlotCount);
 
-			uint64_t TotalSize = 0;
-			for (size_t Index = 0; Index < UsageSlots.size(); ++Index)
-			{
-				TotalSize += UsageSlots[Index];
-				if (TotalSize >= m_Configuration.MemCacheTargetFootprintBytes)
-				{
-					GcClock::TimePoint ExpireTime = Now - ((GcClock::Duration(MaxAge) * Index) / UsageSlotCount);
-					TrimmedSize					  = MemCacheTrim(Buckets, ExpireTime);
-					break;
-				}
-			}
-		});
+	std::vector<CacheBucket*> Buckets;
+	{
+		RwLock::SharedLockScope __(m_Lock);
+		Buckets.reserve(m_Buckets.size());
+		for (auto& Kv : m_Buckets)
+		{
+			Buckets.push_back(Kv.second.get());
+		}
 	}
-	catch (const std::exception& Ex)
+
+	const GcClock::TimePoint Now = GcClock::Now();
 	{
-		ZEN_ERROR("Failed scheduling ZenCacheDiskLayer::MemCacheTrim. Reason: '{}'", Ex.what());
-		m_IsMemCacheTrimming.store(false);
+		ZEN_TRACE_CPU("Z$::ZenCacheDiskLayer::MemCacheTrim GetUsageByAccess");
+		for (CacheBucket* Bucket : Buckets)
+		{
+			Bucket->GetUsageByAccess(Now, MaxAge, UsageSlots);
+		}
+	}
+
+	const uint64_t MemCacheTargetFootprintBytes = (m_Configuration.MemCacheTargetFootprintBytes * 75) / 100;
+
+	uint64_t TotalSize = 0;
+	for (size_t Index = 0; Index < UsageSlots.size(); ++Index)
+	{
+		TotalSize += UsageSlots[Index];
+		if (TotalSize >= MemCacheTargetFootprintBytes)
+		{
+			GcClock::TimePoint ExpireTime = Now - ((GcClock::Duration(MaxAge) * Index) / UsageSlotCount);
+			TrimmedSize					  = MemCacheTrim(Buckets, ExpireTime);
+			break;
+		}
 	}
 }