For reads, 1. Use lock-free ring buffers to record the read events, don't update the eviction policy. 2. Have an array of buffers and use the key's hash to select one 3. Drop the read event if contention or the buffer is full 4. When full, use a try-lock to replay the events against the eviction policy
For writes, 1. Use a single ring buffer to record the write event. 2. If appended, schedule the replay work immediately 3. If full, block on the lock and replay. The lack of a processor / thread / goroutine id means that selecting the read buffer isn't ideal. The accesses to a hot key will contend on the ring buffer, similar to if you use lock striping. However the work involved is cheaper than locking, as you only need to acquire an array index to set its value. Because caches follow a pareto distribution the popular items will be accessed more frequently, so a few dropped events won't change this and the eviction policy should be able to prefer them. I believe the naive hash selection will be faster than sync.Pool, but the two should be compared. This scheme allows you to replace LRU with more advanced policies such as W-TinyLFU, and incorporate other features like very cheaply. I wrote a short overview of this in use, - http://highscalability.com/blog/2016/1/25/design-of-a-modern-cache.html - http://highscalability.com/blog/2019/2/25/design-of-a-modern-cachepart-deux.html and there is an early attempt to port it into Golang in https://github.com/dgraph-io/ristretto/commits/master On Tuesday, July 23, 2019 at 10:22:09 AM UTC-7, Zihan Yang wrote: > > I am trying to implement an LRU cache. Several global lru lists could be > accessed concurrently by multiple goroutines, which could be a disaster in > a machine with 24 or more cores. > > > Therefore, it would be great if I can add the item to P-local storage and > flush the batched item into the lru list as a whole. This should greatly > reduce the contention for the global lru list. > > > How can I do it? I saw some related github issues, #8281 > <https://github.com/golang/go/issues/8281> and #21355 > <https://github.com/golang/go/issues/21355>, which leads me to a project > called gls <https://github.com/jtolds/gls>, but the code seems too much > to integrate into my project (actually I'd better not include any > third-party package to avoid potential law issues). Is there any built-in > way to achieve this? > > > Thanks > -- You received this message because you are subscribed to the Google Groups "golang-nuts" group. To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/0c540295-7922-458e-a4e6-4289281cd0ec%40googlegroups.com.
