Coordinating with Appendable Data Structures

16th February 2019

There is a certain pattern that I think is useful but doesn't get enough air time. I'll outline the pattern in this post and in a follow-up post show how it can be used with cloud-init-buddy to bootstrap systems like consul, zookeeper, MySQL replication, etc. that require non-trivial sequential coordination and information sharing.

A Useful Coordination Pattern

Here’s the pattern in pseudo-code

  1. Initialize the appendable data structure: A
  2. Append to it a unique identifier: I
  3. Loop until the data structure has a specific length/size: L
  4. While looping make sure our unique identifier I is still in A and re-add it if it's not
  5. Do the rest of the work

The above works because the unique identifiers and the length/size of the data structure guarantee that we will converge to a stable state without losing data. It is a little bit like a CRDT because we avoid any conflicts by making sure the data is additive after an initial period of instability. The uniqe identifiers can be added in any sequence and sometimes if a slow registrant comes along it will reset the data structure to an empty state but that's ok because each registrant will re-add itself and rehydrate the data structure. The loss of information is transient because it only happens a finite number of times before entering the registration loop and since the registration loop is stable we can safely proceed with the rest of what follows after we have the required number of registrants.

This means that if you don’t know the number of registrants ahead of time then this pattern doesn’t apply and you have to do something else because you won’t know when the data is stable. The stability is what allows us to proceed with the rest of the process.

I've successfully used this pattern in various scenarios and in an upcoming post I'll outline how to use this pattern to bootstrap a consul cluster with as little overhead as possible.

$ ./ 6428f5771007cf005037d47c9aeac9bfcc8925f9  -