ChainedFastBackend should not invalidate the whole fastBackend when doing a Set()

Major + Performance tags: Very great catch!!!

Very, very interesting :)

This will need to be profiled.

The problem with keeping the cache tags for example is that we have to check them every time we fetch caches. That will likely add quite a few additional DB queries, we at least need to know how many exactly. Because we will definitely trade some runtime performance on completely warm caches with being faster if changes happen.

On the other side, as I mentioned in the other issue, every time we at least only just one cache tag, we completely invalidate every fast chained backend, likely repeatedly (we usually don't do a single invalidation but multiple, through multiple calls). So every saved node, user, comment, ... invalidates the fast chained backends.

Another idea for optimization would be to somehow track what cache tags are really used by a backend. Not sure about an efficient and safe way to do so. We could have a cache entry that e.g. has a list of the first few characters and wether we have any cache tags or not.. that could e.g. allow us to filter out any node*, user*, 4xx* and so on cache tags.

I don't think the invalidate on terminate idea is going to work. For starters, it will definitely break tests as they need to be able to do changes in the test runner process that will invalidate caches on child web requests.

... Maybe a concept similar to fastChainedBackend, but for cache tags, would do the job....

Yes, that would be nice :)

Just me thinking out loud:

Best theoretical strategy would be:

- 1. global timestamp / atomic counter - if valid, receive items directly without checking cache tags (no need to check tags if there was no write / invalidation at all) - that is like a mega cache tag
- 2. Retrieve from fast BE with cache tags as usual
- 3. Retrieve from consistent backend with cache tags as usual

Probably contrib

Nice results!

It makes a lot of sense to store cache tags in the same fashion.

Beware of one thing, APCu / memcache / redis (to some extent) are volatile backends, which means that it is difficult to decide between:

NULL and 0 as a checksum provider.

There is two strategies:

a)

- Write through to MySQL backend (as done here)
- But then also fetch any NULL entries from MySQL backend (to see if they vanished in between)

b)

- Write all tags only to volatile backend during cache get
- Then if encountering NULL => we know its a "cache miss"

I still think overall the whole cache tags API could need/use an "atomic counter" concept for the BE storage, the same as the fast chained backend itself could use it.

Obviously there are many ways to achieve the same goals, so these are just some ideas / thoughts.

Keep up the great work!

#18: Yes, but cache tags don't need the full cache API. Overall they are just atomic counters. That is what I mean with that API.

Without the patch - current head:

Wall time:

Warm home page: 208ms
After saving a node: 375ms

Queries:

Warm home page: 93
After saving a node: 160

With the patch:

Wall time:

Warm home page: 172ms (-36ms ~ -17%)
After saving a node: 341ms (-34ms ~ -10%)

Queries:

Warm home page: 47 (-46 ~ -50%)
After saving a node: 106 (-54 ~ -33%)

Wow.

Can you describe your environment? Operating system, PHP version, rough hardware description, etc.

Awesome work here!

This is something we can definitely do in a minor release, and might be able to do in a patch release - new code is added but there's no deprecation and it's mostly implementation details.

I repeated the test scenario on Debian Jessie (PHP 5.6) with a remote (well tuned) MySQL-Server.

One node

Wall time:

Warm home page: 316ms
After saving a node: 663ms

Queries:

Warm home page: 76
After saving a node: 171

With the patch:

Wall time:

Warm home page: 309ms
After saving a node: 502ms

Queries:

Warm home page: 54
After saving a node: 75

1000 nodes

Wall time:

Warm home page: 389ms
After saving a node: 767ms

Queries:

Warm home page: 76
After saving a node: 148

With the patch:

Wall time:

Warm home page: 389ms
After saving a node: 510ms

Queries:

Warm home page: 54
After saving a node: 85

I think the savings are impressive. Nice work! Each database query that can be saved is worth a lot. The database is the hardest part to scale...

#29: I am currently working on improving chained fast and my thoughts go into a similar direction.

Also we should potentially support async in the future. So if we added a completely new Cache API V2 we should be sure we can make use of async cache fetches in the future.

--

However:

This issue is complicated and also the supercache is pretty complicated.

Can we split this up into tiny steps instead of a full re-architecture?

Yes, the raw cache backends are awesome, but I cannot see why they cannot be implemented on top of the existing structure.

#33 Thanks for the top-level explanation.

