Home ›

Trees in the Reiser4 Filesystem, Part I

Issue 104

From Issue #104
December 2002

Dec 01, 2002  By Hans Reiser
 in
The basic structure of the new ReiserFS—graphs vs. trees, keys, nodes and blocks.
Types of Items

Reiser4 includes many different kinds of items designed to hold different types of information:

  • static_stat_data: holds the owner, permissions, last access time, creation time, last modification time, size and the number of links (names) to the file.

  • cmpnd_dir_item: holds directory entries and the keys of the files they link to.

  • extent pointers: explained above.

  • node pointers: explained above.

  • bodies: hold parts of files not large enough to be stored in unfleaves.

Units

We call a unit that which we must place as a whole into an item, without splitting it across multiple items. When traversing an item's contents, it is often convenient to do so in units:

  • For body items the units are bytes.

  • For directory items the units are directory entries. The directory entries contain a name and a key of the file named (in practice the name and key may be compressed).

  • For extent items the units are extents. Extent items contain only extents from the same file.

  • For static_stat_data the whole stat data item is one indivisible unit of fixed size.

Figure 5. What Node Formats Look Like

Conclusion

I have explained the basic structures of the Reiser4 tree, but the fun stuff is yet to come. I have not yet explained how other researchers structure their trees. Nor did you learn why object contents are stored at the bottom of the tree, why high fanout is important or what are the different kinds of balancing. No hint have I yet given as to why balanced trees are better and dancing trees are best. What I have most especially not done is explain how a subtle and controversial tree structure change, which you can see in the trees depicted in this article, doubled Reiser4 read speed compared to Reiser3. This will (space permitting) be in Part II in next month's issue of Linux Journal.

Resources

Hans Reiser (reiser@namesys.com) entered UC Berkeley in 1979 after completing the eigth grade and majored in “Systematizing”, an individual major based on the study of how theoretical models are developed. His senior thesis discussed how the philosophy of the hard sciences differs from that of computer science, with the development of a naming system as a case study. He is still implementing that naming system, of which Reiser4 is the storage layer. In 1993 he went to Russia and hired a team of programmers to develop ReiserFS. He worked full-time to pay their salaries while spending nights and weekends arguing over algorithms. In 1999 it began to work well enough that his mother stopped suggesting a salaried job at a nice big company.

______________________

Webcast
More Resources
How to Build an Optimal Hadoop Cluster to Store and Maintain Unlimited Amounts of Data Using Microservers

Realizing the promise of Apache® Hadoop® requires the effective deployment of compute, memory, storage and networking to achieve optimal results. With its flexibility and multitude of options, it is easy to over or under provision the server infrastructure, resulting in poor performance and high TCO. Join us for an in depth, technical discussion with industry experts from leading Hadoop and server companies who will provide insights into the key considerations for designing and deploying an optimal Hadoop cluster.

Learn More

Sponsored by AMD

White Paper
More Resources
Red Hat White Paper: Using an Open Source Framework to Catch the Bad Guy

Built-in forensics, incident response, and security with Red Hat Enterprise Linux 6

Every security policy provides guidance and requirements for ensuring adequate protection of information and data, as well as high-level technical and administrative security requirements for a system in a given environment. Traditionally, providing security for a system focuses on the confidentiality of the information on it. However, protecting the data integrity and system and data availability is just as important. For example, when processing United States intelligence information, there are three attributes that require protection: confidentiality, integrity, and availability.

Learn more about catching the bad guy in this free white paper.

Learn More

Sponsored by DLT Solutions