Inside NTFS: File Recovery Algorithm
Read about data recovery procedure for NTFS disks and the algorithm used by file recovery apps. Now when we covered most of the theory, we can proceed to actually recovering files. As you may remember from our previous article, FAT was never designed with data recovery in mind. As a result, FAT was very inconvenient to work with when it came to recovering lost information.
Compared FAT, the NTFS is a nearly perfect file system to recover lost data. After all, it was designed to be robust, and has built-in data recovery and corruption protection mechanisms. Clearly, its designers thought of many things that never occurred to the developers of the earlier file systems. As a result, NTFS permits a data recovery tool to identify and recover all sectors that were occupied by a given file. The only (slight) drawback of NTFS is its tendency to lose the names of deleted files, which, to be fair, only happens under certain circumstances.
Let’s have a look at what happens when Windows deletes a file from an NTFS volume (as opposed to recovering information from damaged volumes with corrupted file systems). Recovering a file deleted from an NTFS volume is simpler than undeleting one in most other file systems. For example, if you were using FAT, the chain of file allocation pointers identifying clusters occupied by the file would be lost when the file was deleted. This does not happen in NTFS.
When deleting a file from HDD or USB disk, memory card CompactFlash, MicroSd, its name is excluded from the parent directory index; the corresponding MFT record as well as all the clusters occupied by that file are released. The index is rearranged, at which time information about the name of the file may be lost. As a result, the deleted file will no longer appear in its containing directory.
However, this small drawback is compensated by that fact that MFT stores all records in a single table. As a result, it becomes much easier to locate available records. Each record contains an attribute containing the base address of the parent catalog. This in turn means that, after locating an empty record, we can determine the record’s full path.
In order to recover files deleted from an NTFS volume, one must scan the MFT looking for empty (available) records. If an empty record is located, one may be able to determine the file name, which is stored in one of the attributes. As you remember, determining file names is not always possible. However, unlike in the case of FAT volumes, all pointers to clusters occupied by that file will still exist. This means we can recover files of any size, even if severely fragmented – of course if its clusters have not been claimed by other files.
As you may remember, some very small files can be stored in the MFT as attributes. These files are called resident files. If a resident file occupied a single MFT record, it can be recovered until the MFT record is re-allocated.
NTFS has a special algorithm for allocating MFT records. When allocating an MFT record, Windows will attempt to make use of the first available record based on its number. As a result, records with lower MFT record numbers are allocated more often than those with higher record numbers.
Transaction log is an essential feature of NTFS. NTFS transaction log records information about write operations into a special file. NTFS transaction log is not always active; however, it contains information about file delete and last editing time.
NTFS is a self-repairing file system. Transaction log is one of the tools allowing the system to rollback changes that led to file system corruption. More often than not, the file system gets damaged during a write operation, for example, if there is a power outage or a system failure at the time the system writes something onto the disk. If the system detects an improper shutdown, or if the “dirty” flag is set during the reboot, Windows analyzes NTFS transaction log. The transaction log contains information about upcoming updates to meta data, and register these updates once they are successfully committed.
So what happens if there is a failure during a write operation? In this case, Windows analyzes the transaction log and rolls back the state of the file system to prior condition. NTFS transaction log does not contain non-resident user data. However, it does contain all resident attributes in order to enable the rollback. As a result, the transaction log cannot be used to recover larger files.
Essentially, the use of the transaction log to recover files it limited. The log makes much more sense when recovering the integrity of the file system by rolling back non-committed changes, which causes the loss of last written data. As a result, Hetman Partition Recovery does not use NTFS transaction log.