[concurrency-interest] some MapMaker design decisions

Bob Lee crazybob at crazybob.org
Tue May 11 09:44:29 EDT 2010


Charles,

See the thread you started "MapMaker listener and removal notification." Ben
is already doing the right thing:

"Yep, that's exactly how my CL implements it, with an internal listener
queue per segment, a Receiver passed to makeXXX(), and invokation on the
clients thread outside of any locks on a mutate."

On Mon, May 10, 2010 at 10:01 PM, Charles Fry <fry at google.com> wrote:

> a) Should eviction notifications be callbacks, or should we simply add
> evicted entries to a queue that users could then poll? Callback
> notifications definitely seem conceptually simpler from the users
> perspective, but they do require the execution of the callback code.
> Using a queue makes the job of performing eviction simpler, but then
> is more complicated for users to integrate with.
>

Queue inside segment, call back in client threads, outside of locks. Best of
both worlds.


> b) If eviction notifications are made using callbacks, where should
> the callback be executed? We could execute them on user threads when
> they make other calls on MapMaker maps, but that implies that
> exceptions and blocking within callbacks could then impact threads
> performing other operations on the map. The other obvious alternative
> would be to require users to provide an ExecutorService for executing
> callbacks, but that feels a bit overkill when all you really want is
> an eviction notification.
>

A user-provided ExecutorService is not viable. The user could just implement
execute() to execute the task in the task immediately in the current thread.


> c) Is it worth doing removal notifications, that include a callback
> when remove is called manually, or is it sufficient to limit
> notifications to eviction events?
>

This was also discussed in the thread. The callback should only be invoked
for automatic evictions. This enables the user to differentiate between
manual and automatic removals. That's harder if you invoke the callback in
both cases.


> d) While there are plenty of algorithms for concurrent
> recency/frequency based eviction policies, it is also simple to
> maintain a mutation queue that records a memento of each modification
> operation, occasionally locking and applying them on a single thread.
> The overhead of such a mechanism is trivial, and it allows the exact
> application of non-concurrent eviction algorithms. It has the minor
> caveat of requiring care to be taken with elements that are removed
> from the cache while one of their mutation mementos is still enqueued.
> Are there other concerns to be aware of, or is this a reasonable
> approach?
>

I still plan to test the LRU algorithm Josh, Jesse and I came up with. It's
incredibly light on memory, CPU and locking. We can experiment with other
algorithms and consider them if they significantly increase retention in
real world code without too much overhead.


> e) With respect to size eviction, our initial thought was to put a
> hard limit on the size of each segment. This has the advantage of
> being very simple conceptually, and the notable disadvantage of
> applying the eviction algorithm at the segment level instead of
> globally. If a mutation queue is used to manage evictions then it can
> very simply be extended to apply them globally instead of per-segment.
> Are there other major considerations to be aware of here? Does it
> sound reasonable to make global eviction decisions?
>

We shouldn't introduce a map-wide lock or CAS. Heavy CAS contention across
cores can actually be slower than grabbing a lock.

Bob
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20100511/5ead3456/attachment.html>


More information about the Concurrency-interest mailing list