Open zepatrik opened 3 years ago
Also found an interesting clock algorithm that is based on a logical ring of nodes, as we might use anyway for consistent hashing @jon-whit https://www.researchgate.net/publication/221134159_An_Efficient_Implementation_of_Vector_Clocks_in_Dynamic_Systems
@zepatrik interesting! I did a quick pass over the paper and it looks quite interesting and promising. I need to read it with way more detail to fully understand though.
On a special type of check request, the content-change check, zanzibar issues a zookie of the latest snapshot.
The zookie encodes the evaluation snapshot and captures any possible causality from ACL changes to content changes, because the zookie’s timestamp will be greater than that of the ACL updates that protect the new content
All it tells us that the data we need for ACL evaluation are propagated already, so we can proceed right? If you would store, let's say, a UUIDv4 together with the relation tuples affected by an ACL update, you can determine whether those data are propagated based on whether the lookup succeeds. For deleting events this would mean adding a tuple that represents the deleted tuple with a new UUID (lets call that gost tuple). By looking up the UUID from the zookie, we can determine whether the data were updated already. For causally related events this would also work I think because you can only apply an event if the previous events UUID lookup succeeded (i.e. the previous event propagated). This way we implicitly build a chain of related events. Issuing events with no zookie on the other hand would start a new event chain, i.e. be concurrent in terms of distributed systems. The client always has to make sure that requests include the right zookie.
Example:
UUID1
to all the new relation tuples (or ghost tuple) and give that back as the zookie1
zookie1
)
UUID1
, if yes handle request, if no forward to other nodeszookie1
)
UUID1
, if yes handle request, if no forward to other nodesUUID2
and update all tuples with UUID1
to UUID2
UUID1
is marked as obsoleted by UUID2
(to be determined whether needed)UUID2
as zookie2
zookie2
)
UUID2
, if yes handle request, if no forward to other nodesUUID3
and assign it to the new tuples (or ghost tuple if only deletion)UUID2
to UUID3
UUID2
is marked as obsoleted by UUID3
(to be determined whether needed)UUID3
as zookie3
zookie3
)
UUID3
, if yes handle request, if no forward to other nodesAll steps are executed as one transaction.
Concurrent transactions should fail because they are updating the same tuples and therefore result in a conflict.
The lookup table for old UUIDs is required to determine whether a "old" zookie is obsoleted by another one. This table can probably be kept contained in size because we can handle zookies so old they are fully propagated by just not applying the check step.
Maybe we can also have a separate table for events instead of having the event IDs in the relation tuple table(s).
Is there anything I missed?
Wouldn't this strategy require that, when writing a relation tuple or executing a content-change check, a UUID would have to be generated and written for any relation tuple involved in the graph of relations traversal? Including those through userset rewrites. And if so, this approach seems like it'd be quite a latent approach.
Consider the scenario where a check is dictated by a relation tuple in another namespace through a userset rewrite rule (tupleToUserset) or where a check's outcome is dependent upon a computerUserset within the same namespace. In these scenarios you'd have to traverse the graph of relations and write the UUID for all tuples involved in the traversal. These writes would also have to be replicated across the majority of replicas in the database cluster, which would further slow down the latency of the check request.
These are the reasons why Spanners snapshot reads with bounded staleness alleviate this issue. You can read all of the tuples of the namespaces involved in the graph traversal at a snapshot no staler than the provided zookie timestamp. So the read might incur a delay because the majority of replicas have to agree on the read snapshot, but they don't have any majority replica write delays. The write latency is incurred only when writing a new relation tuple.
I fear this approach would ultimately dominate the tail latency of Keto, and for a multi-region cluster it probably wouldn't be uncommon to see no less that 200ms for db replication.
Summary of yesterdays synchronous discussions:
So next steps would be to investigate further how the individual approaches look in practice. Come up with a POC. Probably it will make most sense to go with the first approach for now and add optimizations to that (like 2. approach) later on when we have exact cases of failure or unacceptable latency.
Hello contributors!
I am marking this issue as stale as it has not received any engagement from the community or maintainers a year. That does not imply that the issue has no merit! If you feel strongly about this issue
Throughout its lifetime, Ory has received over 10.000 issues and PRs. To sustain that growth, we need to prioritize and focus on issues that are important to the community. A good indication of importance, and thus priority, is activity on a topic.
Unfortunately, burnout has become a topic of concern amongst open-source projects.
It can lead to severe personal and health issues as well as opening catastrophic attack vectors.
The motivation for this automation is to help prioritize issues in the backlog and not ignore, reject, or belittle anyone.
If this issue was marked as stale erroneous you can exempt it by adding the backlog
label, assigning someone, or setting a milestone for it.
Thank you for your understanding and to anyone who participated in the conversation! And as written above, please do participate in the conversation if this topic is important to you!
Thank you 🙏✌️
Unless we add an interim storage such as redis, I think it would make sense to rely on database features such as follower reads to perform fast queries on (slightly stale) data. Please note that follower reads are an enterprise feature in cockroach, but queries will still work in the open source version of it (they'll just be slower).
For the time being I don't think it makes sense to add a cache such as redis. If you need inspiration, spicedb has implemented snapshot tokens using follower reads.
Hello contributors!
I am marking this issue as stale as it has not received any engagement from the community or maintainers for a year. That does not imply that the issue has no merit! If you feel strongly about this issue
Throughout its lifetime, Ory has received over 10.000 issues and PRs. To sustain that growth, we need to prioritize and focus on issues that are important to the community. A good indication of importance, and thus priority, is activity on a topic.
Unfortunately, burnout has become a topic of concern amongst open-source projects.
It can lead to severe personal and health issues as well as opening catastrophic attack vectors.
The motivation for this automation is to help prioritize issues in the backlog and not ignore, reject, or belittle anyone.
If this issue was marked as stale erroneously you can exempt it by adding the backlog
label, assigning someone, or setting a milestone for it.
Thank you for your understanding and to anyone who participated in the conversation! And as written above, please do participate in the conversation if this topic is important to you!
Thank you 🙏✌️
The Zanzibar paper describes the so-called
zookies
to be used for evaluating checks at object versions. They use Googles true time feature to have global timestamps, which will probably not be available everywhere. The tokens are opaque and could encode arbitrary data that can be used by Keto to guarantee that it considers all relation tuples "at least as old as the object verstion". On an object update, Keto issues a new token that will then be stored by the application together with the corresponding object version. It might be possible to use some form of logical vector clock (e.g. bloom clock) as a token, or rely on cockroach to check whether the system time is within a specific window on each instance and get the time from there.