Some questions about Reiser4

Some questions about Reiser4

[Fred -- Speed Up --]

[-- Attachment #1: Type: text/plain, Size: 2211 bytes --]

Hi there ;)

I've read the full official documentation about Reiser4 on the Namesys website, but some question still remain unanswerd. I'd like you to help me solving them :

- Firstly the trees. I read that the it (the storage one, not the semantic side) grew on top, which makes the key grow in lenght. But what about fanout ? When a file has been deleted, can its former key be freed and reused so that the tree keeps balanced ? Does Reiser4 otpimize the tree by storing small files together in a part of the tree, or directories, or whatever organisation : when a file is being written, does Reiser4 give it the first key it finds, or does a segragation exist in order to improve performance ? For instance, small temp files are created and deleted numbers of times, does a special part of the tree keep those temp files so that only a little part of the tree is constantly changing ?
- What do you call a 'graph' when speaking about the structure the semantic layer uses to resolve paths ? How does this part really work (it is not formally spcified in the doc) ?
- How about folders : what status do they have ? They may be stored as other files, as they have to keep their own properties, but their information (the folder's files and subfolder list) is being kept in the semantic layer's graph : how do you handle with this ?
- Why do you need to store the locality_id in the key ?
- How do you handle with big files wich do not fit in contiguous bloc space, so they need more than one extended pointer ? How are those other pointers stored ?
- B+Trees are simply BTrees that do not use BLOBs, am I right ?
- Dancing trees are simply Balanced Trees wich are only modified in an event of memory pressure, don't they ?
- How is the developement ? I mean, should we await the Reiser 4.0 release this summer, or do you need some more time ? What features will be included in 4.0 and which will be left for 4.1 ? Will the packer be ready for release as Reiser 4.0 comes out ?

My goal is to provide a french, complete and exact FDL licensed documentation about Reiser4, hopefully before the next month. I'd just like you to help me, I'm sure you'll be able to.


Thank you in advance,

Fred

Re: Some questions about Reiser4

[Yury Umanets]

Fred -- Speed Up -- wrote:

>Hi there ;)
>
Hello,

>
>I've read the full official documentation about Reiser4 on the Namesys website, but some question still remain unanswerd. I'd like you to help me solving them :
>

>
>- Firstly the trees. I read that the it (the storage one, not the semantic side) grew on top, which makes the key grow in lenght. 
>
What do you mean speaking about key growth in length? Key consists of 
three 64bit components and namely the following:

(1) locality -- object id of the parent object (directory). It also 
contains for 4 bits used for key type.
(2) objectid -- object id (inode number) of the object itself.
(3) offset -- offset inside corresponding object.

Key is constant in length.

>But what about fanout ? When a file has been deleted, can its former key be freed and reused so that the tree keeps balanced ? 
>
First of all key cannot be reused in reiser4, because its two first 
components are obtained from one 64bit counter (oid allocator), which is 
incrementing each time when new object id (inode number) is needed.

Then, why do you think, that tree will be balanced, if file's key is 
reused after file is removed? You probably mean, that all places in tree 
removed file lies in may be reserved and later, when new file of the 
same size is ready, we can occupy these reserved places?

This is too difficuly, because between these two moments we need to do a 
lot of job in tree. Also the maintaining that structs for keeping 
reserved places is a job, which should be done and there are a lot of 
another tasks need to performed.

Yet another issue is that, the tree is not balanced well in the 
modifying time. This job (balancing) is deferred for flush time.

>Does Reiser4 otpimize the tree by storing small files together in a part of the tree, or directories,
>
Yes, reiser4 is storing small files in tree itself. Directories lie in 
tree too.

> or whatever organisation : when a file is being written, does Reiser4 give it the first key it finds, or does a segragation exist in order to improve performance ?
>
Before file can be written, it should be created, that is, its stat data 
should be created. In the creation time inode number is attached to file 
and key based on this inode number is assigned to created stat data.

This is example of stat data key. As you can see, its offset (third 
component) is zero and type is 1, that is stat data one.
[65536:1, 65537, 0]

And this one the key of the filebody start.
[65536:4, 65537, 0]

It has the same components, except of type (4) and namely file body.

