CIS 4307: File Structure - Stable Storage

Data and Index Blocks

Some observations:

• Access time is different at different locations in a file. The first 10 blocks are accessed with a single read (the pointers are in main memory where the inode is brought when the file is opened). The next 1K blocks require up to two reads, one for the index block, one for the data block. The next 1M blocks require up to three reads, and the next 1G blocks require up to four reads. Clearly access time is good at the beginning of the file and gets worse and worse as we move towards its end.
• One needs to have a clear idea of how addressing is done, i.e. how to determine, given an address, which blocks to read and how to compute displacements. For example, if we seek for byte 100,000,000 in a file, we need to go to the 12,207 block, and then look for the 256th byte. We skip the first 10 pointers (each to a block) thus remaining with 12197 to go. We skip the 11th pointer (which points to a single indirection index block with 1024 pointers to data blocks) thus skipping 1024 blocks remaining with 11173 blocks. We are now at the 12th inode pointer. From the 12th inode pointer we go to a double indirection index block. Here each pointer counts as 1K blocks. Thus we have to skip 10 pointers (i.e. 10*1K=10,240 blocks, thus remaining with 933 blocks to go) and follow the 11th pointer to a single indirection index block. Here we go to the 933 pointer and follow it to a data block where the 256th byte is what we are aiming for. Clearly we can write a procedure to do this calculation and to allocate index and data blocks if it is necessary for a write operation.
• The following is a legal sequence of operations: write one byte, seek 1MB(from beginning of file), write another byte, seek 1GB (from beginning of file) and write another byte. The size of the resulting file is 1GB+1 but most of it is with undefined content. One needs to understand the resulting structure of the file in terms of its data and index blocks. In the example we will probably have:
  • The first inode pointer points to a block where the first byte is written.
  • The next 9 inode pointers are null.
  • The next inode pointer points to an index block with 1014 null pointers, followed by a pointer to a data block where only the first byte is defined. The remaining 9 pointers are null.
  • The next inode pointer points to an index block where the first 1023 blocks are null, etc.
  • The next inode pointer is undefined.
• File creation is a time consuming operation. We have to create an inode in the inode list, we have to create an entry in the directory where the file is located and, if the file is non empty, say it has the first byte, we need to allocate and initialize a data block. In general when a file is modified we may have to update directory, inode, index blocks, and data blocks. If these data structure are far apart we may spend a lot of time in seeking operations.
• Directories in Unix are like regular files. The only difference is that they contain file entries. Each file entry has two parts, the name of the file, and the inode number of the file. The latter is used to index into the in disk inode list and to retrieve the inode that describes the file. This inode will be in the in memory inode map while the file is open.

Stable Storage

We consider two disks D1 and D2 that are mirror images (RAID-1) of each other, i.e. they have the same number of equally numbered sectors. Corresponding sectors are intended to have the same content. Here is how we write a value B to a sector s that has currently value A:

 1
    REPEAT
 2      write B to sector s on D1;
 3      read sector s from D1;
 4  UNTIL value read is without error;
 5
    REPEAT
 6      write B to sector s on D2;
 7      read sector s from D2;
 8  UNTIL value read is without error;
 9

We have numbered significant locations in the code. At 1 disks D1 and D2 have the same value A at sector s. At 2, 3, 4, and 5 D2 has value A at s. At 5 D1 has B at s and D2 has A at s. At 6, 7, and 8 D1 at s has value B. Reasoning similarly we see that at 9 we will have value B at s in both D1 and D2. Thus if all goes well we have succeeded in making D1 and D2 mirrors of each other. The problem is when there is a failure at an intermediate point after 1 and before 9. Here is the procedure to follow after a failure.

 10 read sector s from D1;
    if read error then {
      REPEAT
        read value of sector s from D2 and write to sector s on D1;
        read sector s from D1;
      UNTIL value read is without error;
      return;}
 11 read sector s from D2;
    if read error then {
      REPEAT
        read value of sector s from D1 and write to sector s on D2;
        read sector s from D2;
      UNTIL value read is without error;
      return;}
    Compare values read from D1 and D2;
    if different then 
      REPEAT 
        write value read from s on D1 to s on D2;
        read sector s from D2;
      UNTIL value read is without error;

Note that a write operation to stable storage takes (at least) two times the time required for a write to normal storage. This is so since the writes to the two copies must be done serially.

Directly Attached Storage (DAS), Network Attached Storage (NAS), Storage Area Network (SAN)

Storage Area Networks (SAN) and Network Attached Storage (NAS) are intended to remedy the limitations of DAS. A SAN is a separate network of storage nodes dedicated to the storage function, which can be accessed and shared from a variety of computer systems thru special protocols like fiber channel. In a SAN, as in DAS, access to storage is made at the block level. Network Attached Storage is a configuration of storage nodes, seen as a file system and accessed using a high level protocol like NFS. It is implemented using the IP protocol.