| ▲ | josephg 2 days ago |
| Interval tree clocks seem really cool, and I’d love to use them for something. But unfortunately I can’t think of a way to reliably have a system automatically subdivide an interval to bring new servers up without getting pathological behaviour sometimes. Or, if an identifier (interval) goes offline indefinitely, I can’t think of any good way to clear it. In practice, vector clocks / version vectors built using uuid identifiers for machines seem easier to work with, and they’re very predictable. Slightly less efficient - but versions take up a tiny percentage of network traffic and disk space that I don’t think it matters. I really want to use interval tree clocks for something. It’s such a cool algorithm. But I don’t know what I’d use them for - beyond maybe a set of manually provisioned servers syncing data or something. |
|
| ▲ | catwell 2 days ago | parent | next [-] |
| I don't really know what you mean regarding pathological subdivisions, but the case where nodes go offline without merging first is a real issue. There are ways to work around it but if you have to do so you lose a lot of its advantage compared to other schemes. When I did that talk I was at the point you are now, trying to find a real use case. I had considered them for Lima but we were actually find with version vectors. I think the case where ITCs can really shine is when you have a lot of short-lived nodes. That could be containers or serverless functions, for instance. I didn't think about the tracing use case but it makes a lot of sense, you can fork a new node per request. |
| |
| ▲ | josephg a day ago | parent [-] | | > I don't really know what you mean regarding pathological subdivisions I mean - lets say I'm making a collaborative text editor. If I use a CRDT, I need clients to be able to emit changes with unique IDs. The obvious way to do that with ITC is to have a server (or set of servers) hand out part of their interval to clients. And the normal way to hand out part of the server's interval is to split it in two each time. If you have N clients join the server, the server will end up with 1/2^n of the keyspace - since it keeps halving each time a client joins. And some of those clients will just - go away, indefinitely, without "giving the key back". So the server's interval gets smaller and smaller, and the key (interval) that new clients are given will take more and more bits over time. Linearly more bits. With random IDs, the client never needs to give the ID back. You still have problems that the version grows over time - but I can think of a bunch of ways to deal with that. I haven't figured out how to solve that problem with interval tree clocks. | | |
| ▲ | catwell a day ago | parent [-] | | Yes, if you assume some of the clients go away indefinitely without giving their share back and you don't have a solution to deal with this, it's a problem. Solutions are relatively easy on a client-server model (but do you really need something like ITC with a server...?) For instance the server could delegate its part of the interval with a timeout and claim it back once it expires. If you know you have this model you can find a different way to split the interval to avoid the issue of the linear number of bits. Nodes can split their interval however they want. |
|
|
|
| ▲ | catlifeonmars 2 days ago | parent | prev [-] |
| Merging actually seems quite simple given an external coordinator. All you need is some periodic process that can observe the state of the clock, find gaps, and communicate the merge with one of the adjacent nodes. It is something that can be eventually consistent. Splits could occur similarly. Sure you have to ensure single writes from the coordinating process, but that’s easier to solve bc of the relative infrequency that the coordinator needs to run, leaving lots of time for consistency in between updates. The key assumption I’m making here is that nodes communicate much more frequently than nodes are added and removed from the system. We’re optimizing for the latency of the former at the cost of latency of the latter. |
| |
| ▲ | hedgehog 2 days ago | parent | next [-] | | The special thing about ITC is you can do the splitting (to add a member) and joining (to remove one) without any external coordination. They otherwise are used in the same way as vector clocks. I find the linked post more confusing than I remember the original paper being (I wrote an implementation): http://hydra.azilian.net/Papers/Interval%20Tree%20Clocks.pdf | | |
| ▲ | catlifeonmars a day ago | parent [-] | | Hmm yeah, I think I glossed over that point when reading the article. Looking at the paper you linked, I think the clock can be generalized to operate in Q^n. In other words, it doesn’t need to be a real valued space, and it doesn’t need to be bound by to special case of 1 dimension (interval). It only needs to arbitrarily subdividable and have the appropriate boundaries. |
| |
| ▲ | josephg a day ago | parent | prev [-] | | I'm thinking about this in the context of an eventually consistent CRDT or something. In that case, you need to handle the use case of a client going offline (eg the person is on holiday) and they make changes but aren't online for 2 weeks. If a peer isn't emitting changes, I don't see how you can safely merge their keyspace - since they might still be using that keyspace, but be offline, and you can't know. | | |
|