Yet another example, key of the piece of file starting from 100 bytes 
offset.
[65536:4, 65537, 100]

As you can see, offset is 100 now.

> For instance, small temp files are created and deleted numbers of times, does a special part of the tree keep those temp files so that only a little part of the tree is constantly changing ?
>
Actually changing small number of small files does not lead to big 
chnages in tree immediately. I mean that tree will not be packed or 
something like this in this time. All big changes are deffred to flush 
time.

Flush which is running quite rarely is supposed to do the following actions:

(1) Finds dirty slums and pack them. That is, to take care about nodes 
packing (here may be used few invariants like node half filled, but the 
general rule for now is to pack nodes as much as possible).
(2) Allocate all unallocated yet things. That is to assign the real 
block numbers to internal pointers (index part of tree), formatted nodes 
and extents.
(3) Flushing to disk. This is part is quite complex, because of 
journaling in wandered locations. If you are interested in more detailed 
explanetion, ask Hans, or Zam.

>- What do you call a 'graph' when speaking about the structure the semantic layer uses to resolve paths ? How does this part really work (it is not formally spcified in the doc) ?
>
Ask Hans please :)

>- How about folders : what status do they have ? They may be stored as other files, as they have to keep their own properties, but their information (the folder's files and subfolder list) is being kept in the semantic layer's graph : how do you handle with this ?
>
The directories are almost the same objects like files are. That is they 
of course have stat data with properties strored in it and they have a 
body with list of subdirectories stored in it. The difference is that, 
entries body contains the may be accesed by means of using hash of name 
stored in entry, not the liner offset like generic files do.

Each entry roughly speaking contains the following parts:
(1) hash -- two 64bit values calculated by entry name and supposed to be 
used for searching entry by name.
(2) the key of the stat data of object, entry points to.
(3) optional entry name. As it may be obtained from hash, name is not 
stored in entry sometimes.

Thus, in the time you are performing cd /usr/ reiser4 perform the 
following actions:
(1) Seach for stat data key of the root directory. Opens root directory, 
that is makes serach of directory body, entries lie in it.
(2) Generates hash by name (usr) and makes entry lookup by this hash.
(3) After entry is found, its stat data key is extracted and jump to 
point (1), until whole path is parsed and stat data of the last 
directory/file is found.

Of course, this explanation is not full. It does not include symlinks 
handling and cases like not unique keys.

>- Why do you need to store the locality_id in the key ?
>
That is because we want group together all data belong to particular 
object. For instance, all items file contains them, will be stored 
together and reading the file will not lead to perform a lot of seeks. 
The same for directory.

>- How do you handle with big files wich do not fit in contiguous bloc space, so they need more than one extended pointer ? How are those other pointers stored ?
>
We handle this issue by means of using extents. Big file data consists 
of extents. Each extent consists of array  of extent units (pointers). 
The format of the extent unit is the following:

__u64 start;
__u64 width;

Extents file consists of are allocated on flush.

>- B+Trees are simply BTrees that do not use BLOBs, am I right ?
>
Ask Hans about.

>- Dancing trees are simply Balanced Trees wich are only modified in an event of memory pressure, don't they ?
>
That is because the trees are not balanced until flush carres about it. 
Flush is running on memory pressure or once in particular time interval.

>- How is the developement ? I mean, should we await the Reiser 4.0 release this summer, or do you need some more time ? What features will be included in 4.0 and which will be left for 4.1 ? Will the packer be ready for release as Reiser 4.0 comes out ?
>
I think Hans will answer this.

>
>My goal is to provide a french, complete and exact FDL licensed documentation about Reiser4, hopefully before the next month. I'd just like you to help me, I'm sure you'll be able to.
>
This is good. Are you going to consult with us the contents of that 
documentation?  It would be nice of you.

>
>
>Thank you in advance,
>
>Fred
>  
>


-- 
Yury Umanets

Re: Some questions about Reiser4

[Fred -- Speed Up --]

Now that I know that keys depend on inode numbers, I can understand some
points a far better way., thanks a lot ;)

