Take the 2-minute tour ×
Server Fault is a question and answer site for professional system and network administrators. It's 100% free, no registration required.

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...

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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).

share|improve this answer

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.)

share|improve this answer
    
You make some good points about data structure clustering and layout, but what does any of that have to do with the operation of Journal/Log FS pointer data structures? –  Chris S Oct 26 '11 at 20:11
    
He asked why imaps have pointers to other imaps on multiple levels. It's because that's an efficient data structure. –  David Schwartz Oct 26 '11 at 20:24
    
That's an interesting concept I hadn't heard of before. You wouldn't happen to know of any websites were I could read up more on the efficiency and performance of nesting file system data structures? –  Chris S Oct 26 '11 at 20:26
    
The Wikipedia article on inode pointer structures explains how this same structure is used to track file contents. (The main difference being the article is about inode->block->...->block->data and imaps are imap->...->imap->imap->inode, but the technique is substantially the same.) –  David Schwartz Oct 26 '11 at 20:42
1  
Yes, I understand iNodes and how they point to multiple data blocks and can point to other iNodes for larger files. That still doesn't address why using multiple iNode Maps would improve efficient or performance. It seems counterintuitive that adding a layer of abstraction would make referencing an iNode more efficient. –  Chris S Oct 27 '11 at 1:22

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.