Coordinating with appendable data structures

After bootstrapping consul with cloud-init-buddy I also looked into bootstrapping zookeeper and the same pattern that worked for consul worked for zookeeper. I’m documenting the pattern because I think it is useful. You don’t need cloud-init-buddy to apply the pattern and any kind of data store that allows appending in an atomic way will work.

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: L
  4. While looping make sure our unique identifier is still in A
  5. Do the rest of the work

The above works because the unique identifiers and the length of the data structure guarantee that we will converge to a stable state without losing data. The number of nodes can register in any sequence and sometimes if a slow node comes along it will reset the data structure to an empty state. That is why when looping we need to make sure we check and re-add ourselves. The way we achieve stability is by checking the length and only proceeding when we have the required number of elements. This means that if you don’t know the number of nodes ahead of time then this pattern doesn’t apply and you have to do something else because you won’t know when the data structure is stable. The stability is what allows us to proceed with the rest of the process.