baijia - papers and notes

Gal, E. and Toledo, S. 2005. A transactional flash file system for microcontrollers. In Proceedings of the Annual Conference on USENIX Annual Technical Conference (Anaheim, CA, April 10 - 15, 2005).

The paper discusses a transactional file system developed for small-memory systems using NOR flash as the storage media.

To be resilient to the heavy overhead of erase and the wearing of flash blocks, an indirection level is introduced to map logical erase units to physical erase units. By keeping the sector numbers the same in the relevant erase units, it is possible to move data around by copying valid data from an erase unit to another.

The main idea is to use pruned versioned trees to organize various file system data. Logs are used for transactional semantics (e.g., atomicity).

TFFS is designed for NOR flash, which has a nice feature that data can be written in a random access manner. It apparently simplifies the design. Nevertheless, designing a transactional file system on a small-memory system is non-trivial. In quite a few places, special rules or exceptions are introduced to further simplify the design requirements. For example, deletions have limitations.

PDF from the author's web site: http://www.tau.ac.il/~stoledo/Pubs/usenix2005.pdf

@inproceedings{gal05transactional,
author = {Gal, Eran and Toledo, Sivan},
title = {A transactional flash file system for microcontrollers},
booktitle = {ATEC '05: Proceedings of the annual conference on USENIX Annual Technical Conference},
year = {2005},
pages = {7--7},
location = {Anaheim, CA},
publisher = {USENIX Association},
address = {Berkeley, CA, USA},
}

Review:
TFFS is a transactional file system for flash memory devices, being used for system having small memory, such as motes, most of which only have few KB memory.

The main concern when designing a file system for flash memory is the ware out problem. This paper propose to use pruned versioned trees as the data structure.

One problem that has been raised when we were discussing the paper is:
when we have the case,
T1(thread 1): read
T2: write
T3: read
when T2 is not finished, that is the confirm bit is not set, which tree should T3 read? read-only tree or read-write tree?

I think the paper make this problem confusing when it wrote in 4.2 6th paragraph, "If the commit bit is not yet set, then tree access in the read-write version should traverse the spare pointer but tree access in the read-only version should traverse the original pointer"
Then let's see in what case will the tree access the read-write version: "The read-write version represents the state of the tree while processing a transaction and read-only version represents the most-recently committed version."
So I think the first cited sentence cause confusion, since actually when we process a transaction we will only access read-write version.

But I think the later part of this paper has clarify their idea:
in 4.5
"The read-write version of the tree represents the state of the tree at time t, but only if transaction t will commit."
"Hence, the file system allows transactions with TID r, for s< r < t, access to the read-only version of tree and to transaction t access to the read-write version. "

so, I think for the question, read will access the read-write tree