Re: Transparent compression in the FS

[Edward Shushkin]

> Richard B. Johnson wrote:
> 
> >Then the degenerative case is no compression at all. There is no
> >advantage to writing a block that is 1/N full of compressed data.
> >You end up having to write the whole block anyway.
> >
> >This problem was well developed in the days where RLE (at the hardware
> >level) was used to extend the size of hard disks from their physical
> >size of about 38 megabytes to about 70 megabytes. The minimim size
> >of a read or write is a sector.
> >
> >So, lets's use the minimum compression alogithm, no sliding
> >dictionaries complicating things, just RLE and see.
> >
> >The alogithm is a sentinal byte, a byte representing the number
> >of bytes to expand -1, then the byte to expand. The sentinal byte
> >in RLE was 0xbb. If you needed to read/write a 0xbb, you need
> >to expand that to three bytes, 0xbb, 0x00, 0xbb.
> >                                  |     |     |___ byte to expand
> >                                  |     |________ nr bytes (0 + 1)
> >                                  |______________ sentinal byte
> >
> >All other sequences will reduce the size. So, we have a 512-
> >byte sector full of nulls, what gets written is:
> >        0xbb, 0xff, 0x00, 0xbb, 0xff, 0x00
> >           |     |     |     |     |     |___ byte value
> >           |     |     |     |     |_________ 256 bytes
> >           |     |     |     |_______________ sentinal
> >           |     |     |_____________________ byte value
> >           |     |___________________________ 256 bytes
> >           |_________________________________ sentinal.
> >
> >In this example, we have compressed a 512 byte sector to
> >only 6 bytes. Wonderful! Now we have to write 512 bytes
> >so that effort was wasted. 

Reiser4 packs compressed block so it will be represented by a set
of tails (fragments). This approach allows to keep compression ratio
as maximal as possible.

Edward.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/