{"push_id":1223484028,"size":2,"distinct_size":2,"ref":"refs/heads/master","head":"fa6dc010a20b6eb175d92d05651972651278e06f","before":"a7bff697baa062c8f6b8fb760eacf658712b611a","commits":[{"sha":"06a191b8dec693c74c4d3e8347a89dc8596b42fd","author":{"name":"m3b","email":"2ecf65b168d19d1dbd0831ac55bbb7a326b8e150@google.com"},"message":"fix problems in LevelDB's caching code\n\nBackground:\n\nLevelDB uses a cache (util/cache.h, util/cache.cc) of (key,value)\npairs for two purposes:\n- a cache of (table, file handle) pairs\n- a cache of blocks\n\nThe cache places the (key,value) pairs in a reference-counted\nwrapper.  When it returns a value, it returns a reference to this\nwrapper.  When the client has finished using the reference and\nits enclosed (key,value), it calls Release() to decrement the\nreference count.\n\nEach (key,value) pair has an associated resource usage.  The\ncache maintains the sum of the usages of the elements it holds,\nand removes values as needed to keep the sum below a capacity\nthreshold.  It maintains an LRU list so that it will remove the\nleast-recently used elements first.\n\nThe max_open_files option to LevelDB sets the size of the cache\nof (table, file handle) pairs.  The option is not used in any\nother way.\n\nThe observed behaviour:\n\nIf LevelDB at any time used more file handles concurrently than\nthe cache size set via max_open_files, it attempted to reduce the\nnumber by evicting entries from the table cache.  This could\nhappen most easily during compaction, and if max_open_files was\nlow.  Because the handles were in use, their reference count did\nnot drop to zero, and so the usage sum in the cache was not\nmodified by the evictions.  Subsequent Insert() calls returned\nvalid handles, but their entries were immediately evicted from\nthe cache, which though empty still acted as though full.  As a\nresult, there was effectively no caching, and the number of open\nfile handles rose []ly until it hit system-imposed limits and\nthe process died.\n\nIf one set max_open_files lower, the cache was more likely to\nexhibit this beahviour, and cause the process to run out of file\ndescriptors.  That is, max_open_files acted in almost exactly the\nopposite manner from what was intended.\n\nThe problems:\n\n1. The cache kept all elements on its LRU list eligible for capacity\n   eviction---even those with outstanding references from clients.  This was\n   ineffective in reducing resource consumption because there was an\n   outstanding reference, guaranteeing that the items remained.  A secondary\n   issue was that there is no guarantee that these in-use items will be the\n   last things reached in the LRU chain, which actually recorded\n   \"least-recently requested\" rather than \"least-recently used\".\n\n2. The sum of usages was decremented not when a (key,value) was evicted from\n   the cache, but when its reference count went to zero.  Thus, when things\n   were removed from the cache, either by garbage collection or via Erase(),\n   the usage sum was not necessarily decreased.  This allowed the cache to act\n   as though full when it was in fact not, reducing caching effectiveness, and\n   leading to more resources being consumed---the opposite of what the\n   evictions were intended to achieve.\n\n3. (minor) The cache's clients insert items into it by first looking up the\n   key, and inserting only if no value is found.  Although the cache has an\n   internal lock, the clients use no locking to ensure atomicity of the\n   Lookup/Insert pair.  (see table/table.cc:  block_cache->Insert() and\n   db/table_cache.cc:  cache_->Insert()).  Thus, if two threads Insert() at\n   about the same time, they can both Lookup(), find nothing, and both\n   Insert().  The second Insert() would evict the first value, leaving each\n   thread with a handle on its own version of the data, and with the second\n   version in the cache.  It would be better if both threads ended up with a\n   handle on the same (key,value) pair, which implies it must be the first item\n   inserted.  This suggests that Insert() should not replace an existing value.\n\n   This can be made safe with current usage inside LeveDB itself, but this is\n   not easy to change first because Cache is a public interface, so to change\n   the semantics of an existing call might break things, second because Cache\n   is an abstract virtual class, so adding a new abstract virtual method may\n   break other implementations, and third, the new method \"insert without\n   replacing\" cannot be implemented in terms of the existing methods, so cannot\n   be implemented with a non-abstract default.   But fortunately, the effects\n   of this issue are minor, so this issue is not fixed by this change.\n\nThe changes:\n\nThe assumption in the fixes is that it is always better to cache\nentries unless removal from the cache would lead to deallocation.\n\nCache entries now have an \"in_cache\" boolean indicating whether\nthe cache has a reference on the entry.  The only ways that this can\nbecome false without the entry being passed to its \"deleter\" are via\nErase(), via Insert() when an element with a duplicate key is inserted,\nor on destruction of the cache.\n\nThe cache now keeps two linked lists instead of one.  All items\nin the cache are in one list or the other, and never both.  Items\nstill referenced by clients but erased from the cache are in\nneither list.  The lists are:\n- in-use:  contains the items currently referenced by clients, in no particular\n  order.  (This list is used for invariant checking.  If we removed the check,\n  elements that would otherwise be on this list could be left as disconnected\n  singleton lists.)\n- LRU:  contains the items not currently referenced by clients, in LRU order\n\nA new internal Ref() method increments the reference count.  If\nincrementing from 1 to 2 for an item in the cache, it is moved\nfrom the LRU list to the in-use list.\n\nThe Unref() call now moves things from the in-use list to the LRU\nlist if the reference count falls to 1, and the item is in the\ncache.  It no longer adjusts the usage sum.  The usage sum now\nreflects only what is in the cache, rather than including\nstill-referenced items that have been evicted.\n\nThe LRU_Append() now takes a \"list\" parameter so that it can be\nused to append either to the LRU list or the in-use list.\n\nLookup() is modified to use the new Ref() call, rather than\nadjusting the reference count and LRU chain directly.\n\nInsert() eviction code is also modified to adjust the usage sum and the\nin_cache boolean of the evicted elements.  Some LevelDB tests assume that there\nwill be no caching whatsoever if the cache size is set to zero, so this is\nhandled as a special case.\n\nA new private method FinishErase() is factored out\nwith the common code from where items are removed from the cache.\n\nErase() is modified to adjust the usage sum and the in_cache\nboolean of the erased elements, and to use FinishErase().\n\nPrune() is modified to use FinishErase() also, and to make use of the fact that\nthe lru_ list now contains only items with reference count 1.\n\n- EvictionPolicy is modified to test that an entry with an\noutstanding handle is not evicted.  This test fails with the old cache.cc.\n\n- A new test case UseExceedsCacheSize verifies that even when the\ncache is overfull of entries with outstanding handles, none are\nevicted.  This test fails with the old cache.cc, and is the key\nissue that causes file descriptors to run out when the cache\nsize is set too small.\n-------------\nCreated by MOE: https://github.com/google/moe\nMOE_MIGRATED_REVID=123247237","distinct":true,"url":"https://api.github.com/repos/salewski/leveldb/commits/06a191b8dec693c74c4d3e8347a89dc8596b42fd"},{"sha":"fa6dc010a20b6eb175d92d05651972651278e06f","author":{"name":"sanjay","email":"7f4c7d3911be3d3874cd0b021e62f1bd3f31f44f@google.com"},"message":"A zippy change broke test assumptions about the size of compressed output.\nFix the tests by allowing more slop in zippy's behavior.\n-------------\nCreated by MOE: https://github.com/google/moe\nMOE_MIGRATED_REVID=123432472","distinct":true,"url":"https://api.github.com/repos/salewski/leveldb/commits/fa6dc010a20b6eb175d92d05651972651278e06f"}]}
{"actor":{"display_login":"salewski"}}