Trees in the Reiser4 Filesystem, Part I
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.
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.
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.
Hans Reiser (firstname.lastname@example.org) 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.
Free Webinar: Linux Backup and Recovery
Most companies incorporate backup procedures for critical data, which can be restored quickly if a loss occurs. However, fewer companies are prepared for catastrophic system failures, in which they lose all data, the entire operating system, applications, settings, patches and more, reducing their system(s) to “bare metal.” After all, before data can be restored to a system, there must be a system to restore it to.
In this one hour webinar, learn how to enhance your existing backup strategies for better disaster recovery preparedness using Storix System Backup Administrator (SBAdmin), a highly flexible bare-metal recovery solution for UNIX and Linux systems.
|Making Linux and Android Get Along (It's Not as Hard as It Sounds)||May 16, 2013|
|Drupal Is a Framework: Why Everyone Needs to Understand This||May 15, 2013|
|Home, My Backup Data Center||May 13, 2013|
|Non-Linux FOSS: Seashore||May 10, 2013|
|Trying to Tame the Tablet||May 08, 2013|
|Dart: a New Web Programming Experience||May 07, 2013|
- RSS Feeds
- Making Linux and Android Get Along (It's Not as Hard as It Sounds)
- New Products
- Drupal Is a Framework: Why Everyone Needs to Understand This
- A Topic for Discussion - Open Source Feature-Richness?
- Home, My Backup Data Center
- Validate an E-Mail Address with PHP, the Right Way
- New Products
- Tech Tip: Really Simple HTTP Server with Python
- Trying to Tame the Tablet
- Agreed on AirDroid. With my
7 min 56 sec ago
- I just learned this
12 min 6 sec ago
42 min 10 sec ago
- not living upto the mobile revolution
3 hours 33 min ago
- Deceptive Advertising and
4 hours 9 min ago
- Let\'s declare that you have
4 hours 9 min ago
- Alterations in Contest Due
4 hours 11 min ago
- At a numbers mindset, your
4 hours 12 min ago
- Do not get Just Almost any
4 hours 15 min ago
- A fantastic rule-of-thumb to
4 hours 17 min ago