- But I didn't knew Reiser4 was using inodes, as I thought everything was
stored in the tree ... now, you say Reiser4 stores directories and small
files in the tree, but isn't that kind of blobs Reiser4 would not use ?
- In the official documentation, it is said that blobs have moved out from
Reiser4, is that true ?
- In case of a small file being written to the disk, even if it is kept in
the tree you assign it an inode number ?
- What do you really mean by "flush" : can it be considered as a mantainance
operation that's running from time to time to clean the tree ? I saw that
programs can ask Reiser4 to flush, does flush in this case mean "physically
write data to the disk" ?
- When resolving a path, you still need to physically open directories, this
means searching through the tree : isn't there another data structure
intended to cache path data so that resolving a path operation doesn't
include searching the main tree ? I thought the semantic layer had its own
structure, not directly dependent on the main tree, for performance
concerns.
- There is no case of multiple extents use in the official doc, but as you
explained to me they are commonly used : do you need inodes to store extent
pointers, or are they kept together in the tree ?

Be sure you'll have full regard on the documents I'm publishing about
Reiser4.

Than you again,

Fred

Re: Some questions about Reiser4

[Yury Umanets]

Fred -- Speed Up -- wrote:

>Now that I know that keys depend on inode numbers, I can understand some
>points a far better way., thanks a lot ;)
>
Inode number has the different nature in different filesystems.

>
>- But I didn't knew Reiser4 was using inodes, as I thought everything was
>stored in the tree ... now, you say Reiser4 stores directories and small
>files in the tree, but isn't that kind of blobs Reiser4 would not use ?
>
Hans will answer this in monday.

>- In the official documentation, it is said that blobs have moved out from
>Reiser4, is that true ?
>
And this one.

>- In case of a small file being written to the disk, even if it is kept in
>the tree you assign it an inode number ?
>
Of course. Each file contains of the following:
(1) stat data (inode in VFS notation)
(2) some body (tails, extents, directory items, etc)

If we do not assign inode to small file, how VFS will handle it? And how 
reiser4 will find it in the tree?

>- What do you really mean by "flush" : can it be considered as a mantainance
>operation that's running from time to time to clean the tree ?
>
Yes. In general flush is reiser4 subsystem, supposed to flush slums 
(dirty pieces of tree) to the disk. Of course those slums should be 
served in particular maner (packing, allocation) I have written about it.

> I saw that
>programs can ask Reiser4 to flush, does flush in this case mean "physically
>write data to the disk" ?
>
It does mean and this too.

>- When resolving a path, you still need to physically open directories, this
>means searching through the tree : isn't there another data structure
>intended to cache path data so that resolving a path operation doesn't
>include searching the main tree ?
>
Actually there is so called CBK cache. This is simple mechanism to 
satisfy tree lookups (by a key) without searching though the tree itself.
But it is used not only in path serach time, but also in other cases 
(for instance, for seraching file body item at particular file offset).

> I thought the semantic layer had its own
>structure, not directly dependent on the main tree, for performance
>concerns.
>

>- There is no case of multiple extents use in the official doc, but as you
>explained to me they are commonly used : do you need inodes to store extent
>pointers, or are they kept together in the tree ?
>
I can't comprehend you.

>
>Be sure you'll have full regard on the documents I'm publishing about
>Reiser4.
>
>Than you again,
>
Okay, thanks

>
>Fred
>
>
>
>  
>


-- 
Yury Umanets
"We're flying high, we're watching the world passes by..."

Re: Some questions about Reiser4

[Fred -- Speed Up --]

So, what you call "inodes" within Reiser4 are stat data (last access time,
right, ...) and a way to find the files's data (not directly the physical
adress, but a piece of information determining exactly the file), mainly for
VFS compatibility purposes. Are 'inodes' converted to keys when Reiser4 gets
them from VFS, or do they represent a physical adress on the disk ?

Now I'm going to reformulate the question I asked you about big file storage
:
Big files need more than one extent. But according to the documentation,
there seems to be only one pointer associated to each file. So how can you
point out multiple extents necessary to store big files, using extent
pointers in the tree ?

Be sure I'm awaiting the great Hans and his core dev team ;-)

Fred

Re: Some questions about Reiser4

[Yury Umanets]

Fred -- Speed Up -- wrote:

