Logic required to solve a problem relating to location of objects

Question

I have raised a question on dba.stackexchange.com but as the heart of my question is in fact to do with logic I have raised a more general representation of my issue here. I think it is the right place, apologies if not.

I have a number of objects that are read and written to in a set sequence. I also have four locations in which I can store these objects. These objects vary in size but for the purposes of simplicity I have rated them 1 to 3 with 3 being the largest. Location of objects is fixed e.g. objects can not be moved in between sequence steps

I have a table which details the sequence of the process. It has three columns: Sequence, Source, Destination. Processes can and do run in parallel and therefore sequence is not a unique identifier however should one be required it can be considered to be in place.

In an ideal world no object should be located in a way that would result in no object required for a sequence step being co-located with another. Of course this is highly unlikely and instead I am looking for a best solution as opposed to a perfect one.

I have therefore considered that the potential locations may be best ranked as followed.

1. All objects for a sequence located separately.
2. Source and destination objects for sequence located separately.
3. Objects located anywhere

Given that each object has a size I also considered perhaps multiplying the location rank by the size and therefore giving the locations a score. Then based on this I could find the best solution by looking at it's total score.

Does anyone have any suggestions or perhaps addressed a similar problem in the past?

Any help input is greatly appreciated.

Answer 1

So, I'm still not sure that you have enough constraints to force a particular solution, but here's my best guess. From the follow-up comment on the DBA post, I think your real constraint is trying to minimize IO for any particular step of the operation and maximize overall IO throughput.

Starting out, I'll presume we only have Object (table) A on volume 1.
Future steps will generate:
A => B on vol 2
A + B => C on vol 3
A + C => D on vol 4

It's trivial to assign Objects A -> D to volumes 1 -> 4, and they'll never need to move. I suspect you've got a number of sets like this, so it's the scale that's complicating things.

Since you're using size of the object as your score, I would recommend you assign each volume a maximum score that it can handle at once. Size of the object will be coupled to the time of IO. For the sake of my solution, A & B = 1, C = 2, D = 3.

Allocate the sets with the simple mapping until you hit a volume that is completely IO bound. The 4th volume handling Ds will max out first, with the Cs volume coming in pretty close behind. At that point, rework the ordering of the volumes to objects. For this "fill-in" objects, Ds will go to vol 1 or 2, Bs & Cs will end up going to the other of vols 1 or 2, and reads from A will be on vol 3. I didn't add the numbers up, so my allocation on the fill-ins may be off.

At this point, you've pretty much maxed out the capacity of as many drives as you can. If you had more volumes, you could extend the model out so you would work the Nth, N-1, N-2 cases. That's more of an academic exercise for your case, I think.

I'm assuming you have more to move than you have IO bandwidth available, otherwise I'm not sure why you'd worry about this sort of round-robin allocation.