Why do some filesystems out there have imaps to imaps to imaps (multiple imaps)?

Question

It seems that the point of an imap is to hold points to individual inodes so that writes can be done in a really fast manner (can someone explain how this works as well?) but I was wondering what the point of having imaps that contain pointers to other imaps was. Not only that, but they exist on multiple levels as well...

Answer 1

An iNode Map (sometimes mangled to imap, though IMAP is an e-mail protocol), is a pointer to an iNode (seems you got this already). This is used on journaling (mainly Log File Systems) as an abstraction layer. Basically when you want to lookup a give File System iNode, a translation layer looks up the iNode Maps for that location, and returns the current iNode that the file system actually should be pointing at. This location is then read to find the file.

Some file systems can stack these. When a single logical File System iNode is written to multiple times without flushing the journal/log then each write will use a new physical location on the disk, including an iNode pointing to that location. Each outdated iNode Map gets updated to point to the new iNode Map, and eventually to the current iNode.

The reasoning behind these is not speed, but consistence. During a write a new location is selected on disk, the write is doing, then the old location is updated to point to the new location. When the journal/log is consolidated the File System is updated to point to the latest location and the old locations are freed. This way if there is a power failure at any time you will never lose data, either the File System points to the old version of the file or the new, but never anything else (like a half written file, or corrupted data, or into the grass).

Answer 2

It's a fairly typical way of dealing with structures that point to other structures and may vary radically in size. The filesystem is already managing fixed-size blocks of storage space on the partition. So you generally use that size (or a multiple of it) as your unit size.

If you have few enough objects that you can hold them in a block, you do so. If a block overflows, you replace one item in that block with a pointer to a newly-allocated block that holds the pointer you replaced and the new pointer.

This method is chosen because:

1. It plays nicely with caching. The highest-level blocks tend to get accessed a lot and stick in cache.

2. It only requires tracking free space in block-sized units, so it works well with bitmap-based free space management.

3. It scales well, with an average lookup time roughly proportional to the log of the number of elements. (Theoretically, if you store 32 pointers in a block, you can access 32^n pointers with n lookups.)

4. It balances well dynamically. As you add or remove pointers, fairly simple operations can be performed to keep the tree balanced. (You don't want to get a long, skinny tree. You want to keep it fat and short. This is actually very easy to do.)