Empty cache stampede protection

nice - * sub

sub

I like the way this works, will be testing it. The only comment I have right now is that, since locks are global, in order to avoid any possible namespace collisions, I think it makes sense to prefix $full_key with memcache_. Like the attached patch.

Chx mentioned on Twitter that previous work on the stampede problem had been done here: #295738: Cache stampede protection and the code appears to be attempting to handle the stampede case in the dmemcache_get() function. Do we have a good handle on why the existing code would be failing to catch some of the stampedes? Is it a problem of requests taking longer than the default 15 second semaphore?

Right, if memcache needs to be restarted or forcefully flushed for any reason (or, even if the key just doesn't exist yet, such as an aged key that was removed by memcache to make room for something else, etc), then that situation is not covered by the existing memcache code. In that case, all threads will rebuild the value to be cached without regard for each other.

I do agree that making the semaphore work directly from the memcache is appropriate for this. Overall, I agree this patch looks good. I'm not sure that making the number of retries be the same as the number of seconds for the semaphore TTL is appropriate, though.

@der I think that would indeed be a useful statistic.

The patch does a great job in preventing great server killing stampedes. Unfortunately, the benchmark on a production site suffering from stampedes was bad enough that I reverted it.

Benchmark: 20 concurrent admin users hitting a page for 4 minutes.

siege -i -c20 -H "Cookie:[sessioncookie]" --time=4M example.com/taxonomy/term/%

BEFORE PATCH
Transactions: 1766 hits
Availability: 99.94 %
Elapsed time: 239.49 secs
Data transferred: 47.16 MB
Response time: 2.18 secs
Transaction rate: 7.37 trans/sec
Throughput: 0.20 MB/sec
Concurrency: 16.11
Successful transactions: 1766
Failed transactions: 1
Longest transaction: 22.49
Shortest transaction: 1.27

AFTER PATCH
Transactions: 1432 hits
Availability: 100.00 %
Elapsed time: 239.77 secs
Data transferred: 37.62 MB
Response time: 2.84 secs
Transaction rate: 5.97 trans/sec
Throughput: 0.16 MB/sec
Concurrency: 16.94
Successful transactions: 1432
Failed transactions: 0
Longest transaction: 5.87
Shortest transaction: 1.

These numbers did surprise me, as I didn't see anything in the patch that looked particularly naughty. I'll try profiling the changes and let you know what I find out.

subscribe

Sub. Waiting for more benchmarks.

There were a number of issues at play on that benchmark. The site had been running 1.7 on a lower version of memcache (1.2) which we believe results an abysmal hit rates. So the unusually high miss rate + high number of memcached requests are a reasonable explanation for the difference in results. Since this feature can be turned on and off, this is not a blocker.

The documentation for this feature should maybe make a note about the overhead in cases of high request rate and high miss rate in addition to recommending protecting against stampedes at a higher level if possible (which is what we ended up doing).

So I agree that relying on the core locking inc would be rough, but if we make this configurable and disabled by default, then I'm not sure why we couldn't use the lock API and just recommend using the memcache lock inc in docs - if people don't read the docs, they won't know this is there either.

I'd like to see this functionality merged in, but as cache notes above I think we should use the locking API. Implementing the locking logic twice (once in memcache-lock.inc and now again in your patch in dmemcache.inc) seems wasteful and increases the possibility of introducing a bug. The patch should include documentation that explains what it is, how to enable it, and why memcache-lock.inc should be enabled at the same time.

Here's a re-roll using lock.inc, I didn't include the statistics changes here, since I think we'd be better off adding statistics support to memcache-lock.inc if that's desired. I haven't tested this yet, just wanted to refresh this and there's a few discussion points below.

Looking at this again I had a couple more concerns, which are hopefully valid (and if so should be addressed by the patch).

First, dmemcache_set() is always going to try to delete the lock, even if it's never been acquired. This is going to add overhead to every dmemcache_set() even though we only need to release the lock when it's been acquired. To avoid this, I checked the $lock global to see if the cid is in there - if it is, we release it, if not, while it's theoretically possible one process might be able to release a lock held by another one, that's sufficiently rare I don't think we need to account for it.

Also I don't have specific examples to show, I have concerns that leaving apache threads hanging waiting on locks could cause its own problems - as requests could mount up, leading to either max clients being exceeded or swapping. As well as this, if a particular cache item is extremely volatile for some reason, it's possible that we will get race conditions with the locking itself.
For example:

Process 1 acquires a lock.
Process 2 waits.
Process 1 releases the lock.
Process 3 acquires the lock.
Process 2 continues waiting.

To avoid this situation from getting too bad, I removed the maximum tries logic. There are now two variables, memcache_stampede_semaphore and memcache_stampede_max_wait. If neither are set, the values default to 15 and 15 / 3 = 5 respectively.

The idea is that the process acquiring the lock can get that lock for 15 seconds, but the maximum time any individual process will wait for the lock to be released is 5 seconds. This allows those other processes to pass through after they've waited around for a bit, while still allowing the lock to reduce overall load on the server while it's held. If for some reason a lock_release() failed, then again there is still the fallback of a maximum 5 second wait.

Marking CNR.

Also we should get #969998: Shorter lock_wait() polling time in before this or at a minimum very close together.

Thought about this more and realised all of this logic is better handled in cache_get()/cache_set() - we don't want dmemcache.inc to be dependent on the locking framework - also locking and wildcards use dmemcache_set() etc. and those don't need stampede protection (in fact that could add bugs itself).

This no longer applied after recent commits to memcache.inc.

While re-rolling I realised it (and the original patch here) only applied to items that don't exist at all in the memcache bin, however that is an extremely rare case (more or less limited to memcache server restarts and new cache objects), with most invalidation of cache items happening in memcache.inc

So a summary of the latest patch:

- since this now uses lock.inc, I made the handling of expired items also depend on the new memcache_stampede_protection variable.

- any item that's invalid, for whatever reason, has stampede protection now - not just items that are completely missing from memcache.

- we only return expired items if that's the only reason they're invalid, otherwise we have to use lock_wait() to avoid the stampede. I feel like we could possibly do something here with items that are cache misses due to cache_clear_all() (i.e. when cache_lifetime doesn't kick in) - i.e. return stale entries for those too if this setting is enabled, but don't want to introduce that with the initial patch.

- it adds three new variables - memcache_stampede_protection, memcache_stampede_wait_time and memcache_stampede_wait_limit - these are documented in comments in memcache.inc and README.txt. Short version is it tries to balance the need for stampede protection vs. the need to not have individual requests waiting too long, and the possibility for lock_wait() to exit immediately before another process acquires a lock on a cache item.

- there is a lot of code changed here, 90% of this is the move of the original stampede protection from dmemcache.inc to memcache.inc, and the conversion of the return FALSE; in cache_get() to a long if/elseif and a single return at the end.

Patch passes tests with and without the stampede protection enabled.

I'm about to run our load tests with the setting enabled and disabled to confirm it's neutral or better. If that comes back OK then I'll go ahead and commit this, while it's new code, it's disabled by default. I'd be concerned about putting 1.9 out without this available, since http://drupal.org/node/1134242 removes minimum cache lifetime handling for cache_clear_all('*', $table, TRUE); - while that's good for correctness, it could mean more cold start issues.

Minor update - added back 'memcache_' prefix to lock names.

Here's load test output with and without the stampede protection enabled:

Before:

Patch with no stampede protection (this is the same as my baseline too).

STAT total_connections 12058
STAT cmd_get 121686
STAT cmd_set 57798
STAT get_hits 63775
STAT get_misses 57911
STAT incr_hits 0
STAT bytes_read 67898312
STAT bytes_written 169266388
STAT evictions 6220
STAT total_items 57798

Hit rate: 52.4000%
Miss rate: 47.5900%

HTTP return codes:  20x(12045) 30x(1331) 40x(2)  50x(0)
 200: 12045
 302: 1331

Pages per second: 21.16

Patch with stampede protection enabled:

STAT total_connections 11687
STAT cmd_get 231828
STAT cmd_set 113131
STAT get_hits 118542
STAT get_misses 113286
STAT incr_hits 0
STAT bytes_read 82905912
STAT bytes_written 171613850
STAT evictions 6715
STAT total_items 113084

Hit rate: 51.1300%
Miss rate: 48.8600%

HTTP return codes:  20x(11674) 30x(1297) 40x(2)  50x(0)
 200: 11674
 302: 1297

Pages per second: 20.52

You can see that for each get_miss, we've added additional sets - that's the lock being acquired (and why you don't want to use this with core's lock.inc). However, pages per second stays around the same, and bytes read/bytes written only increases a little bit, same with overall hit rate. Since the load tests have a very high cache miss rate, this looks about right to me - we've got more memcache activity, but about the same in terms of actual performance.

Since this is optional and disabled by default, I'm going to go ahead and commit it to dev, it's one thing that would be good to test with the rc on a real site before we release a full 6.x-1.9 though.

I think looking at these memcache stats there is a slight optimization we can make in memcache-lock.inc, will open an issue for this.

Committed with http://drupalcode.org/project/memcache.git/commit/a01034d, moving this to 7.x to be forward ported.

Bumping. This is the last big patch apart from memcache_admin changes that hasn't made it into 7.x yet. Major since I'd like to get this in before a 7.x-1.0.

Forward ported this to 7.x.

The comit of the 7.x patch introduces a new syntax error.
http://drupalcode.org/project/memcache.git/blobdiff/0de438f34fd72eba20bb... :

+      // Finally, check for wildcard clears against this cid.
+      else {
+        if (!$this->wildcard_valid($cid, $cache){
+          $cache = FALSE;
+        }
       }

Closing parenthesis of the if is missing.
Attached patch adds the missing parenthesis and removes two trailing whitespaces.

Thanks, committed to 7.x.