zfs discuss - Jul 2007 - ZFS Compression algorithms - Project Proposal

Bellow, follows a proposal for a new opensolaris project. Of course,
this is open to change since I just wrote down some ideas I had months
ago, while researching the topic as a graduate student in Computer
Science, and since I''m not an opensolaris/ZFS expert at all. I would
really appreciate any suggestion or comments.

PROJECT PROPOSAL: ZFS Compression Algorithms.

The main purpose of this project is the development of new
compression schemes for the ZFS file system. We plan to start with
the development of a fast implementation of a Burrows Wheeler
Transform based algorithm (BWT). BWT is an outstanding tool
and the currently known lossless compression algorithms
based on it outperform the compression ratio of algorithms derived from the well
known Ziv-Lempel algorithm, while being a little more time and space
expensive. Therefore, there is space for improvement: recent results
show that the running time and space needs of such algorithms can be
significantly reduced and the same results suggests that BWT is
likely to become the new standard in compression
algorithms[1]. Suffixes Sorting (i.e. the problem of sorting suffixes of a
given string) is the main bottleneck of BWT and really significant
progress has been made in this area since the first algorithms of
Manbers and Myers[2] and Larsson and Sadakane[3], notably the new
linear time algorithms of Karkkainen and Sanders[4]; Kim, Sim and
Park[5] and Ko e aluru[6] and also the promising O(nlogn) algorithm of
Karkkainen and Burkhardt[7].

As a conjecture, we believe that some intrinsic properties of ZFS and
file systems in general (e.g. sparseness and data entropy in blocks)
could be exploited in order to produce brand new and really efficient
compression algorithms, as well as the adaptation of existing ones to
the task. The study might be extended to the analysis of data in
specific applications (e.g. web servers, mail servers and others) in
order to develop compression schemes for specific environments and/or
modify the existing Ziv-Lempel based scheme to deal better with such
environments.

[1] "The Burrows-Wheeler Transform: Theory and Practice". Manzini,
Giovanni. Proc. 24th Int. Symposium on Mathematical Foundations of
Computer Science

[2] "Suffix Arrays: A New Method for
On-Line String Searches". Manber, Udi and Myers, Eugene W..  SIAM
Journal on Computing, Vol. 22 Issue 5. 1990

[3] "Faster suffix sorting". Larsson, N Jasper and Sadakane,
Kunihiko. TECHREPORT, Department of Computer Science, Lund University,
1999

[4] "Simple Linear Work Suffix Array Construction". Karkkainen, Juha
and Sanders,Peter. Proc. 13th International Conference on Automata,
Languages and Programming, 2003

[5]"Linear-time construction of suffix arrays" D.K. Kim, J.S. Sim,
H. Park, K. Park, CPM, LNCS, Vol. 2676, 2003

[6]"Space ecient linear time construction of sux arrays",P. Ko and
S. Aluru, CPM 2003.

[7]"Fast Lightweight Suffix Array Construction and
Checking". Burkhardt, Stefan and K?rkk?inen, Juha. 14th Annual
Symposium, CPM 2003,


Domingos Soares Neto
University of Sao Paulo
Institute of Mathematics and Statistics

This is a great idea. I''d like to add a couple of suggestions:

It might be interesting to focus on compression algorithms which are
optimized for particular workloads and data types, an Oracle database for
example.

It might be worthwhile to have some sort of adaptive compression whereby
ZFS could choose a compression algorithm based on its detection of the
type of data being stored.

Adam

