Re: Linux page cache issue?

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



You are right. If the device is very big, the radix tree could be huge
as well. Maybe the lookup it not that cheap. But the per-device tree
can be optimized too. A simple way I can immediately image is: evenly
split a device into N parts by the sector numbers. For each part, we
maintain a radix tree. Let's do a math. Suppose I have a 32G partition
(2^35 bytes) and each data block is 4K bytes (2^12).  So the partition
has 2^23 blocks. I divide the blocks into 1024 (2^12) groups. Each
group will only have 2^11 blocks. With radix tree, the average lookup
overhead for each tree would be log(2^11) steps. That is 11 in-memory
tree traverse to locate a page. This cost seems to be acceptable. I
don't really measure it though. As to the memory used for maintain the
radix trees, I believe it is trivial considering the memory size of
modern computers.

Xin

On 3/28/07, John Anthony Kazos Jr. <jakj@xxxxxxxxxxx> wrote:
> The lookup of the per-device radix tree may incur some overhead. But
> compared to the slow disk access, looking up an in-memory radix tree is
> much cheaper and should be trivial, I guess.

I would consider whether or not it really is trivial. You'd have to think
hard about just how much of your filesystem is going to be sharing data
blocks. If you fail to find in the per-file tree, then fail to find in the
per-device tree, then still have to read the block from the device, and
this is happening too often, then the additional overhead of the
per-device tree check for non-cached items may end up cancelling the
savings for cached items.

-
To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html

[Index of Archives]     [Linux Ext4 Filesystem]     [Union Filesystem]     [Filesystem Testing]     [Ceph Users]     [Ecryptfs]     [AutoFS]     [Kernel Newbies]     [Share Photos]     [Security]     [Netfilter]     [Bugtraq]     [Yosemite News]     [MIPS Linux]     [ARM Linux]     [Linux Security]     [Linux Cachefs]     [Reiser Filesystem]     [Linux RAID]     [Samba]     [Device Mapper]     [CEPH Development]
  Powered by Linux