Merge lp://staging/~mkanat/loggerhead/synchronize-lru_cache into lp://staging/loggerhead

Max,

Well done on tracking down the problem and thanks for the patch. Aren't threading problems fun? :-)

My main concern with the proposed change is that I'd prefer the Cache object to have the intelligence to Do The Right Thing wrt locking, rather than it being left up to the client to guard access to it. As it stands, we're deciding to use an LRU cache in apps/branch.py and paying the consequences through increased code complexity several layers deeper. What do you think about having a decorator class that provides the synchronized access? E.g. changing the cache creation line to be something like ...

  graph_cache = ThreadSafeCache(bzrlib.lru_cache.LRUCache(10))

and introducing ThreadSafeCache() as the layer with the RLock?

OTOH, this bug is critical and perhaps we ought to just land it as is, particularly as John is looking to rework the caching architecture Real Soon Now anyhow.

Any second opinions?

> Well done on tracking down the problem and thanks for the patch. Aren't
> threading problems fun? :-)

  Fun indeed. :-)

> What do you think
> about having a decorator class that provides the synchronized access? E.g.
> changing the cache creation line to be something like ...
>
> graph_cache = ThreadSafeCache(bzrlib.lru_cache.LRUCache(10))
>
> and introducing ThreadSafeCache() as the layer with the RLock?

  I thought about that, and the problem is that it would depend to some degree on implementation details of lru_cache--if the client started using it in different ways, or if the lru_cache implementation changed in some ways, we'd have to start adding locks in different places.

  John has already said that he's not going to make the LRUCache itself thread-safe (see the bug), and the only accesses we make into to it are via this interface, so I think the simplest and most forward-compatible solution is to put the locking in our client code.

Sounds fine to me, and I've been running it for a few days without problems.

I should comment here a little bit. I'm a bit surprised that this actually handles what we want it to.

Specifically, RevInfoMemoryCache is created for each History object created, and a new one is created for each HTTP request (if I sorted out my info correctly.)

As such, *each* HTTP thread ends up with its own lock around the cache. And you don't end up doing much of any cross-thread protection, which was the whole point.

I could probably be convinced to add a potential locking primitive to LRUCache. I wanted to avoid the overhead, but we can just default to None, and allow callers to set a Lock object that we'll respect. Something that says "if self._lock is not None: self._lock.acquire()".

I think that __getitem__ can be protected after the "if node is mru:" check. If two threads are accessing different items concurrently, there is no clear-cut MRU, and at worst the one that thinks it is already 'most recent' will just be 1 step behind.

If this *does* seem to fix the problem, my guess is that it only does so by playing tricks with threads and the GIL, and causing sync points. (aka, by accident)

Check out: lp:///~jameinel/bzr/lru_locking

It still needs tests, and possibly 'live-fire' testing, hammering the cache structure with lots of threads. However, I'm fairly sure that I've gotten a minimal locked section (we lock as little as possible), while still maintaining correctness.

LRUCache.add() is not specifically thread-safe if you have cleanups and are adding different values for the same key. We might want to consider putting a big lock around all of add() for that case, but callers could also do that...

The main reason I poked at it was because you can't get 'fine-grained' locking around the LRU double-linked-list unless it is implemented in the cache itself.

Okay, John is right--the bug is not fixed. I just ran into it on bzr.mozilla.org again.

For loggerhead, a quick workaround is to make the lock global instead of a per-instance item.

We do have cleanups, and I suppose it's possible for us to be updating an existing branch with a new cache, right? So I think we'll need this lock in loggerhead anyway.