Using filename-hash as part of key

Using filename-hash as part of key

[Oleg Drokin]

Hello!

   We had a discussion with Hans on read performance now.
   As everybody probably already knows, reiserfs (v3 and v4) is 
   very sensitive to order in which you write files to it if you
   want to read these files back quick. (actually this issue is the same
   with anything that uses filename hashes to quickly navigate through
   directories). In order to achieve best results you need to write
   files in the same order as hashes of their names would appear in directory.
   We refer to this order as "read optimised" ;)
   Of course writing files in read-optimised order is not always possible,
   so the idea is to use hash of file name as part of the key.
   That would allow us to allocate blocks for files in right order (only
   true for reiesr4 where we have delayed allocation).

   Obvious disadvantages are: larger keys mean more fs overhead,
   this optimisation won't work if file gets renamed later, if this directory
   is never read in sequentional order.

   But as Hans argues, usually these sequentional-read operations are ones most
   noticed because they are usually performed by humans:
   ls, tar, copy of a directory and this kind of stuff.

   Now let's listen to all the different opinions on this plan, your comments
   are welcome.

Bye,
    Oleg

Re: Using filename-hash as part of key

[Anders Widman]

> Hello!

>    We had a discussion with Hans on read performance now.
>    As everybody probably already knows, reiserfs (v3 and v4) is 
>    very sensitive to order in which you write files to it if you
>    want to read these files back quick. (actually this issue is the same
>    with anything that uses filename hashes to quickly navigate through
>    directories). In order to achieve best results you need to write
>    files in the same order as hashes of their names would appear in directory.
>    We refer to this order as "read optimised" ;)
>    Of course writing files in read-optimised order is not always possible,
>    so the idea is to use hash of file name as part of the key.
>    That would allow us to allocate blocks for files in right order (only
>    true for reiesr4 where we have delayed allocation).

>    Obvious disadvantages are: larger keys mean more fs overhead,
>    this optimisation won't work if file gets renamed later, if this directory
>    is never read in sequentional order.

>    But as Hans argues, usually these sequentional-read operations are ones most
>    noticed because they are usually performed by humans:
>    ls, tar, copy of a directory and this kind of stuff.

True..  the  perception  of  performance  is  at least as important as
"real" performance.

If  read-optimized  writes  are  not possible, then maybe a utility to
optimize  the  read/file  listing  performance would be beneficial. It
could either be run as a cron job, or manually.

// Anders

>    Now let's listen to all the different opinions on this plan, your comments
>    are welcome.

> Bye,
>     Oleg

Re: Using filename-hash as part of key

[Nikita Danilov]

Oleg Drokin writes:
 > Hello!
 > 
 >    We had a discussion with Hans on read performance now.
 >    As everybody probably already knows, reiserfs (v3 and v4) is 
 >    very sensitive to order in which you write files to it if you
 >    want to read these files back quick. (actually this issue is the same
 >    with anything that uses filename hashes to quickly navigate through
 >    directories). In order to achieve best results you need to write
 >    files in the same order as hashes of their names would appear in directory.
 >    We refer to this order as "read optimised" ;)
 >    Of course writing files in read-optimised order is not always possible,
 >    so the idea is to use hash of file name as part of the key.

Can you clarify this? Hash of a file name is already used as a part of
directory entry key (and has always been from the earliest versions of
reiserfs, as far as I know).

If you are talking about using hash as part of a key of file *body*
and/or stat-data this also has been discussed many times for reiserfs
v3. I generally think this is easy enough to try without a lot of
discussion, thanks to decision to concentrate all key assignment
decisions in one place (kassign.c). One point: probably we want to embed
into key part of file name rather than hash.

 >    That would allow us to allocate blocks for files in right order (only
 >    true for reiesr4 where we have delayed allocation).
 > 
 >    Obvious disadvantages are: larger keys mean more fs overhead,

If we restrict ourselves to only optimizing layout of stat-data (rather
than file bodies), current key size would suffice, because now offset
field of stat-data's key is unused.

 >    this optimisation won't work if file gets renamed later, if this directory
 >    is never read in sequentional order.
 > 
 >    But as Hans argues, usually these sequentional-read operations are ones most
 >    noticed because they are usually performed by humans:
 >    ls, tar, copy of a directory and this kind of stuff.

Humans are so slow compared to the slowest hard drive that ls is the
least important thing to optimize.

 > 
 >    Now let's listen to all the different opinions on this plan, your comments
 >    are welcome.
 > 
 > Bye,
 >     Oleg

Nikita.

Re: Using filename-hash as part of key

[Oleg Drokin]

Hello!

On Mon, Dec 23, 2002 at 02:52:23PM +0300, Nikita Danilov wrote:
>  >    We refer to this order as "read optimised" ;)
>  >    Of course writing files in read-optimised order is not always possible,
>  >    so the idea is to use hash of file name as part of the key.
> Can you clarify this? Hash of a file name is already used as a part of
> directory entry key (and has always been from the earliest versions of
> reiserfs, as far as I know).

No, I mean to use it as part of key used fir everything including
statdata/filebody

> v3. I generally think this is easy enough to try without a lot of
> discussion, thanks to decision to concentrate all key assignment
> decisions in one place (kassign.c). One point: probably we want to embed
> into key part of file name rather than hash.

That would require us to calculate the hash lots of times instead of doing
this only once, no?
We still do not suport changing of hash on the fly anyway.

>  >    That would allow us to allocate blocks for files in right order (only
>  >    true for reiesr4 where we have delayed allocation).
>  > 
>  >    Obvious disadvantages are: larger keys mean more fs overhead,
> If we restrict ourselves to only optimizing layout of stat-data (rather
> than file bodies), current key size would suffice, because now offset
> field of stat-data's key is unused.

No, I think optimising only statdata is not that useful as optimising
both statdata and file data.

>  >    this optimisation won't work if file gets renamed later, if this directory
>  >    is never read in sequentional order.
>  > 
>  >    But as Hans argues, usually these sequentional-read operations are ones most
>  >    noticed because they are usually performed by humans:
>  >    ls, tar, copy of a directory and this kind of stuff.
> Humans are so slow compared to the slowest hard drive that ls is the
> least important thing to optimize.

This is not true for large directories populated in random order.

Bye,
    Oleg

Re: Using filename-hash as part of key

[Valdis.Kletnieks]

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

On Mon, 23 Dec 2002 14:52:23 +0300, Nikita Danilov said:

>  >    But as Hans argues, usually these sequentional-read operations are ones
 most
>  >    noticed because they are usually performed by humans:
>  >    ls, tar, copy of a directory and this kind of stuff.
> 
> Humans are so slow compared to the slowest hard drive that ls is the
> least important thing to optimize.

Never had a 26-hour daily backup of a large mail spool, have you? ;)

Remember that 'tar' and copy of a directory are things that are likely to
be done as part of a production workload - and if you aren't using tar,
you still need to have *something* that does a stat() on every single file,
even if it's an incremental.

There's also resource contention issues - many systems are up 24x7, and
things like backups and the like have to be done on live filesystems during
off-peak hours.  This means that if "off-peak" is 9PM-6AM, you have *two*
constraints:  (1) the job has to finish in under 9 hours, (2) It has to consume
few enough resources that nothing else bogs down....
-- 
				Valdis Kletnieks
				Computer Systems Senior Engineer
				Virginia Tech


[-- Attachment #2: Type: application/pgp-signature, Size: 226 bytes --]