phongn commented on PR #13255: URL: https://github.com/apache/trafficserver/pull/13255#issuecomment-4722541470
@masaori335 in my initial benchmark [private PR](https://github.com/phongn/trafficserver/pull/2#issuecomment-4665036259) you asked > I heard S3-FIFO is lock free, which means we can improve it more by relaxing Stripe Mutex lock contention before RAMCache access. This is unfortunately not true for our internal implementation using existing ATS data structures and conventions. Quoting Claude: > The property the developer is thinking of is real: because S3-FIFO is FIFO-plus-a-counter, a hit needs **no list reordering** — just a 2-bit bump. That's what makes it amenable to a concurrent/lock-free implementation, unlike LRU/CLFUS which mutate list order (and CLFUS recomputes value) on every hit. > > But our RamCacheS3FIFO.cc realizes none of that concurrency. As written it is **not thread-safe**, let alone lock-free: > > * intrusive doubly-linked segment lists and a **chained hash table that rehashes on growth** (`_resize_hashtable`); > * plain non-atomic counters (`_s_bytes`, `_m_bytes`, `_g_count`, `_objects`, `_nentries`); > * entries freed with `THREAD_FREE`; > * and crucially, `get()` **is itself a mutator** — it does `e->freq++` (a non-atomic read-modify-write) and assigns `*ret_data = e->data`. Two concurrent gets on the same bucket already race. > > Getting to the theoretical property would mean rewriting the data structures: atomic counters, a concurrent/sharded hash map, sharded or lock-free FIFOs, and — the hard part — **safe memory reclamation** (epoch/hazard pointers) so eviction can't `THREAD_FREE` an entry a reader is touching. That's a project, not a property we inherit by picking the algorithm. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
