Right now I am working on a distributed system that sends messages from single source to many nodes. It is necessary that certain messages are sent to the same node to ensure order of processing. Using simple hashing on an important piece of the message to decide which node to send to works but leads to significantly uneven distribution. This is because some sets of messages may only occur 10 times in a day, while others might occur 1,000,000 times.
I came upon the idea to instead of use hashing, find average message counts for each recurring type (there are thousands) over a reasonable amount of time and then attempt to organize them into as-even-as-possible sets for each node. This way each node will receive a similar amount of messages.
A simple case with 2 nodes and 4 items explains this:
message_counts_by_type = [1,3,7,9]
[ [1,9], [3,7] ]
Now each node has an even amount of messages (10)
My naiive solution (which gives this result) was to break the set of message type counts into sets the size of the number of nodes
and then select which item to give to what node with a rotating index so that on one run node1 will get the lowest number and node2 will get the highest, and on the next run the opposite.
Here it is abstracted to n nodes in python:
counts = [1,3,3,6,7,...9999] nodes = 8 chunks = [ counts[i:i + nodes] for i in range(0,len(counts), nodes)] # [ [1,3,3], [6,7,9] .... [9997, 9997, 9999] ] counter = [i for i in range(0,nodes)] # [ 1, 2, 3... nodes ] slots = [ for _ in counter] # [ , , , ....  ] for i in range(0, len(chunks)): chunk = chunks[i] for j in range(0, len(chunk)): slots[j].append(chunk[counter[j]]) # rotate counter array # [ 1, 2, 3, 4] -> [ 4, 1, 2, 3 ] counter = [ counter[i-len(counter)] for i in counter ] # get final count of each set/node reduction = [ reduce((lambda x, y: x + y), slot) for slot in slots ]
Anyways, even though it works (better results than just hashing) I feel like this is naive and there is probably a smarter way to accomplish the same thing.