SkipList Memory Release Issue

[Jarves42]

I am facing a strange memory release issue on the use of SkipList.

So I have used skiplist to the cache layer in my system. On the start of the service, I am creating rust std library thread for cache refresh and eviction. I am doing this both operation in single function call only. And there is a wait of 2 minutes between to refresh cache call. I have created same cache structure for multiple partitions(~200 partitions). And I am refreshing all partitions in single thread in single function call.

Addition of new keys in cache would be in parallel of cache refresh cycle.

And we have about 1M keys on average in skiplist.

Problem I am facing that, even after removing keys from cache it is not releasing memory. And memory continuouly increasing till OOM. And if I increase refresh interval to 10 or more minutes I am able to see stready memory in my system which I can't as it will directly affect user experience.

I have even tried using threadpool to refresh partition instead of doing all in one thread. That also didn't work.

I can't post exact function as it is part of very big code base. But trying to give structure overview.

struct Cache {
   inner: SkipList<Vec<u8>,CacheValue>
}

struct Partition {
   id: String,
   cache: Cache
}

So basically spawned thread on start have access of Vec<Partition>. It iterator over it at every 2 minutes and removed expired keys and refreshed remaining keys.

No explicit impl of Drop trait for any struct mentioned above.

Any lead would be really helpful. Thanks.

So the issue with SkipList is that it deallocates memory lazily using the epoch-based GC. If you remove an entry from a skiplist, it will be stashed away on some kind of garbage list. Deallocation happens periodically after every 128 skiplist operations, assuming only one thread is accessing it. Deallocation could be delayed for longer if multiple threads are accessing it.

This mechanism is necessary for efficiency under concurrency. The core idea of epoch-based GC is that we pessimistically assume another thread is accessing the skip list while we're removing entries, so deallocation must be delayed a bit (hopefully not for too long, but some delay is unavoidable).

[ss025]

@stjepang adding more context to @Jarves42 => is there any way to force de-allocation if we know for sure that no thread will be accessing old entries after 2 min. What we are observing is, memory is continuously increasing. We are running an HTTP server that accesses Skiplist to serve requests. If we stop serving requests then it takes 2-3 hours to release memory.

There isn't a great way to do this, but you can call crossbeam_epoch::pin().flush() when idle, which will try to clear up some garbage (not all garbage at once).