Thursday, June 21, 2012

Parallel worlds

Since the single threaded file system implementation is done, we may investigate another implementation which can write in parallel.

The first question regarding this subject is 'Is this real useful?' and the answer is 'It depends.'. The following article shows why this is the only possible answer.

At first let's talk about resources: The physical resource is given by for instance a single hard disc. We have multiple physical resources if we have an array of hard disks. So our expectations are: Parallel writing to one single disc does not bring any benefit. Instead we assume an overhead which is caused by the fact that the threads have to be managed.

Additionally we have to face logical resources. A logical resource is a file which is provided by the disc's file system. Even if we have an array of physical disks available, we can just write to one file by using exactly one thread.

Let's spot some light on my current idea to implement such a parallel writing.

* A Segment is realized as one file. So one segment is exactly one logical resource.
* A parallel writer should be able to write multiple segments in parallel.

So I extended a File System to write and append an array of blocks. To avoid resource blocking, I am using a 'Slicing' mechanism.

At first we index the Blocks by their Segment id. Such an SegmentIndex is a Hash Index which has the Segment Id as the key. The value for each key is a list of Blocks. It looks as the following:

- (0,1) -> [Block_011,...,Block_01n]
- (0,2) -> [Block_021,...,Block_02k]
- ...
- (c,s) -> [Block_cs1,...,Block_csb]
- ...

Whereby 'c' is the container id, 's' is the segment id within the container and 'b' is the block id within the segment.

Now we can just slice the index. The first slice is E.G.:

[Block_011, Block_021, ..., Block_cs1, ...]

Each entry of the slice points to another segment. What we now need is a pool of Writer Threads whereby one thread writes exactly to one of  the entries of the slice. It's surely possible that there are less or more entries than Writers are available. If there are more, then the thread pool queues it.

I already added a simple benchmark test, which shows that now all 4 CPU-cores of my test box are busy. Before it was just one CPU.  But because my development box has just one single hard disc, I can't evaluate the benefits yet. Some meaningful benchmarks will follow.  Quite interesting may it to test with an SSD because there is no seek time.  However, in summary we can say that writing to a disk is indeed absolutely IO bound and so less CPU bound. This raises again the question 'Is this useful?'.Further evaluation will show it.

Feedback? Just post a comment to this article.