On Thu, Jul 05, 2007 at 08:29:38PM -0300, Domingos Soares
wrote:
> Bellow, follows a proposal for a new opensolaris project. Of course,
> this is open to change since I just wrote down some ideas I had months
> ago, while researching the topic as a graduate student in Computer
> Science, and since I''m not an opensolaris/ZFS expert at all. I
would
> really appreciate any suggestion or comments.
> 
> PROJECT PROPOSAL: ZFS Compression Algorithms.
> 
> The main purpose of this project is the development of new
> compression schemes for the ZFS file system. We plan to start with
> the development of a fast implementation of a Burrows Wheeler
> Transform based algorithm (BWT). BWT is an outstanding tool
> and the currently known lossless compression algorithms
> based on it outperform the compression ratio of algorithms derived from the
well
> known Ziv-Lempel algorithm, while being a little more time and space
> expensive. Therefore, there is space for improvement: recent results
> show that the running time and space needs of such algorithms can be
> significantly reduced and the same results suggests that BWT is
> likely to become the new standard in compression
> algorithms[1]. Suffixes Sorting (i.e. the problem of sorting suffixes of a
> given string) is the main bottleneck of BWT and really significant
> progress has been made in this area since the first algorithms of
> Manbers and Myers[2] and Larsson and Sadakane[3], notably the new
> linear time algorithms of Karkkainen and Sanders[4]; Kim, Sim and
> Park[5] and Ko e aluru[6] and also the promising O(nlogn) algorithm of
> Karkkainen and Burkhardt[7].
> 
> As a conjecture, we believe that some intrinsic properties of ZFS and
> file systems in general (e.g. sparseness and data entropy in blocks)
> could be exploited in order to produce brand new and really efficient
> compression algorithms, as well as the adaptation of existing ones to
> the task. The study might be extended to the analysis of data in
> specific applications (e.g. web servers, mail servers and others) in
> order to develop compression schemes for specific environments and/or
> modify the existing Ziv-Lempel based scheme to deal better with such
> environments.
> 
> [1] "The Burrows-Wheeler Transform: Theory and Practice".
Manzini,
> Giovanni. Proc. 24th Int. Symposium on Mathematical Foundations of
> Computer Science
> 
> [2] "Suffix Arrays: A New Method for
> On-Line String Searches". Manber, Udi and Myers, Eugene W..  SIAM
> Journal on Computing, Vol. 22 Issue 5. 1990
> 
> [3] "Faster suffix sorting". Larsson, N Jasper and Sadakane,
> Kunihiko. TECHREPORT, Department of Computer Science, Lund University,
> 1999
> 
> [4] "Simple Linear Work Suffix Array Construction". Karkkainen,
Juha
> and Sanders,Peter. Proc. 13th International Conference on Automata,
> Languages and Programming, 2003
> 
> [5]"Linear-time construction of suffix arrays" D.K. Kim, J.S.
Sim,
> H. Park, K. Park, CPM, LNCS, Vol. 2676, 2003
> 
> [6]"Space ecient linear time construction of sux arrays",P. Ko
and
> S. Aluru, CPM 2003.
> 
> [7]"Fast Lightweight Suffix Array Construction and
> Checking". Burkhardt, Stefan and K?rkk?inen, Juha. 14th Annual
> Symposium, CPM 2003,
> 
> 
> Domingos Soares Neto
> University of Sao Paulo
> Institute of Mathematics and Statistics
> _______________________________________________
> zfs-discuss mailing list
> zfs-discuss at opensolaris.org
> http://mail.opensolaris.org/mailman/listinfo/zfs-discuss
-- 
Adam Leventhal, Solaris Kernel Development       http://blogs.sun.com/ahl

nice idea! :)
>We plan to start with the development of a fast implementation of a Burrows 
>Wheeler Transform based algorithm (BWT).
why not starting with lzo first - it`s already in zfs-fuse on linux and it
looks, that it`s just "in between lzjb and gzip" in terms of
performance and compression ratio.
there needs yet to be demonstrated that it behaves similar on solaris.

see http://www.opensolaris.org/jive/thread.jspa?messageID=111031
 
 
This message posted from opensolaris.org

Awesome initiative.  

One thing ZFS is missing is the ability to select which files to compress.  Even
a simple heuristic like "don''t compress mp3,avi,zip,tar
files" would yield a tremendous change in which data is compressed on
consumer computers.  I don''t know if such a heuristic is planned or
not, but if it is, it might affect the data selection you use for testing your
ideas.
 
 
This message posted from opensolaris.org

>One thing ZFS is missing is the ability to select which files to compress.
yes.

