1
$\begingroup$

I'm trying to optimize a system with a better algorithm for allocating storage. The system has 'N' writer processes and 'M' disks. (N < 30, M < 10. N can change, M is constant).

Any process can write to any disk and each process regularly writes a file every, say, 5 minutes, but the size of the file can be quite different. Each writer independently "chooses" which disk it writes to on a file-by-file basis; so it might write one file to Disk 2 and the next file a few minutes later to disk 8. There is no communication between writers.

This goes on forever.

enter image description here

In the steady state, all disks are "full" and a "deleter" process continuously deletes the oldest files until all disks are no longer "really full". (there are two water marks: "almost full" and "really full", if that helps), so the "deleter" wants:

        Almost Full    Really Full
Disk 1       Y             N
Disk 2       Y             N
Disk 3       Y             N

I need to optimize how the writer chooses which disk to write to such that, as much as possible, different writers are writing to different disks. This is important to balance I/O load.

I had thought this wouldn't be too hard, but the more I think of it, the more problems arise. I've tried a number of things:

  • Randomly choose disk from those with free space. However since there aren't many disks (M is small), there is a good chance all writers will choose the same destination disk and overload the I/O system. Bad.

  • Index/hash the writer number across the list of disks with free space. So if N == M, Writer 1 always ends up writing to Disk 1. However this fights with the deleter working to maintain free space by deleting the oldest files: eg, the first disk gets full but the oldest file is on a different disk.

  • Use first free disk. However this ends up with all writers writing to the same disk.

$\endgroup$
6
  • $\begingroup$ This looks like a system design problem. In systems design, knowing the scale of different parameters is important. The answer is likely to depend on these parameters: things like the RTT to communicate between writer and disk, the distribution of file sizes, how much you care about minimizing the complexity of code or the time spent programming this, whether we need to design around the possibility of network failures or node failures, etc. $\endgroup$ – D.W. Dec 7 '20 at 19:37
  • $\begingroup$ DW, it is simpler than that: everything in one machine. "writers" and the "deleter" are processes (running in Linux) and "disks" are mounted ext4 volumes. Writers just need to independently choose which disk to best spread load across available disks. $\endgroup$ – Danny Dec 8 '20 at 0:55
  • $\begingroup$ What are the restrictions? Can they synchronize and make a decision together? Can they see where other writers are writing and use that to adjust their choice? $\endgroup$ – D.W. Dec 8 '20 at 2:35
  • $\begingroup$ Ideally, the writers should be completely independent; a writer only gets a list of disks with "enough" space. I'd like to avoid having writers communicate with each other. $\endgroup$ – Danny Dec 8 '20 at 12:05
  • $\begingroup$ Can you put more descriptive tags on your Question, please. $\endgroup$ – Max N Jan 20 at 12:43
1
$\begingroup$

There are multiple solutions to this problem:

  1. Consistent hashing with bounded loads
  2. Generic Bin packing algorithm(Knapsack or other)

Both require that the writer know the free storage amount of the drives.

Consistent hashing with bounded loads is based on the consistent hashing algorithm published by akamai and fixed the issue of load inbalancing by overflowing across the ring to the next free "bin".

$\endgroup$
3
  • $\begingroup$ "Consistent hashing with bounded loads" sounds interesting, please give a brief description and a link. $\endgroup$ – j_random_hacker Jan 20 at 17:33
  • $\begingroup$ Thanks, it looks like consistent hashing (with or without bounded loads) is designed for the more complicated situation in which not only the number of writers ( = balls, clients) but also the number of disks ( = servers, bins) can change over time. Still might be helpful. $\endgroup$ – j_random_hacker Jan 20 at 18:04
  • $\begingroup$ nice to hear that! $\endgroup$ – Max N Jan 20 at 18:07

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.