I also realized that it would save a lot of write-traffic if the data in the cache currently is the same (and had not been invalidated) to not write it through and yes the timestamp makes that pretty impossible - though just refreshing the timestamp would still be simpler.

It would still be good if we started the other way round:

What can we do with the cache backends we have right now and then gradually work our way to where we can just plug-in the raw cache backend API and be done.

I have check the patch again and it needs work:

The reason is that

- For ChainedFast it is possible to invalidate at the end of the request. The biggest problem is:

If you have process A taking 2s and process B taking 30s on web heads A and B (or on drush and cli), when we write invalidations at the end of the request, then all caches build with data from A is invalid.

Example (that made it more clear to me):

- Block has text 'HI'

- Block is stored in A and B with 'Hi'

- Block is updated in B with 'Hello World' and B takes 30s, the cache for the block is invalidated, but the timestamp / counter / cache tags are not updated until end-of-request.

- A is retrieving the Block with text 'Hi' from APCu, because the backend is not invalidated.

- A is storing the Block text 'Hi' in the page cache for '/'.

Now B finishes and invalidates the bin counter and the cache tags.

- Now the Block in A is invalid (both in APCu and the DB) and the cache in '/' is also invalid.

So 30s of caches we can't use as it is just now invalid, but on the other hand we could use the older data during that time.

But it depends the 'when-do-users-see-new-content' on the longest running request.

A possible solution for that is a pseudo-timeout listener in core / utility component, which means that you can do e.g.:

\Drupal::service('timeout')->setTimeout($callable, 500);

We would need to add code to common services to call the timeout service to check if something is scheduled, but that would work as we have some very often called functions, e.g. hook invocations, event listeners, database layer, cache layer, etc.

I likely would start with the hook / event listeners as its unlikely something calls no hooks.

One problem is guzzle, because that can lead to a long wait time for a third party service, but we could flush all data before that.

Here's a possible approach that should be low-risk:

Process A writes, last_write_timestamp =1

Process A writes again, checks last_write_timestamp - it’s still 1, so doesn't bother to increment again.

Process B writes, it hasn’t written already, so last_write_timestamp gets updated to 2.

Process A writes again, last_write_timestamp is 2, this is different from 1, so it writes it as 3.

That way if you're doing something with drush locally, you'd only get a single invalidation per-request (at the start, rather than the end).

It would mean more reads from the backend doing the setting, but they should be cheap compared to whatever else it's doing if it's writing cache items.

The problem with invalidating on the end-of-request and why supercache is flawed in that respect (unless my example can be disputed) is when using cache collectors, because those don't use invalidation, but just cache setting.

Cache collectors, create a lock, get the data(), merge key into the array(), set the data(), release the lock()

However if the invalidation is happening just at the end of the request, then the cache collector has written invalid data, which is valid.

So either we need a ->merge() operation on our caching layer, which means the CF backend would only read from the consistent backend for the cache_get().

That has the downside that you always have a DB query, even though the data would match the rest of the bin still perfectly.

OR

We set a cache tag for the bin itself, which we increment on invalidations and store within the cache item.

But that has the downside that the cache collector could become completely invalid not just on the fast, but also in the consistent backend.

OR

We do what catch suggested in #37, which is indeed very low-risk.

--

But as it stands supercache (and the patch in this issue) would - according to my understanding, not work properly with cache collectors as invalid data could be persisted in the end.

I like all the ideas however very much, also I think we could just extend our cache backends with ->counter(), etc.

#40 Thanks for the response.

Even when reading the new supercache code, I think there is still a race condition related to the timestamp.

HEAD broken example:

- Any invalidation in the request => $this->last_invalidation = now(), $this->lastWriteTimestamp = now(), $consistent->get('last_write_timestamp') == now()

AND now() == t(42)

- Now request B comes in, reads t(42) and $this->last_invalidation = NULL, $this->lastWriteTimestamp == $consistent->get('last_write_timestamp') == 42

- So B reads 'foo' from consistent, it stores:

$fast_backend->set('foo', ['bar']) // t(80)

- Now we have a cache->set('foo', ['bar', 'baz']);

- And $created is internally set to t(100) on 'A' and in Consistent Backend

- We see that $this->last_invalidation === $consistent->get('last_write_timestamp'), but we always write, so now() == 120