>So, what you call "inodes" within Reiser4 are stat data (last access time,
>right, ...)
>
Inode is struct in VFS, but in the case of reiser4 it contains also the 
pointer to the loaded reiser4 stat data item. Stat data item contains 
times, mode, nlinks, size, etc.

Each stat data is tag for file. That each file has one stat data. And 
this stat data can be found by its key. Its kay consists of  inode 
number of parent directory,  inode number of file itself and offset 
(zero for stat data).

> and a way to find the files's data (not directly the physical
>adress, but a piece of information determining exactly the file), mainly for
>VFS compatibility purposes. Are 'inodes' converted to keys when Reiser4 gets
>them from VFS, or do they represent a physical adress on the disk ?
>
Inode numbers may be converted to key. And then key is used for 
searching whatever in the tree (stat data, file body, directory entry, etc).
But in the case of seraching file body key must contain also offset 
component installed and namely the offset in file we are want to access.

>
>Now I'm going to reformulate the question I asked you about big file storage
>:
>Big files need more than one extent.
>
Right.

> But according to the documentation,
>there seems to be only one pointer associated to each file. 
>
Each big file can contains not limited number of extent items. Each 
extent item contains extent units. They can be accessed/found by key. 
Each extent unit consists of two fields: start (block number) and width 
(number of blocks). In these range from start to start + width some 
piece of file data is lie. But,  as there is not anough big contiguous 
range on disk (some of blocks are used for diffrent things, like 
bitmaps, leaves, etc), we should use more than one extent items with a 
lot of extent units inside.

>So how can you
>point out multiple extents necessary to store big files, using extent
>pointers in the tree ?
>

>
>Be sure I'm awaiting the great Hans and his core dev team ;-)
>
Actually I'm one of that team. But there are questions Hans can answer 
better than me, because he written that documentation on our web pages. 
It is not the same what is implemented, but it is rather roadmap. And 
I'm trying to explain you the things which are implemebted yet and how 
do thay implemented. But sometimes I can't comprehend your requests :)

>
>Fred
>
>
>
>  
>


-- 
Yury Umanets

Re: Some questions about Reiser4

[Oleg Drokin]

Hello!

On Sat, Apr 26, 2003 at 04:52:25PM +0200, Fred -- Speed Up -- wrote:
> So, what you call "inodes" within Reiser4 are stat data (last access time,
> right, ...) and a way to find the files's data (not directly the physical
> adress, but a piece of information determining exactly the file), mainly for
> VFS compatibility purposes. Are 'inodes' converted to keys when Reiser4 gets
> them from VFS, or do they represent a physical adress on the disk ?

Well, some confusiuon is going on, it seems.
It seems what Yury calls as "inodes" is in fact "object id".
Object id is part of the key. Each item belonging to file/directory/whatever other object
have identical (to other objects belonging to the same object) "object id" part in it's key.
This object id is visible outside of FS as inode number. (but there are no static inode thing
like you see in ext2 for example. The closest object that is similar to inode in the meaning of
ext2fs is "statdata" item. It holds file access modes, size and other stuff. But in fact
it is not necessary that each object should have this "statdata". Also there are no fixed locations
for "statdata"s. Reiser4 sports expandable statdata items that may contain different stuff
based on what kind of files you deal with. E.g. "lightweight" files may not have owner/group/acl stuff
in there (these fields are stored in "unixfile" statdata extension) which might be practical for
single-user systems with only one user.)
This is the same for reiserfs v3 and reiser4. Only in reiserfs v3 we had 32bit (and even less
in 3.5 disk format) wide objectid space and objectids were reusable.
In reiser4 objectid space is 64bits and for now the default setting is not to reuse objectids.

Bye,
    Oleg

Re: Some questions about Reiser4

[Hans Reiser]

Fred -- Speed Up -- wrote:

>Hi there ;)
>
>I've read the full official documentation about Reiser4 on the Namesys website,
>
I recommend reading it again.

> but some question still remain unanswerd. I'd like you to help me solving them :
>
>- Firstly the trees. I read that the it (the storage one, not the semantic side) grew on top, which makes the key grow in lenght.
>
The key is constant in size.

