Message ordering in distributed system
distributed, messaging, system
Solution
This is a fundamental problem in distributed systems known as Atomic Broadcast, with a number of solutions offering different performance and applicability trade-offs (see the survey referenced by the wikipedia page). In practice, the most commonly used are based on Paxos (e.g., libpaxos) or on Totem (e.g., Corosync or Spread). A key issue when selecting one of these is what do you expect to happen if the network partitions: Should it stop ordering messages (block) or should it produce independent orders for each partition?
Problem
I want to build a distributed system where I have "threads" (a collection of messages with it's own ID, not a system process) that are distributed across many servers. These threads must have two critical properties: - Each message in thread must have an order number that reflects it's position in thread based on time. For example by saying "thread1/message10" I can get to message #10 in thread #1 - Once new message gets added to thread a system must be able to assign it an order number that is consistent for all instances of thread on all servers and this number must never change. I want to know if there's any known solution, library or algorithm that can help me implement a second option because now I see it as a big problem because due to many factors different servers can get the same message at different times and that might affect it's order number. Just to outline my thoughts on a problem so far say I have 3 servers with my distributed thread which already contains 5 messages and each server sends a new message to it's own thread and to remaining two. Naive ordering. Each server think it's own message number is 6 and the remaining two messages from other servers will get their numbers on arrival depending on network latency and many other random factors so order numbers are not consistent across servers. This is unacceptable right away. UTC timestamp based ordering. When each thread gets a new message I take say 10 preceding messages that already have correct order numbers, extract their timestamps and determine a new message's order number by finding it's timestamp place in a list of last 10 timestamps. This might work I guess but it does require that some message's order number can be assigned and then changed at some point which is unacceptable. Also I'm not sure if this will work right when a number of incoming messages is huge. Thanks for all the help.