About :: TODO :: Blog :: RSS :: Old blog :: Projects :: GIT :: Gallery :: Notes

Thu, 06 Dec 2007

Multithreaded filesystem access.

Trees are generally (if not always) very bad in parallel access, since there is no a good strategy what to lock and tree modifications usually requires more than one node changes and in some cases (like b-tree or AVL tree) can lead to changes at every layer.
Thus it is much simpler to lock the whole tree during any changes, but since not every node in the tree is in the main memory and thus has to be fetched from the disk, this can lead to long delays per operation.
Contrary Linux VFS operates with pages, where each page is locked individually.
Similar changes for hash tables (i.e. one lock per hash bucket) actually leads to lower performance since when the whole table is locked by single lock because of bad cache line, containing per-bucket lock, bounces, but this, again, is only applicable to main memory, since usually access to single bucket in the hash table is quite cheap even if it contains several entries.
So, I do not know perfect locking scheme for trees, when they are allocated on the disk, so I will find that knowledge in experiments.

The best solution, which is the most related to the real life, is trivial filesystem of course.
Initially this will be a simple and very small kernel module with basic filesystem in it, so that it could be trivially changed to support on-disk filesystem and network filesystem.

I wanted to put my dirty hands into it quite for a while already, so it is time to start...
Stay tuned!

/devel/fs :: Link / Comments ()