> But what about fanout ? When a file has been deleted, can its former key be freed and reused so that the tree keeps balanced ? Does Reiser4 otpimize the tree by storing small files together in a part of the tree, or directories, or whatever organisation : when a file is being written, does Reiser4 give it the first key it finds, or does a segragation exist in order to improve performance ? For instance, small temp files are created and deleted numbers of times, does a special part of the tree keep those temp files so that only a little part of the tree is constantly changing ?
>
no.

>- What do you call a 'graph' when speaking about the structure the semantic layer uses to resolve paths ? How does this part really work (it is not formally spcified in the doc) ?
>- How about folders : what status do they have ? They may be stored as other files, as they have to keep their own properties, but their information (the folder's files and subfolder list) is being kept in the semantic layer's graph : how do you handle with this ?
>- Why do you need to store the locality_id in the key ?
>
So that objects in the same locality are near each other in their tree 
order.

>- How do you handle with big files wich do not fit in contiguous bloc space, so they need more than one extended pointer ? How are those other pointers stored ?
>
One after another in the extent items.

>- B+Trees are simply BTrees that do not use BLOBs, am I right ?
>
No.  B+trees store only pointers in their internal nodes.  A Btree might 
store data smaller than a node inside one of the internal nodes of the 
tree along with several other data items.  That means it is not a B+tree 
and it is not using a BLOB either.

>- Dancing trees are simply Balanced Trees wich are only modified in an event of memory pressure, don't they ?
>
No.

>- How is the developement ? I mean, should we await the Reiser 4.0 release this summer, or do you need some more time ? What features will be included in 4.0 and which will be left for 4.1 ? Will the packer be ready for release as Reiser 4.0 comes out ?
>
The repacker will be in 4.1.

>
>My goal is to provide a french, complete and exact FDL licensed documentation about Reiser4, hopefully before the next month. I'd just like you to help me, I'm sure you'll be able to.
>
>
>Thank you in advance,
>
>Fred
>  
>


-- 
Hans

Re: Some questions about Reiser4

[Hans Reiser]

Yury Umanets wrote:

> Fred -- Speed Up -- wrote:
>
>> Now that I know that keys depend on inode numbers, I can understand some
>> points a far better way., thanks a lot ;)
>>
> Inode number has the different nature in different filesystems.
>
>>
>> - But I didn't knew Reiser4 was using inodes, as I thought everything 
>> was
>> stored in the tree ... now, you say Reiser4 stores directories and small
>> files in the tree, but isn't that kind of blobs Reiser4 would not use ?
>>
> Hans will answer this in monday.
>
>> - In the official documentation, it is said that blobs have moved out 
>> from
>> Reiser4, is that true ? 
>
Yes.

>>
>>
> And this one.
>
>> - In case of a small file being written to the disk, even if it is 
>> kept in
>> the tree you assign it an inode number ?
>>
> Of course. Each file contains of the following:
> (1) stat data (inode in VFS notation)
> (2) some body (tails, extents, directory items, etc)
>
> If we do not assign inode to small file, how VFS will handle it? And 
> how reiser4 will find it in the tree? 

We assign an objectid.  We do not have inodes.

>
>
>> - What do you really mean by "flush" : can it be considered as a 
>> mantainance
>> operation that's running from time to time to clean the tree ?
>>
> Yes. In general flush is reiser4 subsystem, supposed to flush slums 
> (dirty pieces of tree) to the disk. Of course those slums should be 
> served in particular maner (packing, allocation) I have written about it.
>
>> I saw that
>> programs can ask Reiser4 to flush, does flush in this case mean 
>> "physically
>> write data to the disk" ?
>>
> It does mean and this too.
>
>> - When resolving a path, you still need to physically open 
>> directories, this
>> means searching through the tree : isn't there another data structure
>> intended to cache path data so that resolving a path operation doesn't
>> include searching the main tree ?
>>
> Actually there is so called CBK cache. This is simple mechanism to 
> satisfy tree lookups (by a key) without searching though the tree itself.
> But it is used not only in path serach time, but also in other cases 
> (for instance, for seraching file body item at particular file offset).
>
>> I thought the semantic layer had its own
>> structure, not directly dependent on the main tree, for performance
>> concerns.
>>
>
>> - There is no case of multiple extents use in the official doc, but 
>> as you
>> explained to me they are commonly used : do you need inodes to store 
>> extent
>> pointers,
>
no

