Cache made consistent: Meta’s cache invalidation solution
engineering.fb.com
engineering.fb.com
And regarding those tools:
it doesnt sound like Polaris would handle a network partition well. If a cache invalidation triggers it to check the other caches for consistency... that assumes Polaris will receive that invalidation message. Imagine a scenario of 5 cache servers, and a Polaris server. On one side of the split is Polaris and 2 servers, and the other has 3 cache servers... It's possible for the 3 cache servers to receive an update that is not received by the polaris+2 network... And polaris would not just be unaware of the inconsistency, but it also wouldn't know to check later for the inconsistency when the network partition is resolved.
I also feel like the consistency tracing is assuming that only one fill and invalidate is occurring at a time (when in practice, there may be multiple fills and invalidates occurring in parallel on the same data)... and that those calls will arrive in order. If they arrive out of order, it doesnt sound like it would catch that.. and I think you're relying on Polaris to catch this case, but high latency cannot be differentiated from a network partition except the length of the delay... so these two types of errors can be seen together.. in which case, you'd have a cache error that neither tool would detect.
I would like to hear why Im wrong.
I understand this is being used in prod, but network partitions don't occur everyday... and Im not convinced this has seen enough flaky networks to work out the bugs.
Yeah I have learned about some people have different perceptions of what cache invalidation means (I have a narrower definition, a subset of what some people think as cache invalidation). I will not die on this hill. I am happy to rename/rephrase/anything to be helpful.
> it doesnt sound like Polaris would handle a network partition well ...
Good question. And you are right. My thought on this is that over time, polaris would still catch those unique issues happened at network partition or whatnot. Polaris doesn't promise have 100% coverage all the time. However, over time, if there are flaws in the system, Polaris should help surface it. And once it did (even with just one inconsistent sample), it should be very actionable, and we can find out why it happened, and fix the underlying cause.
> I also feel like the consistency tracing is assuming that only one fill and invalidate is occurring at a time (when in practice, there may be multiple fills and invalidates occurring in parallel on the same data)... and that those calls will arrive in order. If they arrive out of order, it doesnt sound like it would catch that..
It doesn't make that assumption actually. Distributed systems are state machines. Consistency tracing essentially logs (it doesn't do much detection) state transitions. So when polaris detects an anomaly, we have all the information to help us diagnose. And you are right that fills and invalidations can happen in parallel and it's fine. E.g. if fill happens before invalidation, we can always track state mutations caused by the invalidation. If invalidation is the culprit (the earlier fill can't be because it happened earlier), we would have a log for it.
Sorry if it sounds like silly questions, I was genuinely curious to learn about the strategy since the blog started with "When it comes to cache invalidation, we believe we now have an effective solution to bridge the gap between theory and practice"
> what about many-to-many where one fetch returns inconsistent results Are you referring to the case when cache stores a complicated result of a function that fetches data from many sources, and how to figure out when to invalidate? If so, I am sorry but that's not the cache invalidation I was referring to. (https://news.ycombinator.com/item?id=31676102)
> What about data queried while there's a transaction rollback.. when is it updated in the cache
This might be easier to answer. I assume if you run the database with isolation level higher than read-committed, you will be fine.
Could this delay cause a wrong reporting? Since the source of truth (the DB) could already received multiple mutate events of the data Polaris trying to verify? How do you handle this case?
Assuming your definition of cache invalidation is about "when/who" to invalidate on writes. Let's actually try solving it.
E.g. in its most generic form, a cache can store arbitrary materialization from any data source. Now when updating the data source, in order to keep caches consistent, you essentially need to transact (cross system transaction) on both the data source and cache(s). Usually cache has more number of replicas, I am not sure running this type of transactions is practical at scale.
What happens if we don't transact on both systems (the data source, and cache)? Well, now whenever the asynchronous update pipeline performs the computation, it's done against a moving data source (not a snapshot of when the write was committed). Now let's say the data source is Spanner, which provides point-in-time snapshots. On Spanner commit you can get a commit time (TrueTime) back. Now using that commit time, to read the data and compute cache update asynchronously can be done.
Because the materialization in cache don't take writes themselves, so updates to them are essentially performed blindly and can be ordered by the commit time (TrueTime).
Now this does assume whatever we cache (the query e.g.) needs to be schematized, and made known to the invalidation pipeline. I think it's a very fair assumption to make. As otherwise (anyone can cache anything without the invalidation pipeline knowing at all), it's pretty obvious that this problem can't be solved.
- client starts a transaction
- client runs any mutations as needed
- client collects user_ids whose cache entries need to be invalidated
- client invalidates cache
- client commits the transaction
You can use a versioning scheme supported by the database to do compare-and-swap – i.e. sending invalidate along with a hybrid-logical-clock. HLC is nice in this case as it handles DB transaction rollback gracefully, if the database supports it.
Or we can always do the invalidation asynchronously (by recording the invalidation keys transactionally and have a tailer that sends out the invalidation).
I will make an edit to the blog to make it more clear. Let me know if that makes sense!
I mean this – cache invalidate/fill race specifically – is very much a solved problem from a protocol perspective, as long as our definition of the problem is the same – do not leave stale data in cache indefinitely. That is not to say it is easy; I am not trying to minimize anyone's struggles. https://research.facebook.com/publications/scaling-memcache-... might be of interest.
A lot of the challenges in cache are in making the tradeoffs between consistency and coordination overhead based on the workload and the requirement, _and actually_ making caches consistent in production. As explained in the post, there are practical challenges that are very unique to cache and cache invalidation.
Can't we assume they tested it before deploying to production by introducing all the weird stuff that might happen in a distributed system like partitions, high latency, so they aren't relying only on "it seems to work in production"?
Having better tests and better observability in production are also not mutually exclusive.
Contrasting that with Spanner where cache coherency is solved by reading from the recent past at consistent snapshots or by issuing global transactions that must complete without conflict within a brief truetime window. I am guessing the cost of Spanner underneath the social graph would be a bit too much for whatever benefits might be gained, but curious if anyone looked into using something similar.
Spanner is awesome and one of my favorite systems/papers. I think it would be very computational and power expensive to run the social graph workload on a spanner-like system. Do you have an estimate of how many megawatts (if not more) are needed to support one quadrillion queries a day on Spanner?
EDIT: I have no clue how efficient MySQL+TAO really are but figure that at least tens of thousands of machines go into it.
I was actually a little surprised how hard it is to get performance/W figures since I don't currently have any physical server hardware to go off of.
Since I observed data inconsistencies on Facebook multiple times, I believe they aren't as concerned about data integrity as a company doing financial transactions would be.
I'm a bit confused here. Polaris behaves as a regular cache server which receives invalidation events, but isn't the typical bug related to cache invalidation that a service forgets to contact the cache server for invalidation? So this will only catch cases where (1) you remember to contact Polaris, but you forgot to contact other cache servers [which Polaris happens to know about], OR (2) you're not handling errors during invalidation requests to the cache server [and the request to Polaris was successful]? Or are you cache servers "smart" and might have internal logic which "ignores" an invalidation?
What am I missing?
EDIT: Reading through "A real bug we found and fixed this year" and I'm still a bit confused. It seems like a very contrived bug directed directly to how you deal with versioning (e.g. you allow the latest version to be present with stale metadata, or something?). My main concern with cache invalidation is what to invalidate at what time.
There is a detailed write up here: https://elliotswart.github.io/pragmaticformalmodeling/cachin...
That's not the case based on our experience at FB. At-least-once delivery is a solved problem basically.
But you are absolutely right that if there's an issue in the invalidation delivery, it's possible that polaris won't receive the event as well. Polaris actually supports a separate event stream (all the way from client initiated writes) to cover this case.
I'm assuming the versioning is what ensures proper write, invalidation, and fetch ordering so that e.g. slow mysql writes/replication don't cause remote TAO clusters to receive an invalidation message and then read a stale value from a replica?
That's not the case.
> If someone were to directly write to MySQL shards there would be stale data
For the sake of this discussion, you can assume this is the setup, and everything should still stand.
> I'm assuming the versioning is what ensures proper write, invalidation, and fetch ordering so that e.g. slow mysql writes/replication don't cause remote TAO clusters to receive an invalidation message and then read a stale value from a replica?
You should join us :p This is getting into the details of our cache invalidation protocol and our cache consistency model. Maybe another post on another day!
yeah that specific bug is convoluted.
> It seems like a very contrived bug directed directly to how you deal with versioning (e.g. you allow the latest version to be present with stale metadata, or something?).
This is mostly for performance reason that I won't go into details too much here. Version is mostly an internal concept that clients don't care about. So it's OK-ish.
> My main concern with cache invalidation is what to invalidate at what time.
Can you elaborate? Our experience on cache invalidation is that you invalidate on mutation, and in terms of "what to invalidate" it depends on the computation, which you might have to give me a little more details.
> you have tools to analyze the correctness of your solution
That's half of it. Cache invalidation is hard not only because of the complexity of cache coherence protocols, some of which is not very complicated. But cache invalidation does introduce countless races that manage to introduce cache inconsistencies in ways that are just hard to imagine ahead of time (in my experience). IMO, that's the harder part of cache invalidation – when cache inconsistencies happen, answering the "why" question is much harder than having a cache invalidation protocol (you can have TLA+ for one if you will). And answering the "why my cache is inconsistent" is the problem we solved, which I think is the harder part of the cache invalidation problem.
That should be the title and focus of your post. Instead, it feels like grandiose claims about solving cache invalidation itself.
That is definitely something I worried about. But at the same time, I do think we solved the harder part of the cache invalidation problem. TAO and Memcache serves quadrillions queries a day. Based on our experience, answering the question of "why my cache is inconsistent" is the hardest thing about cache invalidation.
Cache invalidation protocols can be complicated, but some are pretty managable. You can also verify it using TLA+ if you will. But once the rubber hits the road, some cache entries tend to be inconsistent.
I definitely worry about people taking this the wrong way, but at the same time, I stand by the claim of "cache invalidation might no longer be a hard thing in computer science".
> How is that solving a computer science problem?
It depends on your definition of a computer science problem. I am definitely not solving P = NP. By your definition, does Google's Paxos Made Live paper solve a computer science problem?
The claim is more a play on Phil Karlton's quote, as the work here makes cache invalidation much easier (in my opinion). Also Phil Karlton's quote doesn't necessarily _make_ a problem a computer science problem, don't you think? I think it's a good quote and there's a lot of truth in it.
> the work here makes cache invalidation much easier
The tool itself doesn't make cache invalidation easier, it makes finding bugs (that happen to be cache invalidation bugs), easier. By that logic, if one never wrote a bug, cache invalidation would still be as difficult as before.
Again, good work on the tool. That's fantastic. I've definitely done some huge work in this area myself and struggled a lot. Let's also realize that it is also FB internal, so whatever solutions you've come up with aren't really helping anyone else without spending the same amount of engineering time and resources on the problem.
I understand if you disagree with these premises. And all these make sense.
Let's discuss the "cache invalidation problem" by your definition.
E.g. in its most generic form, a cache can store arbitrary materialization from any data source. Now when updating the data source, in order to keep caches consistent, you essentially need to transact (cross system transaction) on both the data source and cache(s). Usually cache has more number of replicas, I am not sure running this type of transactions is practical at scale.
What happens if we don't transact on both systems (the data source, and cache)? Well, now whenever the asynchronous update pipeline performs the computation, it's done against a moving data source (not a snapshot of when the write was committed). Now let's say the data source is Spanner, which provides point-in-time snapshots. On Spanner commit you can get a commit time (TrueTime) back. Now using that commit time, to read the data and compute cache update asynchronously can be done.
Now this does assume whatever we cache (the query e.g.) needs to be schematized, and made known to the invalidation pipeline (in the form of some control plane metadata). I think it's a very fair assumption to make. As otherwise (anyone can cache anything without the invalidation pipeline knowing at all), it's pretty obvious that this problem can't be solved.
My context is working on Notion’s caches for page data. Our pages are made out of small units called “blocks” that store pointers to their child content. To serve all the blocks needed to render a page, we need to do a recursive traversal of the block tree. We have an inconsistent cache of “page chunks” right now, how would you think about making a consistent cache?
There are two parts to solve this problem 1. monitor and measure how consistent the cache is 2. figure out why they are inconsistent
I will focus on #1 in this comment. You can build something very similar to Polaris (mentioned in the blog) that - tails your database's binlog so it knows when e.g. "friendship" data is mutated - it can then perform the computation to figure out which cache entries "should have been" updated. E.g. if Alice just friended Bob, then Alice's friends-of-friends and Bob's friends-of-friends should reflect the change. And your monitoring service will "observe" that and alert on anomalies
I am trying to help.
On the other hand, I don’t think figuring out “when” to invalidate is what makes cache invalidation hard. I shared the same view as Marc https://twitter.com/marcjbrooker/status/1534944340266864640?....
There is a trade off between coordination (in some cases with unbounded write amplification https://twitter.com/uvdn7/status/1534979480363667457?s=21&t=...) and relaxed consistency. I assumed this is a trade off that people just have to make based on their workload (hence you saw me saying in other comments about TTL; it’s about tradeoffs, when the cost of coordination/invalidate surpasses the benefit — higher hit rate, etc.)
I acknowledge that both are hard. The former can't be avoided. And the latter is easy in certain cases (if you have a simpler data model, etc.). I am not saying the latter is easy. More details in https://news.ycombinator.com/item?id=31676102
And I made the mistake of assuming the definition of “cache invalidation” as it means different things to different people. Marc’s view is a very good one https://twitter.com/marcjbrooker/status/1534944340266864640?... but it’s actually different than some people’s definition on this thread.
I will not defend myself; and you are welcome to speculate. I said it here https://twitter.com/uvdn7/status/1534978702609682432, and other places on this thread, and I will repeat it again.
I should have applied a narrower and more specific definition of cache invalidation in the blog post. The confusion it caused is not intended.
> how to implement invalidating it when you know exactly what needs invalidation
I stand by the claim that this is a hard problem, as explained in the blog post. When you deal with a cache you are inherently dealing with a distributed system (there's cache and the source of truth). And the contribution is making this aspect more manageable, which is common to all invalidation based caches.
The idea is that with all these observability capabilities, debugging cache inconsistencies is getting very actionable and close to how we debug an error with message telling us exactly where an exception happened.
Does the invalidation need to be predictable before you can use tracing? What kind of parameters do you have so you don't have too much logging or too little?
It starts all the way from client initiated write (where we mint a unique id, and plumb it all the way through).
> What kind of parameters do you have so you don't have too much logging or too little?
This is the key question! If you go to the second half of the post, it talks about an insight about how we managed to log only when and where cache inconsistencies _can_ be introduced. There's only a small window after mutation/write where cache can become inconsistent due to invalidation. So it's very cheap to trace and provide the information we need.
EDIT: Already answered in this reply: https://news.ycombinator.com/item?id=31671794
Distributed systems are state machines, with consistency tracing keeping track of all the state transitions, debugging cache inconsistencies in an invalidation-based cache is very actionable and managable based on our experience.
Curious because I’ve been learning TLA+ recently and interested to more know about cases where an algorithm has been proven but actual an implementation of it fails.
My favorite example is Paxos. Its algorithm fits on a single slide. But it’s notoriously hard to make it actually work correctly in production.
I am sorry for the confusion. We have internal abstractions that deals with the problem you described (especially in simpler forms, the example you have is fairly managable actually).
EDIT: I can see why it gets complicated if your data model and query is very complicated.
As long as the client submits transactions with “I calculated this based off of X@v4” then the database can reject if there is a newer version of X.
The client can then replay the transactions against the cache and by then there will be a X@v5.
With this scheme you can track the transaction replay rate instead of having to build a new system to read-back the cache for consistency.
To get the traceability on which cache node is stale, the client can forward a header from the cache node that identifies it. Then using the same transaction rejection rate ops has visibility on which cache node isn’t being updated.
No cache invalidation needed. Always just cache forever X@version, it’s just that the cache allows an unstable query for GET X.
Here's a bunch of versions of variable "X":
X@Alice-V1, X@Alice-V2, X@Bob-V1, X@Alice-V2/Bob-V2, X@Carol-V1
Which version of "X" should you read?
EDIT: Alice, Bob, and Carol are three different servers. What has happened here is that Alice and Bob are closer together, so their updates are faster between each other (synchronizing the writes). Carol is slower for some reason (bad connection?), and is going to update off of old data.
In this case, the two valid caches are X@Alice-V2/Bob-V2, and X@Carol-V1. The other cached data is old and can be discarded.
Things get complicated when you have not only reads (such as in your simplified question), but also writes that are cached (such as what happens in practice).
Plus what about read workloads, like “pull message from queue and send it as a push notification to user Y”? I guess it’s fine if the push is re-delivered due to stale cache?
What I thought the article would tackle is the dependencies between stored objects. Some solve it with super complicated graphs others by just flushing the entire cache.
At Meta, why not just use flat files or a store that act as one, pubsub the changes, listen on the changes and update aggregated views as needed and store them. Then just short-term cache everything on the edge.
Like tracking dependencies, so it knows what to invalidate on mutations?
Those are the kind of rates that lead to very hard to find bugs. You won't properly write code in downstream systems to properly handle that failure case, and suddenly someone will get paged at 3am because it has just happened years after the code was deployed and nobody really understands how this corner case suddenly happened!
When I'm building systems, every happy codepath should either happen frequently or never.
Having a cache whose design allows it to be stale but only very rarely seems like a bad idea. If I was building something on top of this cache I would have a layer on top to force staleness for 1 in 1000 requests just to force the application built on top to be designed to handle that properly.
> Having a cache whose design allows it to be stale but only very rarely seems like a bad idea.
And that's exactly why we first brought this number from 6 9's to more than 10 9's; and we are not done yet. Also the cache is not "designed" to be inconsistent. It's like Paxos is designed to solve the consensus problem, but when implemented, most Paxos implementations do not work properly.
> Data in cache is not durable, which means that sometimes version information that is important for conflict resolution can get evicted.
> We also added a special flag to the query that Polaris sends to the cache server. So, in the reply, Polaris would know whether the target cache server has seen and processed the cache invalidation event.
To make special flag work, cache server need to track not only current version state, but also past versions. If it tracks past versions, then conflicts can be resolved at the cache server level, but whole premise of article is that cache servers can't resolve conflicts by themselves.
I will try to answer this one without too much implementation details.
First of all, cache items can be evicted and are not durable, which is just a fact. But that doesn't mean we can't track progress (in terms of "time" or "logical time"/"order" in distributed system terms). The social graph is sharded (not surprisingly). We can keep progress of each cache host per shard, which is just a map kept in memory, which doesn't get evicted.
I hope this answers your question.
Simple. Effective. But it obviously doesn't work for everything.
I'm a little confused:
- Is the database updated notification going out while the transaction is still in-progress? Doesn't it make more sense to delay the notification until after the transaction commits?
- If a cache tries to update itself while there's an open transaction against the data it's trying to read, shouldn't the database block the operation until the write is complete? And then shouldn't another notification after the transaction commits trigger the cache to update?
No, that's not what happened.
> If a cache tries to update itself while there's an open transaction against the data it's trying to read, shouldn't the database block the operation until the write is complete?
Yes. Generally speaking, having a read transaction here would be better. There are unrelated reasons why it's done this way. The point of the example is that it's really intricate and we can still identify the bug regardless.
I'm not too familiar with your database, but I wonder if you could have a "read transaction" with such a short timeout that you could return a "try again soon" error to the cache? (The only time I dealt with dirty reads like this was Microsoft SQL, I suspect you're using something with very different transaction semantics or guarantees.)
>>Polaris pretends to be a cache server
De facto, it is a cache server, with the associated performance decrease. Isn't the main purpose of caching to improve performance?
>>We deploy Polaris as a separate service so that it will scale independently from the production service and its workload.
Assuming the scaling is horizontal, so then, to synchronize among the service instances, what do you do? Create another meta-Polaris service? Not rhetoric or sarcasm - hoping for an open discussion.
Polaris only receives cache invalidation event, and doesn't serve any client queries.
> so then, to synchronize among the service instances
It doesn't synchronize among the service instances. It's actually basically stateless. It pretends to be a cache server only for receiving invalidation events, and acts as a client, and assumes no knowledge of the cache internals.
That’s 11,574,074,074 requests per second.
1 request from human would likely create multiple queries internally.
I imagine huge distributed systems as Markov chains, where transitions are probabilistic rather than deterministic.
What if you measure for 1 hour instead of 5 minutes? Still 10 nines?
The number of nines actually go up with increasing timescale windows because Polaris checks anomalies at write-time/invalidation-time.
I guess the behavior of what you are describing is cache inconsistencies at read-time. E.g. if I introduced an inconsistent cache entry at time T, it can be exposed to many subsequent reads (hence the "building up over time" as you mentioned). This is an important metric as well – we actually measure it as well.
The key difference between read-time cache consistency measurement and write-time cache consistency measurement is about "purpose". Write-time cache consistency measurement is more actionable, as it captures the moment (or very close) of when cache becomes inconsistent. If one wants to debug something, you want to get close to when the anomaly happens. Read-time cache consistency measurement is more about measuring the negative impact of cache inconsistencies (which are client facing).
...and off-by-one errors.
(I'm starting to think that 'naming things' and 'cache invalidation' are the same thing, since you need to invalidate the cache anytime the description of the thing changes)
> Cache invalidation is a process in a computer system whereby entries in a cache are replaced or removed.
It's the smallest unit of function that "cache invalidation" must perform. Some people define cache invalidation as a problem of figuring out "when/who" to invalidate. That's not the definition I am using (and my definition is narrower in that sense). The confusion is not intended, as I believe (as I explained in the post) that even with the narrower definition, cache invalidation is still insanely hard.
If it helps, let's essentially break cache invalidation into a few parts 1. knowing when/who to invalidate 2. actually processing the invalidate
My argument is that #1 can be very managable with simpler data models (as we did). #2 can't be avoided; and #2 is very hard. And the post is about how we believe we have a systemic approach for managing #2.
For #1, say, you are caching a result of joining two tables with two ids that you are filtering on. It's still very managable to track the dependency and know when to invalidate. It can easily grow out of hand (join 10 tables with 100 lines of SQL). Then solving the "when/who" to invalidate problem is essentially equivalent to doing "joins" on the write/invalidation path. First of all, it's unbounded. The number of cache entries you need to invalidate can be unbounded (not bounded by the number of indices, but a function of data in the database instead). My argument is that why do this to begin with? I acknowledge this is hard. But why do it? On the other hand, you can have simpler data models (e.g. TAO), fetching and stitching everything together on the read path scales fairly well. It's essentially doing "joins" on the read path. But it's all hitting caches, so it's fast still.
For some complicated queries, you can cache secondary indices (which is easier to figure out the "when/who" question, just as how DB figures out which index entry to update on transactions) to make your read-path join faster. The write amplification / cache invalidation fanout is bounded. You don't do "join" on writes/invalidations.
Let's discuss the "when/who" problem specifically, if say we just have to solve it.
E.g. in its most generic form, a cache can store arbitrary materialization from any data source. Now when updating the data source, in order to keep caches consistent, you essentially need to transact (cross system transaction) on both the data source and cache(s). Usually cache has more number of replicas, I am not sure running this type of transactions is practical at scale.
What happens if we don't transact on both systems (the data source, and cache)? Well, now whenever the asynchronous update pipeline performs the computation, it's done against a moving data source (not a snapshot of when the write was committed). Now let's say the data source is Spanner, which provides point-in-time snapshots. On Spanner commit you can get a commit time (TrueTime) back. Now using that commit time, to read the data and compute cache update asynchronously can be done.
On the other hand, it's very easy to feel like #2 is an easy problem, which probably explains why people think #1 is what Phil Karlton was referring to. The analogy I like to use is Paxos. The protocol fits on a single slide. It's easier to feel like you have Paxos work; but it's very hard to have Paxos actually work.
Here's the recording of my talk at systems @scale which I hope people find it helpful (no matter how you define cache invalidation – the broader vs. narrower definition) – https://www.facebook.com/watch/live/?ref=watch_permalink&v=3....
We seem to have different concepts with regards to the cache invalidation problem.
The one I know has to do with "Is there a change in the source data? How should I check this? How often?" and such things.
Yours seems to be "In my distributed system, I cannot guarantee the order of the messages that get exchanged, and thus, different nodes may end up having different information at times".
IMO you have a consensus/distributed data problem, not a cache invalidation problem (the inconsistency between your cache nodes is a consequence of the underlying design of your system).
OP's response to this, in another comment, is: "Now going back to your example with complicated dependencies. Maybe TTL is a better solution. With many dependencies, any changes from the dependency list might trigger invalidation. At some point, just doing TTL, would be simpler."
But what if you actually do want your dependency list to trigger invalidation?
https://materialize.com/ is the closest thing I know of to a "solution" for this - it lets you build nested, realtime materialized views on top of streaming and non-streaming data, all with SQL syntax and Postgres wire compatibility, that fully recalculate and recache their results whenever any input changes, no matter how deep (based on https://timelydataflow.github.io/timely-dataflow/ from Microsoft Research).
You could either use the outputs of such a system as a cache, or weave together a cache invalidation signaling system that sends a stream of keys that need to be evicted from cache at any time, directly into a Kafka topic. And then, of course, this could plug into Meta's cache invalidation consensus system. But it's remarkably disingenuous for Meta to pretend that the dependency side of this problem is trivial or can be solved by TTLs alone.
>But what if you actually do want your dependency list to trigger invalidation?
I (we, as it was a team) once had a scenario where there was a big dependency graph with a lot of replicas (not necessarily caches but a similar thing) and if we just used TTLs the effect on the whole thing was that there were some periods of time where we've just got a flood of nodes (children, grandchildren, and so on) all wanting to update at the same time, talking to each other and whatnot.
In the end the solution was quite complex as it was a combination of a short TTL, some random delays here and there to lower the probability of things happening at the exact same time, very low message overhead and a system akin to ETags in HTTP [1]. It was very hard due to the scale of the whole system and I'm sure Meta has this problem 100x so, disregarding the poor choice of title, it was an interesting read nonetheless.
1: https://developer.mozilla.org/en-US/docs/Web/HTTP/Headers/ET...
Let's do it.
E.g. in its most generic form, a cache can store arbitrary materialization from any data source. Now when updating the data source, in order to keep caches consistent, you essentially need to transact (cross system transaction) on both the data source and cache(s). So in theory this can be done. Usually cache has more number of replicas, I am not sure running this type of transactions is practical at scale.
What happens if we don't transact on both systems (the data source, and cache); but rather invalidate caches asynchronously? Well, now whenever the asynchronous update pipeline performs the computation, it's done against a moving data source (not a snapshot of when the write was committed). It can't be done.
Now let's say the data source is Spanner, which provides point-in-time snapshots. On Spanner commit you can get a commit time (TrueTime) back. Now using that commit time, to read the data and compute cache update asynchronously can be done.
Now this does assume whatever we cache (the query e.g.) needs to be schematized, and made known to the invalidation pipeline (in the form of some control plane metadata). I think it's a very fair assumption to make. As otherwise (anyone can cache anything without the invalidation pipeline knowing at all), it's pretty obvious that this problem can't be solved.
> Cache invalidation is a process in a computer system whereby entries in a cache are replaced or removed.
It's the smallest unit of function that "cache invalidation" must perform. Some people define cache invalidation as a problem of figuring out "when/who" to invalidate. That's not the definition I am using (and my definition is narrower in that sense). The confusion is not intended, as I believe (as I explained in the post) that even with the narrower definition, cache invalidation is still insanely hard.
It's not disingenuous. You are welcome to speculate.
If it helps, let's essentially break cache invalidation into a few parts 1. knowing when/who to invalidate 2. actually processing the invalidate
My argument is that #1 can be very managable with simpler data models (as we did). #2 can't be avoided; and #2 is very hard. And the post is about how we believe we have a systemic approach for managing #2.
It's very easy to feel like #2 is an easy problem, which probably explains why people think #1 is what Phil Karlton was referring to. The analogy I like to use is Paxos. The protocol fits on a single slide. It's easier to feel like you have Paxos work; but it's very hard to have Paxos actually work.
> Now going back to your example with complicated dependencies. Maybe TTL is a better solution. With many dependencies, any changes from the dependency list might trigger invalidation. At some point, just doing TTL, would be simpler.
#1 is a hard problem, if the data model and data in cache is complex I agree. My comment here is referring to update-heavy workloads. If you have a large dependency, your invalidation workload will tend to be heavy. At some point, you will spend more power on processing invalidation than serving user queries. The post is talking about a narrower problem; and I am not trying to minimize anyone's struggle.
I will take a closer read. It seems similar to what I described here https://news.ycombinator.com/item?id=31676849.
I can imagine an automated solution to achieve what you described eg by keeping track of the table:columns touched by the query. Maybe that’s what these system did.
It has its downside though, as the invalidation cost in this case can be unbounded (read as huge write amplification in some cases). I imagine it would be hard to provision the invalidation pipeline. This is where it gets into trade offs. Eg by just caching the primary index and secondary indices (not materializations) you can very far as well (do joins on read). But it depends on the workload.
> Imagine that after shuffling Alice’s primary message store from region 2 to region 1, two people, Bob and Mary, both sent messages to Alice. When Bob sent a message to Alice, the system queried the TAO replica in a region close to where Bob lives and sent the message to region 1. When Mary sent a message to Alice, it queried the TAO replica in a region close to where Mary lives, hit the inconsistent TAO replica, and sent the message to region 2. Mary and Bob sent their messages to different regions, and neither region/store had a complete copy of Alice’s messages.
A solution to this problem is to update Alice's primary message store to be "region 2;region 1" for a period of time, and get Alice to retrieve messages from both message stores during that period.
However, since you have a caching layer that doesn't have an explicit TTL, such that any cache inconsistency can last indefinitely, you now have a much bigger distributed data problem.
> 2. In the first round, the cache first filled the old metadata.
> 3. Next, a write transaction updated both the metadata table and the version table atomically.
> 4. In the second round, the cache filled the new version data.
Another way to look at this is that while the database can handle writes to the 2 tables atomically, the caching layer can't do a consistent read from the 2 tables, because it is either too expensive to do the 2 reads from within a database transaction, or too expensive to do a single read with join?
Our current system also suffers heavily from distributed inconsistency, mostly due to these "too expensive" constraints imposed by an ex-FB guy, even though our scale is nowhere near FB level. Yes I am bitter.
> Our current system also suffers heavily from distributed inconsistency
Despite of people having different definitions of cache invalidation (mine is narrower, and a subset), I hope the techniques covered here can be helpful (even a tiny bit).
If you assume loosely-coupled, eventually-consistent data, you haven't solved the problem at all -- you've just side-stepped it. If you assume a single-writer, multiple-reader architecture, you don't have the original problem at all.
Do you have any reference or links about it? Thanks.
> point of view of a writer in a multiple-writer distributed system > If you assume a single-writer, multiple-reader architecture, you don't have the original problem at all.
It starts to sounds like you are describing Paxos?
- https://en.wikipedia.org/wiki/Cache_coherency_protocols_(exa...
- https://www.cs.utexas.edu/~pingali/CS377P/2018sp/lectures/me...
I know the same problem exists in distributed shared-memory systems like supercomputers, but I'm not sure where the original term comes from.
(edit: you can take some comfort that you're not the first to define cache invalidation in this way, but then you're not the first to claim this victory either: https://briandunnington.github.io/distributed_cache_invalida... ;)
Yeah I assumed it would originate cache coherency protocol as well. In that case, it's not hard to figure out "when" to invalidate, as you just invalidate the cacheline on mutates based on addresses. If cache invalidation originates from cache coherency protocols, I would assume Phil Karlton's quote was not referring to the "when" to invalidate as being the hard problem. But I will not die on this hill. I am open to rephrase/redefine/reword in anyway that is helpful to people.
You misnamed the problem you are trying to solve.
Say, you are just caching simple k/v data (no joins, nothing). Are you claiming cache invalidation is simple in that case?
Also the reason why I didn't mention the cache invalidation dependencies is that _I believe_ it's a solved problem (see the link above, we do operate memcache at scale). I am happy to discuss if and why it wouldn't work for your case.
No.
>I believe it's a solved problem
It's not.
Suppose you have source-of-truth A (doesn't really matter if it's a key-value store or whatever, it could even be a function for all intents) and a few clients B1, B2, B3, ... that rely on the data from A. You have to keep them in sync. When should B* check if A has changed? Every time they need it? Every minute? Every hour? Every day? This is the cache invalidation problem; which IMO is not even a problem but a tradeoff, but whatever.
Epilogue: With all due respect, you have an unbelievable career, IBM, Autodesk, Google, Box and now Meta. None of those companies would give me five minutes of their time because I am self-taught, yet here we are :)
Although I didn't mean it as an attack it def. didn't add to the discussion, so I'll be more careful onwards.
Epilogue: With all due respect, you have an unbelievable career, IBM, Autodesk, Google, Box and now Meta. None of those companies would give me five minutes of their time because I am self-taught, yet here we are :)
Here’s some unsolicited feedback - I interpreted your comment above as implying you know more than $peer, and it comes off a little snarky with the emoji face. That approach doesn’t demonstrate professionalism to me. On the other end, $peer focuses on the technical challenge. Most of the gig boils down to communicating ideas.
A few things to clarify here what you are referring to as clients are cache hosts (as they keep data). You seem to imply that the cache is running on the client? I was referring to cache servers (think memcache, Redis, etc.), for which the membership can be determined. So on update (e.g. when you mutate A, you know all the Bs to invalidate).
Now continuing with your example, with cache running on the client. Assuming we are talking about same concept when we say "client", the membership is non deterministic. Clients can come and go (connect and disconnect as they wish). There are some attempts to do invalidation-based cache on clients, but they are hard because of the reason I just mentioned. So usually client cache is TTL'ed. E.g. the very browser you are using to see this comment has a lot of things cached. DNS is not going to send an invalidate event to your browser. It't TTL based.
I guess what I am saying is that cache invalidation rarely applies to cache side cache as far as I know. Maybe you have a different example, which we can discuss.
> So on update (e.g. when you mutate A, you know all the Bs to invalidate).
But "knowing" this is a big part of what people mean when they say cache invalidation is hard! If the value in B is dependent on a complicated function of A's state, then it may be difficult to automatically determine, for any given mutation to A, which parts of B's cache need to be invalidated.
> There are some attempts to do invalidation-based cache on clients, but they are hard because of the reason I just mentioned. So usually client cache is TTL'ed.
Given this statement, the original title of this submission is even more baffling. If you recognize that data can be cached in clients, and that invalidating those caches is so hard that most systems -- including yours -- just completely abandon the goal of being able to do it correctly/reliably, then how can you claim your system makes it no longer a hard problem?
> But "knowing" this is a big part of what people mean when they say cache invalidation is hard!
I can see that. Memcache is a look-aside cache we have at scale. There are abstractions on top to manage this complexity; and it has been fairly managable. I am sure you can come up with a complicated dependency tree that things are not obvious at all. But when you do have a very large dependency tree, any change in them can trigger cache invalidation, at which point, caching with TTL will be a better option IMO. I can see where you are coming from.
> If you recognize that data can be cached in clients, and that invalidating those caches is so hard that most systems
My reasoning for this being hard is different than yours I think. In my comment, it's due to indeterminism of the cluster membership. I think in that case, we are talking about different problems.
I see where you are coming from; and I don't disagree. I just want to clarify a few things I talked about.
It's not that actually doing the invalidation in the most complicated scenarios can't be done, but rather not worth it (a tradeoff). I tried to explain it here https://news.ycombinator.com/item?id=31676102. But I think Marc did a much job at putting it concisely https://twitter.com/MarcJBrooker/status/1534944338341310470.
I know the tradeoff and I didn't consider the tradeoff specifically is what made cache invalidation hard (it's a distributed system challenge in general I thought). In in that context, I brought up TTL, as I think it makes a better tradeoff in the scenario. Again, cache invalidation can be done (in some cases with unbounded write/invalidation amplifications). It's just that IMO it's not worth it in that case.
What matters is B* reads from A, but how often should that be? That's it, literally. That's the whole problem.
> the inconsistency between your cache nodes is a consequence of the underlying design of your system
I disagree with this. First of all, imposing order and synchrony is expensive, slow and unreliable. Even if we do that, cache fill and invalidation will never be externally coordinated; and will collide on the cache host.
> I disagree with this. First of all, imposing order and synchrony is expensive, slow and unreliable. Even if we do that, cache fill and invalidation will never be externally coordinated; and will collide on the cache host.
This is a weird reply. GP writes "A implied B" and you disagree by arguing that you had to do A. Sure. But it's still what implied B. Quite a fundamental logic flaw, no?
B == "Inconsistency between your caches"
GP: A -> B
You: "Imposing order and synchrony is [bad things]" == "If you don't do A then [bad things]", i.e., (not A) -> [bad things]
Also you: "Even if we did, then [other issues]" == "Even if you don't do A then [other issues]", i.e., (not A) -> ..what? B?
You are certainly not arguing against the A -> B implication.
I was essentially saying !A !-> !B - even if we have a strongly ordered system, there will still be inconsistencies/races/problems.
And I can see why it's a bad/weird argument. Thank you for pointing it out. Really appreciate it!
EDIT: I would have rephrased it this way
- A -> B is right - But !A -> B also holds. Hence what we talked about here is relevant/useful regardless. And it's not about A.
Would that be better?
Short-sighted because it narrows the original problem (cache invalidation) to a specific version (detecting cache invalidation errors past an arbitrary time-frame).
Grandiloquent because it then claims to have "solved" the general problem, whereas they haven't even solved the narrowed version. Notice their own premise:
> For any anomaly in a stateful service, it is an anomaly only if clients can observe it one way or the other. Otherwise, we argue that it doesn’t matter at all.
This is a practical attitude that can yield great results, and probably even good engineering practice. However, it will never lead to solving a problem, because a problem isn't solved until you prove that it is.
Thanks for the comment! I stand by this claim; I would love to hear more about why an anomaly (any anomaly) matters if it can't possibly be observed by any client for stateful service.
This is quite different than what the described system does though. The system flags errors that have been observed. The correct claim to go with what the article does would thus be:
> For any anomaly in a stateful service, it is an anomaly only if the current clients running their current operations happen to observe it. Otherwise, we argue that it doesn't matter at all.
It's much more noticeable this way, isn't it?
The exact same argument applies to normal exceptions and errors. It might be the case that out of quadrillions of queries a day, just none of them hit the error path, and hence we won't observe any issues.
I can see that in this case, if it matters or not becomes somewhat subjective. It's a good point though!
I am serious when I say cache invalidation might no longer be a hard thing in computer science. In the post, I explained why cache invalidation is hard; and how we solve/manage its unique challenge and complexity. By my definition, we are solving the cache invalidation problem.
The analogy I have is Paxos. It's notoriously hard to implement Paxos correctly. Google published a paper on Paxos Made Live just on how they managed the implementation and productionization complexity.
Can you elaborate?
The hard part of cache invalidation is to detect when an update somewhere in your system is going to affect the result of that query, such that you need to trigger an invalidation.
We have memcache which is a look-aside cache that serves this type of workload. What you described can be solved by adding one level of abstraction and letting reads and writes all go through it.
Now on your read path, you can construct arbitrary complex sql queries or whatnot, but it must take some kind of input to filter on. Those become part of the "keys".
The invariant is that as long as the "context/filter" you encode covers all the mutations which would impact your cache data, you should be good. Based on our experience, it has been fairly managable.
Well, isn’t this the truly hard part of cache invalidation?
E.g. in its most generic form, a cache can store arbitrary materialization from any data source. Now when updating the data source, in order to keep caches consistent, you essentially need to transact (cross system transaction) on both the data source and cache(s). Usually cache has more number of replicas, I am not sure running this type of transactions is practical at scale.
What happens if we don't transact on both systems (the data source, and cache)? Well, now whenever the asynchronous update pipeline performs the computation, it's done against a moving data source (not a snapshot of when the write was committed). Now let's say the data source is Spanner, which provides point-in-time snapshots. On Spanner commit you can get a commit time (TrueTime) back. Now using that commit time, to read the data and compute cache update asynchronously can be done.
Because the materialization in cache don't take writes themselves, so updates to them are essentially performed blindly and can be ordered by the commit time (TrueTime).
Now this does assume whatever we cache (the query e.g.) needs to be schematized, and made known to the invalidation pipeline (in the form of some control plane metadata). I think it's a very fair assumption to make. As otherwise (anyone can cache anything without the invalidation pipeline knowing at all), it's pretty obvious that this problem can't be solved.
Some cache entries depend on the state of rows in Table C, but for some combinations of Table A and Table B, no data from Table C ends up in the cache entry.
All of this is business logic, and now it's touching one of our supposedly low-level libraries, which is separated by at least one level of indirection from the rest of the business logic - if your architecture is good. But caching tends to rot architecture.
This is a good example. Let's talk about it. Say we have a table for "friends", and a separate materialization, in cache!, for "friends-of-friends-who-lives-in-us". First of all, the query for the cache data needs to be schematized and made known to the data source. Otherwise, a client can cache arbitrary materialization of anything, it would be obvious that, in its most generic form, the problem can't be solved.
Now assume the data in cache is schematized. There's a transaction that changes "friends" table. Now we have two options, one is that within the same transaction (x-system 2phase commit for example), updates cache (the one that stores "friends-of-friends-who-live-in-us"). This is the synchronous flavor of it, which has obvious scaling challenges.
Spanner, etc. are about handling the async flavor of the same logic.
> if your architecture is good. But caching tends to rot architecture.
My speculation is that sometimes people are using cache without knowing they are dealing with a distributed system. A cache in its nature is a distributed system (because there's cache and the source of truth).
The linked blog post is targeted towards cache service owners, not cache users (who puts materializations in cache). If I learned anything from this public civil discourse on Hacker News is that
we should avoid putting the power/responsibility of cache invalidation in the hands of cache users
we should provide guard rails via better abstractions, simpler data models (e.g. a graph data model)
we should avoid caching relations (separate materializations) but prefer caching indices instead, so the write/invalidation amplification is bounded.Say, you are caching a result of joining two tables with two ids that you are filtering on. It's still very managable to track the dependency and know when to invalidate. It can easily grow out of hand (talking about 10 table joins and 100 lines of SQL). Then solving the "when/who" to invalidate problem is essentially equivalent to doing "joins" on the write/invalidation path. First of all, it's unbounded. The number of cache entries you need to invalidate can be unbounded (not bounded by the number of indices, but a function of data in the database instead). My argument is that why do this to begin with? I acknowledge this is hard.
But why do it? On the other hand, you can have simpler data models (e.g. TAO), fetching and stitching everything together on the read path scales fairly well. It's essentially doing "joins" on the read path. But it's all hitting caches, so it's fast still.
For some complicated queries, you can cache secondary indices (which is easier to figure out the "when/who" question, just as how DB figures out which index entry to update on transactions) to make your read-path join faster.
Now getting back to the “what’s really hard about cache invalidation” part. Even with a much simpler model. Say you just have a k/v store, no joins, nothing. Is cache invalidation simple in that case?
I went into details about why it’s still insanely hard. And the big example at the end might help make that point.
And this is one level beneath challenges from tracking dependencies, and I argue that’s what makes cache invalidation hard.
Now going back to your example with complicated dependencies. Maybe TTL is a better solution. With many dependencies, any changes from the dependency list might trigger invalidation. At some point, just doing TTL, would be simpler.
"Please use the original title, unless it is misleading or linkbait; don't editorialize." - https://news.ycombinator.com/newsguidelines.html
Editorializing the original title to make it more linkbait is going the wrong way down a one-way street. Please don't.
(If you're the author, then please either use the original title or, if it's linkbait, change the HN title to make it less so.)
I respect the guidelines and I am OK with the rename. I just want to clarify that I don’t think the old title is misleading.
Which I don't think it is.
> casually optimistic claims about complex and hard problems are the essence of click-bait
A group of people at Facebook worked on this for many years. TAO and Memcache serves quadrillions of queries a day. I wanted to make this claim – cache invalidation might no longer be a hard problem in Computer Science – years ago; but I didn't because I don't want to jump the gun. We baked the solution for years. There's nothing casual about this.
Will you be writing this up as well? It's very ambitious!
If C++'s memory model can abstract away multiple cachelines, why can't we steal the idea and abstract away distributed system details? The single keyword of distributed systems is "order". And that's exactly what `std::memory_order` captures, which is not a coincidence.
You can DM me and I would love to chat. I am @uvdn7 on twitter.
I went into details in the post about what I believe is the root cause of why cache invalidation is hard, which seems different than what you are saying.
TL;DR this is a blogpost about some very interesting problems with distributed cache consistency and observability. The article doesn't address cache invalidation and - based on their replies here - the author doesn't seem to understand the cache invalidation problem at all.
On the definition of cache invalidation, and specifically why it's hard. Can you send me a link to any definition of it? This is what's in wikipedia and I think it's reasonable.
> Cache invalidation is a process in a computer system whereby entries in a cache are replaced or removed.
And I think I am describing that process, and what's hard about it. Some comments here explicitly talk about dependencies, which I can see why it's hard. My point is that even without dependencies, cache invalidation remains a hard problem. Now about dependency tracking, some of my thoughts are captured here https://news.ycombinator.com/item?id=31674933.
This comment describes the "hard" part of cache invalidation best: https://news.ycombinator.com/item?id=31674251 - your response to them makes very little sense.
First, you acknowledge that they're correct, though you use obtuse language to say so: you seem to like using the very abstract term "dependency" to represent the very simple concept of detecting updates.
In your second paragraph you then go off on an unrelated tangent by saying:
> Now getting back to the “what’s really hard about cache invalidation” part.
No. You're not "getting back" to that - you're changing the subject back to the topic of your article, which is unrelated to cache invalidation.
> Say you just have a k/v store, no joins, nothing.
Cache invalidation is about invalidation - it's not about your store architecture. It's not about the implementation of logic that processes the clearing/overwrite of values, it's about the when and nothing else.
> just doing TTL, would be simpler.
Yes. It is simpler. If you want to avoid solving the hard problem, you can use a TTL. Now... how long should it be?
E.g. in its most generic form, a cache can store arbitrary materialization from any data source. Now when updating the data source, in order to keep caches consistent, you essentially need to transact (cross system transaction) on both the data source and cache(s). Usually cache has more number of replicas, I am not sure running this type of transactions is practical at scale.
What happens if we don't transact on both systems (the data source, and cache)? Well, now whenever the asynchronous update pipeline performs the computation, it's done against a moving data source (not a snapshot of when the write was committed). Now let's say the data source is Spanner, which provides point-in-time snapshots. On Spanner commit you can get a commit time (TrueTime) back. Now using that commit time, to read the data and compute cache update asynchronously can be done.
Because the materialization in cache don't take writes themselves, so updates to them are essentially performed blindly and can be ordered by the commit time (TrueTime).
Now this does assume whatever we cache (the query e.g.) needs to be schematized, and made known to the invalidation pipeline (in the form of some control plane metadata). I think it's a very fair assumption to make. As otherwise (anyone can cache anything without the invalidation pipeline knowing at all), it's pretty obvious that this problem can't be solved.
> The invariant is that as long as the "context/filter" you encode covers all the mutations which would impact your cache data, you should be good.
I wrote this line, which is referred to as that being exactly why cache invalidation is hard, in the commented you linked.
> it's about the when and nothing else.
Let's talk about that. Not to over generalize this, with a simpler cache model (say you just cache a single item), do you agree that solving the "when" problem is very managable? If not, I would like to be enlightened.
Now with this very simple cache model, where we have "magically" solved the "when" problem. Do you think cache invalidation is solved? Or it's simple? After knowing when, you still need to actually update cache right, and not to leave it in an inconsistent state (against the source of truth). Is that simple?
Let's essentially break cache invalidation into a few parts 1. knowing when/who to invalidate 2. actually processing the invalidate
My argument is that #1 can be very managable with simpler data models. #2 can't be avoided; and #2 is very hard.
The "when" problem is dependent on your application architecture, not on your cache backend nor the number of keys in it.
If, overall, you have an extremely simplistic application architecture, then cache invalidation may be quite easy, but you'll either:
1. forgo advanced user interaction or dynamic updates, in which case cache invalidation may not even be required at all (excepting publishing)
2. have scalability problems, and need to increase the complexity of your application to meet those challenges
The difficulty of cache invalidation scales with the complexity of your application (and not necessarily linear scaling)
> My argument is that #1 can be very managable with simpler data models. #2 can't be avoided; and #2 is very hard.
Yes, #1 can be manageable for low-traffic simple static applications. It is a general problem who's difficulty relates to the complexity of the application.
Yes, #2, can't be avoided. But, while it is interesting, and - in some cases, given a specific caching stack - it may be relatively hard, it's not a general problem. Difficulties with it are implementation-specific, not broadly applicable. Significantly, it's not the general and fundamental hard problem being referred when people talk about the universal difficulty of "cache invalidation".
I would argue the "when" problem is dependent on data models. And it's possible that we are referring to the same thing with different names.
> If, overall, you have an extremely simplistic application architecture
I mean FB is not a simple app. A complicated app can be built on a relatively simple data model as well (that's essentially how TAO works). But we do have memcache as well; and in some cases it can be complicated/hard. I can see that, and I won't argue against it.
> Yes, #2, can't be avoided. But, while it is interesting, and - in some cases, given a specific caching stack - it may be relatively hard, it's not a general problem.
I respectfully disagree. I explained in the blog post about why #2 is a generally hard problem. The analogy I like to use is Paxos. The protocol fits on a single slide. It's easier to feel like you have Paxos work; but it's very hard to have Paxos actually work.
I think you fundamentally misunderstand what the word "general" means here.
I have nothing more to add, if that's your standpoint. But I am glad that we "debugged" to close to the "root" of our assumptions/context.