- Now request on head B reads 'foo' _again_ to write the new data (which is typical for cache collectors), but $this->lastWriteTimestamp == 42 still and statically cached.

- Now request B checks 'foo', which has t(80), which is > 42 => valid

=> B has read invalid data

=> HEAD fails for our static caching case, too.

=> => => Cache collectors are evil

---

Or rather cache collectors MUST have a current timestamp, so:

lock();

// This is new.
if ($this->cache instanceof ResettableCacheInterface) {
  $this->cache->reset();
}

$cache = $this->cache->get($cid);
$items = $cache ? $cache->data : array();
$items = array_merge($items, $updated);
$this->cache->set($cid, $items);

unlock();

#40: I made more examples now.

The first was just a problem with invalid caches that need to be thrown away, but cache collectors are just plain broken by this.

Usually we have the pattern:

- cache miss => rebuild => cache set (we never read before write)

And for dependent data:

- cache miss => rebuild => cache set + tags for dependencies we read in rebuild

Any cache write for dependencies must also invalidate the tag first, so we usually do _just_ invalidate and rebuild on demand and mostly depend on cache tag based invalidation now.

So usually invalidation is completely different from updating the cache. They are two different operations.

That works quite well.

But cache collectors do:

- cache get - cache miss - partial rebuild - ... - end of request - lock() - cache get - update - cache set - unlock()

And while we accept a certain degree of race there, due to statically caching the partial rebuild, the time between cache get and cache set is quite short, while a statically cached timestamp could be valid and is very likely valid due to the first cache get().

The main reason why catch's approach cannot work with the current way this works, is that the fast backend creates a _NEW_ expire timestamp(), as if it was valid now().

e.g. we probably need a ChainedFastCacheableBackendInterface for APCu and add:

$this->fastBackend->setWithMetadata($item->cid, $item->data, [], ['created' => $item->created]);

OR

$this->fastBackend->setWithCreated($item->cid, $item->data, [], $item->created);

if we are sure we never need to overwrite any other metadata.

BECAUSE IF ->created always matches what is in the DB or the timestamp if it is larger, then we still have race conditions, however they are less, because reading from consistent and writing to fast is no longer an operation that refreshes the cache item. So this is likely something we should do in any case.

- Cache item enters cache at t=20 in some web head

Case A:

- A invalidates the bin for some other item (t=40)
- B reads the item from consistent, and stores it with t=40 (=max(20,40)) into its fast cache backend
- A invalidates the bin again (t=60), but does not write the ts
- B reads the item from fast cache backend as ->created t=40 matches t=40 of last_write_ts
- B writes it again, the item was valid, but the bin was not => FINE

Case B: Clear invalidation / Delete

- A invalidates the bin for some other item (t=40)
- B reads the item from consistent, and stores it with t=40 (=max(20,40)) into its fast cache backend
- A invalidates the cache item itself by clearing it (t=60), but does not write the ts
- B reads the item from fast cache backend as ->created t=40 matches t=40 of last_write_ts
- B writes it again, the item was valid, but the consistent item was not => NOT FINE

=> on clears we need to write through to the bin in every case

Case C: Cache->set()

- A invalidates the bin for some other item (t=40)
- B reads the item from consistent, and stores it with t=40 (=max(20,40)) into its fast cache backend
- A sets the cache item to something else (t=60), but does not write the ts
- B reads the item from fast cache backend as ->created t=40 matches t=40 of last_write_ts
- B writes it again, the item was valid, but the consistent item was not => NOT FINE

=> on set we need to write through to the bin in every case

Case D: Cache Tag invalidation

- A invalidates the bin for some other item (t=40)
- B reads the item from consistent, and stores it with t=40 (=max(20,40)) into its fast cache backend
- A invalidates the tags of the item (t=60), but does not write the ts
- B reads the item from fast cache backend as ->created t=40 matches t=40 of last_write_ts and as there are no tags, cache tag invalidation does not interest
- B writes it again, the item was valid, but the consistent item was not => However as the cache tags had been cached as well from the first consistent read, this works by chance as it writes the item with the old cache tags, ts = 60, fast backend has ts = 60 information.

But if B reads by chance again just from the fast backend on the next request and then writes, then the data will be stored with the right cache tags suddenly. As the invalidation of the cache tag was never seen.

So the idea to store created with this, does not help to make catch' idea workable :/.

I think its possible to write test cases for the cases above.

