Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
    
You haven't provided enough constraints to nudge the end algorithm in one direction or another. For example, are your volumes large enough to store all the objects? What mandates creating a sequence? What do you mean by the objects are operated on in a set sequence? Is it Obj A then B -> C -> D or is it A -> B and / or C -> D? If the latter, can we just simplify the problem and say 1 = A + B and 2 = C + D, so we have 2 objects instead of 4? –  GlenH7 May 17 '12 at 21:00
    
Thanks for taking the time to respond Glen. The volumes are all of the same fixed size. It is possible to store all objects on the same volume (it would probably best to not assume this though). Regarding the sequence, I can see how it isn't clear, hopefully the following clarification will help. Some processes are executed in parallel. e.g. Step 1 A is read from and B is written to. Step 2, A and B are read from and C is written to. Step 3, A and C are read from and D is written too. Once again thanks for your help. –  Ally Reilly May 18 '12 at 9:58
add comment

1 Answer

up vote 0 down vote accepted

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.

share|improve this answer
1  
Thanks for your answer Glen, it has helped me move towards a solution. –  Ally Reilly May 23 '12 at 10:58
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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