5 ms·

I see a couple of monitoring/reporting systems.. but no caching solution. These are tools to catch bugs in the solution you're using. Good work, but not a solut

I see a couple of monitoring/reporting systems.. but no caching solution. These are tools to catch bugs in the solution you're using. Good work, but not a solution for cache invalidation. 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.

uvdn7 4y ago
> but not a solution for cache invalidation 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.
- snarkypixel 4y ago
  I also was surprising to not see the solution to the cache invalidation. The blog post describes how the tracing/logging mechanism works, but what about the actual cache consistency/invalidation strategy? I.e. what about many-to-many where one fetch returns inconsistent results.. how do you even know it's inconsistent? What about data queried while there's a transaction rollback.. when is it updated in the cache? 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"
  - uvdn7 4y ago
    These are good questions. I might not have satisfying answers to all of them but I will try. > 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 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.
    - i_r7al 4y ago
      > delaying performing the compute-intensive operation until an inconsistent sample crosses the reporting timescale 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?
      - uvdn7 4y ago
        No actually. When a sample has crossed the reporting timescale, and it's inconsistent. Regardless of if the db changes later or cache becomes consistent later, at the moment it's still an anomaly (inconsistency in this case).
uvdn7 4y ago
> Good work, but not a solution for cache invalidation. 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.
- uvdn7 4y ago
  More details can be found at https://blog.the-pans.com/when-and-how-to-invalidate-cache/ https://blog.the-pans.com/when-and-how-to-invalidate-cache/
  - yencabulator 4y ago
    From the article: - 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 now have caches fetching & storing the "old" state between the last two steps. This fails to invalidate cache in all scenarios.
    - gigatexal 4y ago
DeathArrow 4y ago
>I understand this is being used in prod, but network partitions don't occur everyday... 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"?
- uvdn7 4y ago
  My experience is that this is easier said than done. But I agree with you that in theory, one can inject failure and run tests with all possible combinations, and have a repeatable test framework (think about foundationdb’s test framework) to help root cause test failures. Sqlite has very impressive reliability; its test framework is not open sourced. It also benefits from user bug reports, as it’s literally the widest deployed db. Bugs/flaws happen. Having better tests and better observability in production are also not mutually exclusive.

uvdn7 4y ago

> but not a solution for cache invalidation 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.

snarkypixel 4y ago
I also was surprising to not see the solution to the cache invalidation. The blog post describes how the tracing/logging mechanism works, but what about the actual cache consistency/invalidation strategy? I.e. what about many-to-many where one fetch returns inconsistent results.. how do you even know it's inconsistent? What about data queried while there's a transaction rollback.. when is it updated in the cache? 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"
- uvdn7 4y ago
  These are good questions. I might not have satisfying answers to all of them but I will try. > 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 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.
  - i_r7al 4y ago
    > delaying performing the compute-intensive operation until an inconsistent sample crosses the reporting timescale 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?
    - uvdn7 4y ago
      No actually. When a sample has crossed the reporting timescale, and it's inconsistent. Regardless of if the db changes later or cache becomes consistent later, at the moment it's still an anomaly (inconsistency in this case).

uvdn7 4y ago

> Good work, but not a solution for cache invalidation. 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.

uvdn7 4y ago
More details can be found at https://blog.the-pans.com/when-and-how-to-invalidate-cache/ https://blog.the-pans.com/when-and-how-to-invalidate-cache/
- yencabulator 4y ago
  From the article: - 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 now have caches fetching & storing the "old" state between the last two steps. This fails to invalidate cache in all scenarios.
  - gigatexal 4y ago

DeathArrow 4y ago

>I understand this is being used in prod, but network partitions don't occur everyday... 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"?

uvdn7 4y ago
My experience is that this is easier said than done. But I agree with you that in theory, one can inject failure and run tests with all possible combinations, and have a repeatable test framework (think about foundationdb’s test framework) to help root cause test failures. Sqlite has very impressive reliability; its test framework is not open sourced. It also benefits from user bug reports, as it’s literally the widest deployed db. Bugs/flaws happen. Having better tests and better observability in production are also not mutually exclusive.