there is also no filesystem based approach in compressing/decompressing a whole
filesystem. you can have 499gb of data on a 500gb partition - and if you need
some more space you would think turning on compression on that fs would solve
your problem. but compression only affects files which are new. i wished there
was some zfs set compression=gzip <zfs> , zfs compress <fs>, zfs
uncompress <fs> and it would be nice if we could get compresion
information for single files. (as with ntfs)
>Even a simple heuristic like "don''t compress mp3,avi,zip,tar
files"
that`s already existing. afaik, zfs tries to compress a datablock and if that
isn`t compressible enough, it doesn`t store it compressed. it has no
"knowlegde" of what type of data a file contains, tough.
 
 
This message posted from opensolaris.org

> zfs tries to compress a datablock and if that isn`t compressible enough, it
doesn`t store it compressed.
That feature was pointed out to me off-list, and it makes great sense.  I had
not heard about that before this thread.
 
 
This message posted from opensolaris.org

"roland" <devzero at web.de> wrote:
> > there is also no filesystem based approach in
compressing/decompressing a whole filesystem. you can have 499gb of data on a
500gb partition - and if you need some more space you would think turning on
compression on that fs would solve your problem. but compression only affects
files which are new. i wished there was some zfs set compression=gzip
<zfs> , zfs compress <fs>, zfs uncompress <fs> and it would be
nice if we could get compresion information for single files. (as with ntfs)
 
one could kludge this by setting the compression parameters desired on the tree
then using a perl script to walk the tree, copying each file to a tmp file,
renaming the original to an arbitrary name, renaming the tmp to the name of the
original, then updating the new file with the original file''s metadata,
do a checksum sanity check, then delete the uncompressed original.
 
-=dave
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.opensolaris.org/pipermail/zfs-discuss/attachments/20070708/4b8815cb/attachment.html>

Dave Johnson wrote:
> "roland" <devzero at web.de <mailto:devzero at
web.de>> wrote:
>  >
>  > there is also no filesystem based approach in 
> compressing/decompressing a whole filesystem. you can have 499gb of data 
> on a 500gb partition - and if you need some more space you would think 
> turning on compression on that fs would solve your problem. but 
> compression only affects files which are new. i wished there was some 
> zfs set compression=gzip <zfs> , zfs compress <fs>, zfs
uncompress <fs>
> and it would be nice if we could get compresion information for single 
> files. (as with ntfs)
>  
> one could kludge this by setting the compression parameters desired on 
> the tree then using a perl script to walk the tree, copying each file to 
> a tmp file, renaming the original to an arbitrary name, renaming the tmp 
> to the name of the original, then updating the new file with the 
> original file''s metadata, do a checksum sanity check, then delete
the
> uncompressed original.
This solution has been proposed several times on this forum.
It is simpler to use an archiving or copying tool (tar, cpio, pax,
star, cp, rsync, rdist, install, zfs send/receive et.al.) to copy
the tree once, then rename the top directory.  It makes no sense to
me to write a copying tool in perl or shell.  KISS :-)
  -- richard

Hi,
> It might be interesting to focus on compression algorithms which are
> optimized for particular workloads and data types, an Oracle database for
> example.
Yes, I agree. That is what I meant when I said "The study might be
extended to the analysis of data in specific applications (e.g. web
servers, mail servers and others) in order to develop compression
schemes for specific environments...". However, I was not considering
it as a major task, but a minor one. How important such a feature
would be to opensolaris?

> It might be worthwhile to have some sort of adaptive compression whereby
> ZFS could choose a compression algorithm based on its detection of the
> type of data being stored.

  That''s definitely a great idea. I''m just afraid that would
be a bit
hard to identify the data type of a given block or set of blocks in
order to adapt the compression algorithm to it. At the file level it
would be pretty easy in most cases, but at the block level we don''t
have a clue about what kind of data are inside the block. The
identification process would depend on some statistical properties of
the data and I don''t know how hard it would be to scan the blocks and
process them on a reasonable amount of time, and the whole thing must
be done before the compression really starts.
 Therefore, prior to the development of an adaptative scheme, it''s
very important to know if such a thing would be worthwhile. In other
words, we need to know the relative variation of the block''s
compression ratio while compressed by different algorithms: is it true
that block B1 can be significantly better compressed by algorithm X
than by algorithm Y, while the inverse happens with block B2? It makes
sense, but I wouldn''t say it''s true before a deeper analysis
and some
experiments.
 Summarizing, I think the idea of an adaptative scheme very nice and
interesting. :-)

Domingos.

--
Domingos Soares Neto
University of Sao Paulo
Institute of Mathematics and Statistics







> Adam
>
> On Thu, Jul 05, 2007 at 08:29:38PM -0300, Domingos Soares wrote:
> > Bellow, follows a proposal for a new opensolaris project. Of course,
> > this is open to change since I just wrote down some ideas I had months
> > ago, while researching the topic as a graduate student in Computer
> > Science, and since I''m not an opensolaris/ZFS expert at all.
I would
> > really appreciate any suggestion or comments.
> >
> > PROJECT PROPOSAL: ZFS Compression Algorithms.
> >
> > The main purpose of this project is the development of new
> > compression schemes for the ZFS file system. We plan to start with
> > the development of a fast implementation of a Burrows Wheeler
> > Transform based algorithm (BWT). BWT is an outstanding tool
> > and the currently known lossless compression algorithms
> > based on it outperform the compression ratio of algorithms derived
from the well
> > known Ziv-Lempel algorithm, while being a little more time and space
> > expensive. Therefore, there is space for improvement: recent results
> > show that the running time and space needs of such algorithms can be
> > significantly reduced and the same results suggests that BWT is
> > likely to become the new standard in compression
> > algorithms[1]. Suffixes Sorting (i.e. the problem of sorting suffixes
of a
> > given string) is the main bottleneck of BWT and really significant
> > progress has been made in this area since the first algorithms of
> > Manbers and Myers[2] and Larsson and Sadakane[3], notably the new
> > linear time algorithms of Karkkainen and Sanders[4]; Kim, Sim and
> > Park[5] and Ko e aluru[6] and also the promising O(nlogn) algorithm of
> > Karkkainen and Burkhardt[7].
> >
> > As a conjecture, we believe that some intrinsic properties of ZFS and
> > file systems in general (e.g. sparseness and data entropy in blocks)
> > could be exploited in order to produce brand new and really efficient
> > compression algorithms, as well as the adaptation of existing ones to
> > the task. The study might be extended to the analysis of data in
> > specific applications (e.g. web servers, mail servers and others) in
> > order to develop compression schemes for specific environments and/or
> > modify the existing Ziv-Lempel based scheme to deal better with such
> > environments.
> >
> > [1] "The Burrows-Wheeler Transform: Theory and Practice".
Manzini,
> > Giovanni. Proc. 24th Int. Symposium on Mathematical Foundations of
> > Computer Science
> >
> > [2] "Suffix Arrays: A New Method for
> > On-Line String Searches". Manber, Udi and Myers, Eugene W..  SIAM
> > Journal on Computing, Vol. 22 Issue 5. 1990
> >
> > [3] "Faster suffix sorting". Larsson, N Jasper and Sadakane,
> > Kunihiko. TECHREPORT, Department of Computer Science, Lund University,
> > 1999
> >
> > [4] "Simple Linear Work Suffix Array Construction".
Karkkainen, Juha
> > and Sanders,Peter. Proc. 13th International Conference on Automata,
> > Languages and Programming, 2003
> >
> > [5]"Linear-time construction of suffix arrays" D.K. Kim,
J.S. Sim,
> > H. Park, K. Park, CPM, LNCS, Vol. 2676, 2003
> >
> > [6]"Space ecient linear time construction of sux arrays",P.
Ko and
> > S. Aluru, CPM 2003.
> >
> > [7]"Fast Lightweight Suffix Array Construction and
> > Checking". Burkhardt, Stefan and K?rkk?inen, Juha. 14th Annual
> > Symposium, CPM 2003,
> >
> >
> > Domingos Soares Neto
> > University of Sao Paulo
> > Institute of Mathematics and Statistics
> > _______________________________________________
> > zfs-discuss mailing list
> > zfs-discuss at opensolaris.org
> > http://mail.opensolaris.org/mailman/listinfo/zfs-discuss
>
> --
> Adam Leventhal, Solaris Kernel Development       http://blogs.sun.com/ahl
>

Hi,
> why not starting with lzo first - it`s already in zfs-fuse on linux and it
looks, that it`s just "in between lzjb and gzip" in terms of
performance and compression ratio.
> there needs yet to be demonstrated that it behaves similar on solaris.
Good question and I''m afraid I don''t have a good answer to it.
:-)
I chose to start by BWT for three reasons:

1) I have been researching suffix arrays and suffix trees for my MSc
thesis on information retrieval algorithms, so I''m familiar with
suffixes sorting and BWT, and maybe I gonna do my PhD on the subject;

2) lzo is copyrighted, so it''s not clear if it can be used on ZFS;

3) lzo is just another implementation of Ziv-Lempel while BWT is a
completely different approach. Why not try it?

Domingos.
--
Domingos Soares Neto
University of Sao Paulo
Institute of Mathematics and Statistics






>
> see http://www.opensolaris.org/jive/thread.jspa?messageID=111031
>
>
> This message posted from opensolaris.org
> _______________________________________________
> zfs-discuss mailing list
> zfs-discuss at opensolaris.org
> http://mail.opensolaris.org/mailman/listinfo/zfs-discuss
>

On Jul 9 2007, Domingos Soares wrote:
>Hi,
>
>> It might be interesting to focus on compression algorithms which are
>> optimized for particular workloads and data types, an Oracle database
for
>> example.
>
>Yes, I agree. That is what I meant when I said "The study might be
>extended to the analysis of data in specific applications (e.g. web
>servers, mail servers and others) in order to develop compression
>schemes for specific environments...". However, I was not considering
>it as a major task, but a minor one. How important such a feature
>would be to opensolaris?
Some specific cases where you could find extra compression would be:
-differencing multiple versions of documents (doc/xls/html) (this type of 
delta compression is currently possible using SmartVersion from 
http://www.smartversion.com/ I haven''t seen delta compression in other 
non-backup related compression tools; as I understand it, ZFS snapshots are 
filesystem-wide deltas)

-media types known to be further recompressible: some older AVI and 
QuickTime video actually compress quick well using ZIP or RAR. The RAR 
format itself has a multimedia compression option to enable algorithms that 
work better on multimedia content.
>> It might be worthwhile to have some sort of adaptive compression
whereby
>> ZFS could choose a compression algorithm based on its detection of the
>> type of data being stored.
>
>  That''s definitely a great idea. I''m just afraid that
would be a bit
>hard to identify the data type of a given block or set of blocks in
>order to adapt the compression algorithm to it. At the file level it
>would be pretty easy in most cases, but at the block level we don''t
>have a clue about what kind of data are inside the block. The
>identification process would depend on some statistical properties of
>the data and I don''t know how hard it would be to scan the blocks
and
>process them on a reasonable amount of time, and the whole thing must
>be done before the compression really starts.
Wouldn''t ZFS''s being an integrated filesystem make it easier
for it to
identify the file types vs. a standard block device with a filesystem 
overlaid upon it?

I read in another post that with compression enabled, ZFS attempts to 
compress the data and stores it compressed if it compresses enough. As far 
as identifying the file type/data type how about:
1.) ZFS block compression system reads the ZFS file table to identify which 
blocks are the beginning of files (or for new writes, the block compression 
system is notified that file.ext is being written on block #### (e.g. block 
9,000,201).
2.) ZFS block compression system reads block ####, identifies the file type 
probably based on the file header and applies the most appropriate 
compression format, or if none found, the default

An approach for maximal compression:
The algorithm selection could be
1.) attempt to compress using BWT, store compressed if BWT works better 
than no compression
2.) when CPU is otherwise idle, use 10% of spare cpu cycles to "walk the 
disk", trying to recompress each block with each of the various supported 
compression algorithms, ultimately storing that block in the most space 
efficient compression format.

This technique would result in a file system that tends to compact its data 
ever more tightly as the data sits in it. It could be compared to 
''settling'' flakes in a cereal box...the contents may have had
a lot of ''air
space'' before shipment, but are now ''compressed''. The
recompression step
might even be part of a period disk scrubbing step meant to check and 
recheck previously written data to make sure the sector it is sitting on 
isn''t going bad.

An aging (2002) but thorough comparison of many archivers/algorithms is 
Jeff Gilchrist''s Archive Comparison Test: http://compression.ca/ 
http://compression.ca/act/act-win.html

> Wouldn''t ZFS''s being an integrated filesystem make it
easier for it to
> identify the file types vs. a standard block device with a filesystem 
> overlaid upon it?
I''m not sure.  I would think that most applications are going to use
the
POSIX layer where there''s no separate API for filetypes.  Every file is
"just" a bytestream.  I don''t see that ZFS gives you any more
information about a file''s purpose or use.
> I read in another post that with compression enabled, ZFS attempts to 
> compress the data and stores it compressed if it compresses enough. As far 
> as identifying the file type/data type how about:
> 1.) ZFS block compression system reads the ZFS file table to identify which
> blocks are the beginning of files (or for new writes, the block compression
> system is notified that file.ext is being written on block #### (e.g. block
> 9,000,201).
While it is "block" compression, it is filesystem blocks, not disk
blocks.
 
> An approach for maximal compression:
> The algorithm selection could be
> 1.) attempt to compress using BWT, store compressed if BWT works better 
> than no compression
> 2.) when CPU is otherwise idle, use 10% of spare cpu cycles to "walk
the
> disk", trying to recompress each block with each of the various
supported
> compression algorithms, ultimately storing that block in the most space 
> efficient compression format.
It would be interesting to determine how this could fit in with
snapshots.  From one point of view this is the same data, just
compressed differently.  So you might want the old snapshots to point to
it.  From another point of view this data has changed, so the snapshots
should point to only the original form of the data.

Would this be worthwhile even if you had to allocate more space because
it could not be shared by older snapshots?


-- 
Darren Dunham                                           ddunham at taos.com
Senior Technical Consultant         TAOS            http://www.taos.com/
Got some Dr Pepper?                           San Francisco, CA bay area
         < This line left intentionally blank to confuse you. >

On Mon, Jul 09, 2007 at 05:27:44PM -0500, Haudy Kazemi
wrote:
> Wouldn''t ZFS''s being an integrated filesystem make it
easier for it to
> identify the file types vs. a standard block device with a filesystem 
> overlaid upon it?
How?  The API to ZFS that most everything uses is the POSIX API.
There''s no MIME type argument to creat(2).
> I read in another post that with compression enabled, ZFS attempts to 
> compress the data and stores it compressed if it compresses enough. As far 
> as identifying the file type/data type how about:
> 1.) ZFS block compression system reads the ZFS file table to identify which
> blocks are the beginning of files (or for new writes, the block compression
> system is notified that file.ext is being written on block #### (e.g. block
> 9,000,201).
You might as well cache this in the dnode to keep the number of reads
needed to re-discover this info to a minimum.
> 2.) ZFS block compression system reads block ####, identifies the file type
> probably based on the file header and applies the most appropriate 
> compression format, or if none found, the default
Like an in-kernel file(1).  That could work, but that seems like a lot
of work.

You might as well try all compression algorithms available, pick the
best one the first time that one of them works for any given file block
being written, and record this in the file''s dnode so that for
subsequent writes only that compression algorithm is used.  (Of course,
the compression algorithm selection process could be more dynamic than
that.)
> An approach for maximal compression:
> The algorithm selection could be
> 1.) attempt to compress using BWT, store compressed if BWT works better 
> than no compression
> 2.) when CPU is otherwise idle, use 10% of spare cpu cycles to "walk
the
> disk", trying to recompress each block with each of the various
supported
> compression algorithms, ultimately storing that block in the most space 
> efficient compression format.
Sure, that''s a lazy (in the sense of doing the work in the background
when there''s enough cycles) approach to compression *and* compression
algorithm selection.
> This technique would result in a file system that tends to compact its data
> ever more tightly as the data sits in it. It could be compared to 
> ''settling'' flakes in a cereal box...the contents may have
had a lot of ''air
> space'' before shipment, but are now
''compressed''. The recompression step
> might even be part of a period disk scrubbing step meant to check and 
> recheck previously written data to make sure the sector it is sitting on 
> isn''t going bad.
Re-compressing (re-encrypting, etc...) as part of a "filesystem scrub"
(as opposed to volume scrub) is one of the reasons for wanting a
"filesystem scrub" feature.

Nico
--

On Mon, Jul 09, 2007 at 03:42:03PM -0700, Darren Dunham
wrote:
> > Wouldn''t ZFS''s being an integrated filesystem make
it easier for it to
> > identify the file types vs. a standard block device with a filesystem 
> > overlaid upon it?
> 
> I''m not sure.  I would think that most applications are going to
use the
> POSIX layer where there''s no separate API for filetypes.  Every
file is
> "just" a bytestream.  I don''t see that ZFS gives you any
more
> information about a file''s purpose or use.
Of course, we could add an API (or extended attr naming convention) for
specifying MIME types for files.

"Richard Elling" <Richard.Elling at Sun.COM>
wrote:
> Dave Johnson wrote:
>> "roland" <devzero at web.de <mailto:devzero at
web.de>> wrote:
>>  >
>>  > there is also no filesystem based approach in 
>> compressing/decompressing a whole filesystem.
>>  one could kludge this by setting the compression parameters desired on
>> the tree then using a perl script to walk the tree, copying each file
to
>> a tmp file, renaming the original to an arbitrary name, renaming the
tmp
>> to the name of the original, then updating the new file with the
original
>> file''s metadata, do a checksum sanity check, then delete the
uncompressed
>> original.
>
> This solution has been proposed several times on this forum.
> It is simpler to use an archiving or copying tool (tar, cpio, pax,
> star, cp, rsync, rdist, install, zfs send/receive et.al.) to copy
> the tree once, then rename the top directory.  It makes no sense to
> me to write a copying tool in perl or shell.  KISS :-)
That''s not compresing an existing file tree, that''s creating a
compressed
copy, which isn''t the problem asked.  How do you do that if your tree
is
full (which is probably the #1 anyone would want to compress an existin 
tree) ?

You must be lucking enough to use BLISS (buying luns increases storage 
st...) :)

-=dave

> Wouldn''t ZFS''s being an integrated filesystem make it
> easier for it to 
> identify the file types vs. a standard block device
> with a filesystem 
> overlaid upon it?
> 
> I read in another post that with compression enabled,
> ZFS attempts to 
> compress the data and stores it compressed if it
> compresses enough. As far 
> as identifying the file type/data type how about:
> 1.) ZFS block compression system reads the ZFS file
> table to identify which 
> blocks are the beginning of files (or for new writes,
> the block compression 
> system is notified that file.ext is being written on
> block #### (e.g. block 
> 9,000,201).
> 2.) ZFS block compression system reads block ####,
> identifies the file type 
> probably based on the file header and applies the
> most appropriate 
> compression format, or if none found, the default
> 
> An approach for maximal compression:
> The algorithm selection could be
> 1.) attempt to compress using BWT, store compressed
> if BWT works better 
> than no compression
> 2.) when CPU is otherwise idle, use 10% of spare cpu
> cycles to "walk the 
> disk", trying to recompress each block with each of
> the various supported 
> compression algorithms, ultimately storing that block
> in the most space 
> efficient compression format.
> 
> This technique would result in a file system that
> tends to compact its data 
> ever more tightly as the data sits in it. It could be
> compared to 
> ''settling'' flakes in a cereal box...the contents may
> have had a lot of ''air 
> space'' before shipment, but are now
''compressed''. The
> recompression step 
> might even be part of a period disk scrubbing step
> meant to check and 
> recheck previously written data to make sure the
> sector it is sitting on 
> isn''t going bad.

this sounds really good - i like that ideas
 
 
This message posted from opensolaris.org

pedantic comment below...

dave johnson wrote:
> "Richard Elling" <Richard.Elling at Sun.COM> wrote:
>> Dave Johnson wrote:
>>> "roland" <devzero at web.de <mailto:devzero at
web.de>> wrote:
>>>  >
>>>  > there is also no filesystem based approach in 
>>> compressing/decompressing a whole filesystem.
>>>  one could kludge this by setting the compression parameters
desired on
>>> the tree then using a perl script to walk the tree, copying each
file to
>>> a tmp file, renaming the original to an arbitrary name, renaming
the tmp
>>> to the name of the original, then updating the new file with the
original
>>> file''s metadata, do a checksum sanity check, then delete
the uncompressed
>>> original.
>> This solution has been proposed several times on this forum.
>> It is simpler to use an archiving or copying tool (tar, cpio, pax,
>> star, cp, rsync, rdist, install, zfs send/receive et.al.) to copy
>> the tree once, then rename the top directory.  It makes no sense to
>> me to write a copying tool in perl or shell.  KISS :-)
> 
> That''s not compresing an existing file tree, that''s
creating a compressed
> copy, which isn''t the problem asked.  How do you do that if your
tree is
> full (which is probably the #1 anyone would want to compress an existin 
> tree) ?
IMHO that is a management problem, not a technology problem.
> You must be lucking enough to use BLISS (buying luns increases storage 
> st...) :)
Prior planning prevents piss-poor performance.  Really. ;-)
  -- richard

Adam Leventhal wrote:
> This is a great idea. I''d like to add a couple of suggestions:
> 
> It might be interesting to focus on compression algorithms which are
> optimized for particular workloads and data types, an Oracle database for
> example.
NB. Oracle 11g has builtin compression.  In general, for such problems, solving
them closer to the application is better.
> It might be worthwhile to have some sort of adaptive compression whereby
> ZFS could choose a compression algorithm based on its detection of the
> type of data being stored.
I think there is fertile ground in this area.  As CPU threads approach $0,
it might be a good idea to use more of them :-)
  -- richard