uvdn7

8 ms·

61.
by uvdn7 4y ago
I can't give away details/numbers. But I have to say, what you did right here is very impressive.
62.
by uvdn7 4y ago
> Paxos is an implementation (of protocols). 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.
63.
by uvdn7 4y ago
Interesting… what are your thoughts on Lamport’s TLA+?
64.
by uvdn7 4y ago
Let try to put this as concisely as possible. When you put an algorithm in code, when rubber hits the road, you have to make certain assumptions of how things work, eg how events are ordered, how fsync works, what kind of failure scenarios
65.
by 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)
66.
by uvdn7 4y ago
Yep. To generalize this even more, it’s not that cache invalidation is hard but “materialization/denormalization is hard” (even if it’s a table on the same database). Hence why I never thought this is what made cache invalidations hard
67.
by uvdn7 4y ago
Looks like the separate materialization (what's stored in cache) is schematized? I will take a closer read. It seems similar to what I described here https://news.ycombinator.com/item?id=31676849 .
68.
by uvdn7 4y ago
Let's actually also try to solve the "cache invalidation" 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 kee
69.
by uvdn7 4y ago
Let's solve 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 cons
70.
by 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
71.
by 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).
72.
by uvdn7 4y ago
> But what if you actually do want your dependency list to trigger invalidation? 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 ord
73.
by uvdn7 4y ago
You are right. The assumptions I made are - the definition of cache invalidation https://news.ycombinator.com/item?id=31676102 - subsequently, by that definition, _make_ cache consistent in production is the harder problem
74.
by uvdn7 4y ago
I also think it can be solved by changing the data model. 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
75.
by uvdn7 4y ago
Thanks for the reference. Naiad: A Timely Dataflow System is an interesting paper!
76.
by 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
77.
by uvdn7 4y ago
I am using the following definition from Wikipedia > 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" mus
78.
by uvdn7 4y ago
Yep. I respect this definition, and I tried to clarify things a bit here https://news.ycombinator.com/item?id=31676102 . I am sorry for the confusion. We have internal abstractions that deals with the problem you described (
79.
by uvdn7 4y ago
I understand some people have a different definition of cache invalidation. I am using the following definition from Wikipedia > Cache invalidation is a process in a computer system whereby entries in a cache are replaced or removed. It&
80.
by uvdn7 4y ago
> The "when" problem is dependent on your application architecture, not on your cache backend nor the number of keys in it. I would argue the "when" problem is dependent on data models. And it's possible that we
81.
by uvdn7 4y ago
You assessment is good. > 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 ca
82.
by 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 wil
83.
by uvdn7 4y ago
I am glad you caught that! I am personally very very excited about this. Because if you think about it, distributed systems and cache coherence problems on a multi-core system are essentially the same thing. If C++'s memory model can a
84.
by uvdn7 4y ago
Thanks for the links! 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
85.
by uvdn7 4y ago
The "hard problem" defined here is more about the engineering side. The analogy I have is Paxos the protocol and Google's Paxos Made Live paper. We do have many cache coherency protocols that are provably correct (using TLA+
86.
by uvdn7 4y ago
That's not intended. What's your definition of cache consistency?
87.
by uvdn7 4y ago
> the original cache invalidation problem 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 d
88.
by uvdn7 4y ago
I really appreciate your comment. I am learning as we speak. 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&
89.
by uvdn7 4y ago
First of all, I do think you folks make good points. Let me try again. > 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 w
90.
by uvdn7 4y ago
Yep. Polaris checks can be sampled, but still covers pretty much all types of workload and scenarios/races over time.

More ›