3
$\begingroup$

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]

desired result:

[
    [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

[[1,3],[7,9]]

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.

Any ideas/criticism?

Thanks.

$\endgroup$
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Bin_packing_problem $\endgroup$ – D.W. Apr 11 '18 at 0:15
  • 2
    $\begingroup$ IIUC, your problem is called multiway partition. @D.W.'s suggestion can be adapted to your problem as follows: Pick a large bin capacity and solve bin packing with this capacity; if fewer than nodes bins are required, then decrease the capacity and try again. Keep doing this until making it any smaller requires more than nodes bins. (I can prove that) this produces an optimally even partition into nodes parts. You can use binary search on the bin size to speed this up, but note that every single BP instance is an NP-hard problem, so solving it exactly could be slow. $\endgroup$ – j_random_hacker Apr 11 '18 at 11:03
  • 1
    $\begingroup$ Sorry, but I was too quick to claim I can prove that an optimally even partition can be found via bin packing. A partition that minimises the largest sum can indeed be found using the binary search I suggested, but if your goal is to minimise the spread (difference between the largest and smallest sums), then my suggestion doesn't always work. ... $\endgroup$ – j_random_hacker Apr 14 '18 at 12:08
  • 1
    $\begingroup$ ... Here is a counterexample: the unique partition of $\{9,9,9,12,14,19\}$ into 3 parts with minimum maximum sum is 9+9+9=27, 12+14=26, 19, with maximum sum 27 and spread 27-19=8. But the partition 19+9=28, 9+14=23, 12+9=21 has larger maximum sum (28) but smaller spread (28-21=7). Since bin-packing will consider only partitions having minimum maximum sum, it will miss this optimal-spread solution. $\endgroup$ – j_random_hacker Apr 14 '18 at 12:08
  • $\begingroup$ @j_random_hacker thanks for your insight. I have some reading and experimenting to do to attempt your suggestions, I'm not a trained computer scientist, just a self taught programmer and this problem has opened up an interesting can of worms for me. I modified my original algo with a second step that redistributes smaller types from overloaded nodes to underloaded ones to try and even the distribution as much as possible. It leads to better results but definitely not optimal. $\endgroup$ – AllTheTime Apr 17 '18 at 19:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.