Couple more ideas:

1. In the fast backend, keep a lastValidTimestamp and lastWriteTimestamp. lastValidTimestamp is compared against cache->created. lastWriteTimestamp is compared with the timestamp in the consistent backend, as long as they're the same, we don't update lastValidTimestamp. This ought to address the original concern in the issue summary with local writes, but without requiring cache tags in the fast backend.

2. When we cache set, get lastWriteTimestamp from both backends as well as lastValidTimestamp, compare them, and if lastValidTimestamp is updated, throw away the write. This starts to help with the race condition Fabianx mentions.

Cache collectors still need some help to get a fresh cache entry when they request it the second time (i.e. just before the write, because we want to cumulatively merge cache items). I wonder whether we could always re-fetch lastWriteTimestamp whenever a duplicate cache ID is requested (requires keeping an array of already-seen cache IDs). I've seen non-cache-collector cases in the wild where the same cache item is fetched over and over in a request, but it's usually a symptom of a problem rather than by design - we static cache most things.

#45

2. The problem is that we can also have dependent caches:

e.g.

function a() {
  if ($cached = $cache->get('a')) {
    return $cached->data;
  }

  $a_data = calc_a();
  $cache->set('a', $a_data, Cache::PERMANENT, ['tag:a']);
}



function b() {
  if ($cached = $cache->get('b')) {
    return $cached->data;
  }

  $a_data = a();
  $b_data = calc($a_data);
  $cache->set('b', $b_data, Cache::PERMANENT, ['tag:a', 'tag:b']);
}

But because we throw away the cache tags in the fast backend and rely purely on the last-write timestamp, we never know that b depends on a.

Therefore just checking for duplicate get() (to detect CC pattern) is not enough, but we indeed have to throw away all set's() that try to set data once invalid data has been read at all from this bin.

And for this scenario not even reset() would help as even if we read a new timestamp, the data written can still be wrong.

TL;DR: If we want to support dependent caches with chained fast, then we need to push the cache tags and validate from the fast backend.

Now of course we could 'cache the cache tags' in the fast backend, but that is another discussion again.

The advantage there is that we would know a read conflict and could invalidate an invalidly written item.

Basically I think we run into the problems with both ACID and CAP here - however for a limited subset functionality and especially just cli() + web, fast chained might still work okay enough.

But therefore I think for many web servers https://www.drupal.org/project/lcache will be the better choice for 8.3.x / 8.4.x as it seems to have a good theoretical background for the concurrency model, while chained fast does seem like it does (time stamps), but actually due to the implementation has several short comings.

Obviously it makes zero sense to read the timestamp every time as it would be a round-trip to the database every time.

Another advantage is that with lcache you just have one round-trip to the database (check that there are zero transactions on a different web head) if only one web server is used, because drush does only need to write through to the transaction log, but can't read from APCu due to missing SHM segment so would not need to be put in sync.

Caveat: I have not yet checked lcache for the e.g. cache collector problem and how it resolves conflicts on the same data and dependent data.

In practice we could and should implement the same for chained_fast though, because the one webhead + cli is way easier to deal with than concurrent web heads in general.

e.g. if its the same head that wrote => no invalidation needed ever
if it is drush that wrote => always invalidate

There is still potential for races, but way more manageable.

Therefore just checking for duplicate get() (to detect CC pattern) is not enough, but we indeed have to throw away all set's() that try to set data once invalid data has been read at all from this bin.

That's what #45.2 should deal with though. i.e. we optimize the case where we've only written locally, but we're more aggressive about throwing away items where another web head has written in-between. Between the two we should get better consistency with ~neutral performance.

The issue with cache collectors is that in this case, we don't want to throw away the write (unless there was an invalidation), but we do want to get a fresh item before we write back.

Also #45 would improve the situation for cache collectors. If we add a reset() (to force updating the timestamp, in this case it's because we're about to write and need to check something first), then we get the fresh cache entry. If that cache entry was written by another process and it shares the same local cache then we get a proper cumulative cache write, because lastValidTimestamp doesn't need to be updated (assuming the bin hasn't been written on another web head). If another web head has written to the bin, then we end up discarding it, but that protects us against invalidations.

There's a higher risk of discarding valid cache entries the more web heads are added of course.

The issue is duplicated by #3334489: ChainedFastBackend invalidates all items when cache tags are invalidated