>> or are they kept together in the tree ? 
>
yes.

>>
>>
> I can't comprehend you.
>
>>
>> Be sure you'll have full regard on the documents I'm publishing about
>> Reiser4.
>>
>> Than you again,
>>
> Okay, thanks
>
>>
>> Fred
>>
>>
>>
>>  
>>
>
>


-- 
Hans

Re: Some questions about Reiser4

[Hans Reiser]

Fred -- Speed Up -- wrote:

>So, what you call "inodes" within Reiser4 are stat data (last access time,
>right, ...) and a way to find the files's data (not directly the physical
>adress, but a piece of information determining exactly the file), mainly for
>VFS compatibility purposes. Are 'inodes' converted to keys when Reiser4 gets
>them from VFS, or do they represent a physical adress on the disk ?
>
We don't call them inodes, we call them stat data, and stat data are 
stored in the tree where they can be found by their key like everything 
else.

>
>Now I'm going to reformulate the question I asked you about big file storage
>:
>Big files need more than one extent. But according to the documentation,
>there seems to be only one pointer associated to each file. So how can you
>point out multiple extents necessary to store big files, using extent
>pointers in the tree ?
>
>Be sure I'm awaiting the great Hans and his core dev team ;-)
>
>Fred
>
>
>
>  
>


-- 
Hans

Re: Some questions about Reiser4

[Hans Reiser]

Yury Umanets wrote:

> Fred -- Speed Up -- wrote:
>
>> So, what you call "inodes" within Reiser4 are stat data (last access 
>> time,
>> right, ...)
>>
> Inode is struct in VFS, but in the case of reiser4 it contains also 
> the pointer to the loaded reiser4 stat data item. Stat data item 
> contains times, mode, nlinks, size, etc.
>
> Each stat data is tag for file. That each file has one stat data. And 
> this stat data can be found by its key. Its kay consists of  inode 
> number of parent directory,  inode number of file itself and offset 
> (zero for stat data).
>
>> and a way to find the files's data (not directly the physical
>> adress, but a piece of information determining exactly the file), 
>> mainly for
>> VFS compatibility purposes. Are 'inodes' converted to keys when 
>> Reiser4 gets
>> them from VFS, or do they represent a physical adress on the disk ?
>>
> Inode numbers may be converted to key.

No.  Directory objectid plus file objectid which is used as an inode 
number by VFS plus offset can be converted into a tree.  You cannot find 
a file in reiser4 by objectid (inode number) alone.

> And then key is used for searching whatever in the tree (stat data, 
> file body, directory entry, etc).
> But in the case of seraching file body key must contain also offset 
> component installed and namely the offset in file we are want to access.
>
>>
>> Now I'm going to reformulate the question I asked you about big file 
>> storage
>> :
>> Big files need more than one extent.
>>
> Right.
>
>> But according to the documentation,
>> there seems to be only one pointer associated to each file.
>
> Each big file can contains not limited number of extent items. Each 
> extent item contains extent units. They can be accessed/found by key. 
> Each extent unit consists of two fields: start (block number) and 
> width (number of blocks). In these range from start to start + width 
> some piece of file data is lie. But,  as there is not anough big 
> contiguous range on disk (some of blocks are used for diffrent things, 
> like bitmaps, leaves, etc), we should use more than one extent items 
> with a lot of extent units inside.
>
>> So how can you
>> point out multiple extents necessary to store big files, using extent
>> pointers in the tree ?
>>
>
>>
>> Be sure I'm awaiting the great Hans and his core dev team ;-)
>>
> Actually I'm one of that team. But there are questions Hans can answer 
> better than me, because he written that documentation on our web 
> pages. It is not the same what is implemented, but it is rather 
> roadmap. And I'm trying to explain you the things which are 
> implemebted yet and how do thay implemented. But sometimes I can't 
> comprehend your requests :)
>
>>
>> Fred
>>
>>
>>
>>  
>>
>
>


-- 
Hans