Algorithm for picking seedbox to put torrent on

Question

Which algorithm would be best for deciding which seedbox each torrent should go on? It must be able to fit the torrents in the minimum number of seedboxes, but also maximize the free space on each seedbox and equalize the number of torrents per seedbox. There may be other requirements for this application that I have not screwed up thought of yet.

My current dataset is 8.9TB in 154 torrents, but both numbers will be growing. My current seedboxes can each hold 455GB, but this will probably change in the future. 8.9TB/455GB = 20 seedboxes minimum and 154/20 = around 8 torrents per box, for my current dataset & seedboxes.

My first attempt was to walk through the torrent list from largest to smallest. If the current torrent would fit on the current seedbox, put it there and remove it from the list, then move on to the next torrent. Once the complete list of torrents was walked, move on to the next seedbox, starting the list of remaining torrents over from the largest remaining.

This resulted in 20 seedboxes (the optimal solution), but I ran into two different problems:

1. I underestimated the overhead on each seedbox. Since I stuffed as many torrents as I could on each, box 1 ran out of space. I solved this by moving a 4GB torrent to box 19, but it would be nice if the new algorithm did a better job of spreading free space around.

2. I ended up with three torrents on box 0 (and eventually box 1), and 51 torrents (eventually 52) on box 19. CPU/memory utilization on a seedbox is proportional to the number of torrents, regardless of the size of each torrent. This means box 19 is doing 17 times as much work as box 0. It would be nice if the new algorithm kept the number of torrents per seedbox relatively consistent.

My subsequent attempts REALLY aren't worth discussing.

A CPAN module already implementing the algorithm would be awesome (yeah, right). If you'd like to play with live data, a list of the current torrent sizes can be found at https://freerainbowtables.com/torrents.txt

Thank you.

Answer 1

I'd enumerate the torrents from big to small, putting each on a seed that currently has the maximum free size percentage. This should result in a relatively equal distribution of number of files and total size per seed. Of course, if you have seeds of highly different storage and transmission capacities, you will need a smarter algorithm, but for seeds that are basically all similar this should be good enough.

I don't have access to a computer right now, so can't run the algorithm on your data, but from a first impression, the sizes seem distributed such that it should work.

Update: Installed python on phone, here's code:

import requests

response = requests.get("https://freerainbowtables.com/torrents.txt")
data = response.text

filesizes = list(map(int, data.splitlines()))
buckets = [ {"seed":i, "size":0, "files":[]} for i in range(0,20)]

for n, s in enumerate(filesizes):
    bucket = buckets[0]
    for b in buckets[1:]:
        if b["size"] < bucket["size"]:
            bucket = b
    bucket["size"] += s
    bucket["files"].append({"n":n, "size":s})

for n, b in enumerate(buckets):
    print('{}: {} files, {} bytes'.format(n, len(b['files']), b['size']))

Output:

0: 8 files, 486654427136 bytes
1: 8 files, 486676852736 bytes
2: 8 files, 485931884544 bytes                              
3: 7 files, 486433857536 bytes                              
4: 7 files, 486393159680 bytes                              
5: 8 files, 486450675712 bytes                              
6: 8 files, 486064533504 bytes                              
7: 7 files, 486233931776 bytes                              
8: 8 files, 485878333440 bytes                              
9: 7 files, 484118614016 bytes                              
10: 6 files, 483423199232 bytes                             
11: 8 files, 486040858624 bytes                             
12: 9 files, 487123714048 bytes                             
13: 8 files, 485853274112 bytes                             
14: 7 files, 486502432768 bytes                             
15: 7 files, 486432681984 bytes                             
16: 9 files, 486372478976 bytes                             
17: 8 files, 485347581952 bytes                             
18: 8 files, 486434230272 bytes                             
19: 8 files, 485311655936 bytes