[Cache] Improve reliability and performance of TagAwareAdapter by making tag versions an integral part of item value
#42997
Conversation
|
Hey! I see that this is your first PR. That is great! Welcome! Symfony has a contribution guide which I suggest you to read. In short:
Review the GitHub status checks of your pull request and try to solve the reported issues. If some tests are failing, try to see if they are failing because of this change. When two Symfony core team members approve this change, it will be merged and you will become an official Symfony contributor! I am going to sit back now and wait for the reviews. Cheers! Carsonbot |
|
Hi, thanks for the PR, it's an impressive amount of work!
While it may not be explicit, I feel like
Can you please split this proposal in a separate PR so that we can consider it separately? Note that I still need to understand when this is an appropriate strategy, vs recomputing or locking. I'm also wondering how this works when the cache is cold? (but let's discuss that in the new PR) |
|
Thank you for your feedback @nicolas-grekas!
A few years ago I arrived at the conclusion that The main purpose of this family of adapters is to make tag-based invalidation reliable for LRU-like caches. OCC is just a possible positive side-effect.
I'll cherry-pick related to RetryProxyAdapter commits into a new branch. Should I also remove them from the current branch and leave the rest in current PR, or I need to cherry-pick the rest and open new PR for Ephemeral Adapters? Which option is the best? |
Currently,
Yes please. Let's keep only ephemeral-related stuff in this very PR. |
face50d to
5af1ff6
Compare
a697b14 to
c952262
Compare
c952262 to
a93b9ed
Compare
|
I am back :) Have made some fixes and improvements.
Of course, this solution attracted my attention. I can say that although TagAwareAdapter handles the absence of item tags gracefully (it requires both keys), different situations when data may become outdated are possible. For example, Redis may reject writes when it fails to reclaim enough memory (is out of memory), thus updating relatively big item value may be rejected while item tags are sucessfully updated (ironically, instances with 'noeviction' policy are most obviously affected by this scenario). Theoretically, two concurrent processes may overwrite one of the each other's keys. With regard to LRU scores and evictions, absolutely in most cases Redis will evict these keys separately just because of its probabilistic LRU algorithm https://redis.io/topics/lru-cache, and sometimes instead of evicting one item of bigger size Redis will have to evict more items (many smaller item tags). Memcached, in its turn, uses separate queues for items of different sizes so again these keys most likely will be evicted separately https://memcached.org/blog/modern-lru/. I'd say that because of their splitted nature, items have more than one reason to become corrupted. With sharded db, you may also be concerned with the fact that the ratio of survived items when one of shards goes down declines from (N-1)/N to ((N-1)/N)^2 since item's value and their tags are stored randomly on different shards. But my main concern is the versioning algorithm, it may be affected by evictions and OOM state. When tag's version (another key, not from the pair mentioned above) is evicted, it's being "reset" to 0. You may lose invalidation which occured before eviction if previous item's tag version was 0 and item had not been updated (recomputed and saved) by the time of tag eviction. Or, item's tag version may be non-0 but something near to, then it's possible to lose invalidation(s) which occur(s) after eviction. In such situations, item's value remains valid while should be deemed invalidated.Versions are incremented, and increment operation is not atomic. Setting aside theoretical debates about atomicity, let's focus on implementation details specific to Memcached and Redis. When memory limit is reached, Redis and Memcached evict other key(s) on SET even if specified key already exists. In Memcached, it very likely will be another tag since they all are in a one queue for smallest items. In Redis, as we already know, SET (and other memory consuming commands) may be rejected resulting in not updating a value and responding with -OOM command not allowed when used memory > 'maxmemory'. That is, tag invalidation may be lost.
In EphemeralTagAwareAdapter, tag invalidation is DELetion of a tag. Redis doesn't reject DEL command so you'll never lose invalidation because of OOM state. After eviction or invalidation (which have the same effect), tag version is set to a new random number from fairly wide range (presisely 2^64 even for 32-bit platforms) which will be used for tagging items till the next invalidation or eviction. In relation to OCC, there was one intresting bug/feature of TagAwareAdapter which was corrected by update #43302 (no 100% guarantee, though). The order of operations on items and tags is different for adapters with single pool and with two separate pools for items and tags because they use different deferred queues which are implicitly flushed at different points. In most cases this difference doesn't affect data validity much but with single pool item value is saved to cache before current tag version is even loaded from cache, hence item may be saved with outdated data and then new just updated tag version will be attached. Why did I say that this feature doesn't affect data validity much? Because data validity is already affected by the fact that tag versions are loaded after data was computed and passed to So achieving OCC with tags is possible only if it's allowed to pass a callback instead of a pre-computed value. Allowing this for == Appendix == Examples of Redis commands for computing and saving new tagged item with TagAwareAdapter, 1 pool (wrong order): TagAwareAdapter, 2 pools (right order): EphemeralTagAwareAdapter without OCC, 1 pool: EphemeralTagAwareAdapter with OCC, 1 pool: EphemeralTagAwareAdapter with OCC, 2 pools: |
a93b9ed to
b0b2c35
Compare
|
Thanks for the extensive details, that's super interesting! About split keys for value & tags, let's merge them. We don't guarantee that cached values will survive a minor upgrade so it's fine to break that. We just need to be sure that we gracefully discard old data. About versioning, good points also! We have #43301 on the topic but you go further. I like deleting for invalidating. I would really really prefer not adding a new adapter to the component. Would you agree with sending PRs that incrementally converge to implementing your proposals into |
|
@nicolas-grekas If all features of |
|
Yes, I'd be fine renaming your |
|
|
As long as the code remain backward compatible, it should be fine :) |
6c63270 to
0e8d14d
Compare
|
As a proof of concept I made
Which of these points are real BC breaks? Are there other barriers? |
There was a problem hiding this comment.
Change of invalidation algorithm makes it impossible to use different versions of TagAwareAdapter concurrently including period of rolling updates
That's fine, we don't guarantee that.
Implicit commit on tag invalidations is not in effect anymore. This behavior is very specific to TagAvareAdapter and I think users should be warned about this change.
Can't we preserve it?
Private method getTagVersions is replaced with inherited protected one, and there is other new protected methods.
I would prefer reducing the API surface, including protected methods. Let's mark the concrete classes final and the abstract one @internal at least.
0f7c13f to
c878e52
Compare
TagAwareAdapter by making tag versions an integral part of item value
|
I'm proposing sbelyshkin#1 on top of your work. I added notes there. Here's a quick summary:
Somehow reverted by my DTO proposal, which would allow - in another iteration - to use HSET for Redis, thus consuming even less storage.
Reverted, because I don't get what this provides. What did I miss?
Replaced by LRU-based pruning, which is simpler and should be as effective.
Reverted also, this won't make a difference in practice, better keep the code simple. Let me know if I missed anything! |
210b4cb to
9961272
Compare
|
Thanks a lot @nicolas-grekas ! I need some time to review all changes you've proposed.
How is this achieved?
In what way and where do you plan to use HSET?
This was a tiny optimization for computing expiration only once and not every time you retrieve a known tag from internal cache. Really tiny :)
I'll check that.
It was another optimization. The only reason for this is better performance when retrieving small items (a few KBs). The degree of increase depends on the ratio of CPU/IO time for whole operation and can be as high as 20% for TAA+FileSystemAdapter on local FS and as high as 10% for TAA+RedisAdapter with local instance of Redis. But for big items (100KBs and more) or for slow IO, the increase is not so impressive. |
9961272 to
8c991c8
Compare
by 1. fetching old-style tags while fetching items and 2. have metadata[tags] set to an array when retrieving newly persisted items (vs unset for older ones)
metadata is about expiry, ctime and tags. I think we could drop expiry and replace it by a call to
Thanks for the details, I didn't bench in such details. I still would like to not duplicate the logic so what I did instead is removing the generator. getItems now returns a simple array. The generator was not useful anyway since we buffer all items internally. This should reclaim some perf. |
Note that this is not true anymore: we don't persist the tags when retrieving items. Does it make sense? I'd like to have your thoughts about that. |
Thank you for bringing this to my attention. Very likely this solution will increase the number of overwrites of tags and hence item computations. I experimented around this earlier and now need to dive into new code and benchmark it again. I'll do it on this weekend. |
e25b80c to
b0e3c9e
Compare
b0e3c9e to
6a90ca0
Compare
|
ctime is now packed as a 14-bits floating point number. This leave 2 bits free: one is used to tell if tags are set or not, the other could be used for future needs. I'm going to merge this PR because I think it's ready. If any changes should be made, a follow up PR is very welcome @sbelyshkin |
|
Thank you @sbelyshkin. |
|
I'm a bit late but very happy to see the result :) I would only warn about declared backward compatibility which is for prevention of cold start after upgrade rather than for simultaneous use of new and old versions of adapter since old adapters reject new format (new wrapper class is unknown to them) and recompute items. So, running them simultaneously will put extra load on old instances. I hope we'll have the possibility in the future to discontinue an old two-keys format for less I/O and better performance. |
|
@sbelyshkin the solution is indeed backward compatible but not forward compatible (which is a lot harder to achieve) |
This PR was merged into the 6.1 branch. Discussion ---------- [Cache] Optimize caching of tags | Q | A | ------------- | --- | Branch? | 6.1 | Bug fix? | no | New feature? | no <!-- please update src/**/CHANGELOG.md files --> | Deprecations? | no <!-- please update UPGRADE-*.md and src/**/CHANGELOG.md files --> | Tickets | - <!-- prefix each issue number with "Fix #", no need to create an issue if none exist, explain below instead --> | License | MIT | Doc PR | - <!-- required for new features --> It's the follow-up to #42997. 1. Forcing the adapter to fetch tags on item commits makes the algorithm straightforward and a bit more optimized. 2. Caching tag versions only when they are retrieved from or being persisted to the pool ensures that any tagged item will be rejected when there is no related tags in the pool. 3. Using FIFO instead of LRU for known tag versions allows to use all cached tags until expiration and still be able to prevent memory leak. <!-- Replace this notice by a short README for your feature/bugfix. This will help reviewers and should be a good start for the documentation. Additionally (see https://symfony.com/releases): - Always add tests and ensure they pass. - Bug fixes must be submitted against the lowest maintained branch where they apply (lowest branches are regularly merged to upper ones so they get the fixes too.) - Features and deprecations must be submitted against the latest branch. - Changelog entry should follow https://symfony.com/doc/current/contributing/code/conventions.html#writing-a-changelog-entry - Never break backward compatibility (see https://symfony.com/bc). --> Commits ------- 68f309b [Cache] Optimize caching of tags
…kas) This PR was merged into the 6.4 branch. Discussion ---------- [Cache] Fix BC layer with pre-6.1 cache items | Q | A | ------------- | --- | Branch? | 6.4 | Bug fix? | yes | New feature? | no | Deprecations? | no | Issues | Fix #53825 | License | MIT Issue introduced in #42997 Commits ------- 9372d95 [Cache] Fix BC layer with pre-6.1 cache items
I'd like to introduce a new family of Tag Aware Adapters which can be used with various volatile storages such as Ephemeral Redis and Memcached. (Current implementations of TagAwareAdapters either do not support them explicitly or fail to guarantee tag-based invalidation of linked items)
Besides the main purpose and functionality, they have a feature which, I feel, needs to be explained and defended. Namely, an optimistic concurrency control, or something like that :)
With Ephemeral Tag Aware adapters, it's pretty easy to achieve OCC, at least we can track changes (tag invalidations) which happen during computation of value. Though outdated writes are not "rolled back" by adapters, the invalidated values will be rejected on subsequent reads. Without this feature, in such situations we usually end up with stale items waiting for the next update/invalidation, sometimes for quite a long period. Unit tests may shed further light on the power of OCC.
And one more thing in this PR is RetryProxyAdapter which is complementary to get()'s probabilistic stampede protection and a lock-free alternative to its LockRegistry. It's main advantage is that it is suitable for all PSR-6 adapters as well as for TagAware ones. As a special case, it can be useful in distributed setups when replicas are used for reads and a replication lag may be significant from time to time.
Your comments and suggestions will be greatly appreciated.