|Subject||Re: [Firebird-Architect] Cost of LRU|
- The cycle manager controls two read/write locks, which alternately control the current cycle
- Work threads take a shared lock on the current cycle lock when they start work on behalf of a user request and release it when it finishes
- The cycle manager thread sleeps for a period of time (one second is good). When it wakes up, it bumps the cycle number, flips the active and inactive cycle locks, and waits for exclusive lock on inactive cycle lock.
- When the cycle gets the exclusive lock, it knows that all worker threads that started in the prior cycle have finished and can execute end-of-cycle code.
- When the end-of-cycle tasks are complete, the cycle manager goes back to sleep and the process repeats
The BDB equivalents in Falcon were managed this way: When a
worker thread touched a BDB, it wrote the number of the current
cycle into the BDB. One of the end-of-cycle tasks was to scream
through the BDB list moving BDBs referenced in the prior or
current cycle to the front of the LRU. Since BDBs could be
added to the end of the BDB list with an interlocked
compare-and-swap (CAS) instruction, the LRU chain was completely
Another thing the cycle manager can be used for is managing a
non-interlocked hash table. A node can always be safely added
to a hash table with an interlocked CAS. Removing a node is
more troublesome as some thread may be walking the collision
chain for the node to be removed. With a cycle manager, a node
is removed from the collision chain with an interlocked CAS
keeping its collision pointer intact. But rather than deleting
the node, it gets put into a "node purgatory". Another one of
the end-of-cycle tasks is to grab the purgatory list head
(another interlocked CAS, setting to new value to NULL) before
waiting on the prior cycle lock, then deleting the nodes
formerly in purgatory.
The combination of cycle locks and interlocked CAS managed data
structures can make all sorts of operations completely
non-blocking. Neat stuff.
On 11/2/2014 1:46 PM, Ann Harrison aharrison@... [Firebird-Architect] wrote:
Thinking about the conference and V3 and a customer's comment that InterBase isn't as fast as it might be on a multi-processors and doesn't seem to consume much CPU, I remembered one of the things that came up in the face-off between Falcon and InnoDB. There's nothing like a hot performance race to uncover problems lurking in old code.
As Falcon increased the number of pages it cached, the cost of maintaining an LRU queue grew to about 10% of the CPU. Jim backed off to a much less precise algorithm for determining which pages to drop from cache. We found that the extra I/O cost was minimal. I won't try to explain what he did (he probably will), but my recollection was that Falcon was spending a lot of time reordering the top 200 pages - which were never going to be dropped.