linux-erofs.lists.ozlabs.org archive mirror
 help / color / mirror / Atom feed
From: Gao Xiang <hsiangkao@linux.alibaba.com>
To: ZiyangZhang <ZiyangZhang@linux.alibaba.com>
Cc: linux-erofs@lists.ozlabs.org
Subject: Re: [PATCH 4/4] erofs-utils: mkfs: introduce global compressed data deduplication
Date: Wed, 7 Sep 2022 13:55:50 +0800	[thread overview]
Message-ID: <YxgyZqrZs1X2V1pC@B-P7TQMD6M-0146.local> (raw)
In-Reply-To: <20220906114057.151445-4-ZiyangZhang@linux.alibaba.com>

On Tue, Sep 06, 2022 at 07:40:57PM +0800, ZiyangZhang wrote:
> From: Ziyang Zhang <ZiyangZhang@linux.alibaba.com>
> 
> This patch introduces global compressed data deduplication to
> reuse potential prefixes for each pcluster.
> 
> It also uses rolling hashing and shortens the previous compressed
> extent in order to explore more possibilities for deduplication.
> 
> Co-developped-by: Gao Xiang <hsiangkao@linux.alibaba.com>
> Signed-off-by: Ziyang Zhang <ZiyangZhang@linux.alibaba.com>

Some preliminary numbers:
Image				Fs	Type						Size
system.raven.87e115a1           erofs   uncompressed                                    910082048
system.raven.87e115a1           erofs   4k pcluster + lz4hc,9 + ztailpacking            584970240       -35.7% off
system.raven.87e115a1           erofs   4k pcluster + lz4hc,9 + ztailpacking + dedupe   569376768       -37.4% off

linux-5.10 + linux-5.10.87      erofs   uncompressed                                     1943691264
linux-5.10 + linux-5.10.87      erofs   4k pcluster + lz4hc,9 + ztailpacking             661987328      -65.9% off
linux-5.10 + linux-5.10.87      erofs   4k pcluster + lz4hc,9 + ztailpacking + dedupe    490295296      -74.8% off

linux-5.10.87                   erofs   4k pcluster + lz4hc,9                            331292672

One observation is since the tailpacking pcluster doesn't have blkaddr
so data relating to tailpacking pcluster cannot be deduped.

On the other side, it can work with `fragment' feature later together to
minimize image sizes.


Attach a fix for uncompressed pcluster:

diff --git a/lib/dedupe.c b/lib/dedupe.c
index c53a64edfc8d..c382303e2ceb 100644
--- a/lib/dedupe.c
+++ b/lib/dedupe.c
@@ -21,7 +21,7 @@ struct z_erofs_dedupe_item {
 	unsigned int	compressed_blks;
 
 	int		original_length;
-	bool		partial;
+	bool		partial, raw;
 	u8		extra_data[];
 };
 
@@ -86,6 +86,7 @@ int z_erofs_dedupe_match(struct z_erofs_dedupe_ctx *ctx)
 		ctx->e.length = window_size + extra;
 		ctx->e.partial = e->partial ||
 			(window_size + extra < e->original_length);
+		ctx->e.raw = e->raw;
 		ctx->e.blkaddr = e->compressed_blkaddr;
 		ctx->e.compressedblks = e->compressed_blks;
 		return 0;
@@ -114,6 +115,7 @@ int z_erofs_dedupe_insert(struct z_erofs_inmem_extent *e,
 	di->compressed_blkaddr = e->blkaddr;
 	di->compressed_blks = e->compressedblks;
 	di->partial = e->partial;
+	di->raw = e->raw;
 
 	/* with the same rolling hash */
 	if (!rb_tree_insert(dedupe_subtree, di))
-- 
2.30.2


  reply	other threads:[~2022-09-07  5:56 UTC|newest]

Thread overview: 6+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2022-09-06 11:40 [PATCH 1/4] erofs-utils: introduce z_erofs_inmem_extent ZiyangZhang
2022-09-06 11:40 ` [PATCH 2/4] erofs-utils: lib: add rb-tree implementation ZiyangZhang
2022-09-06 11:40 ` [PATCH 3/4] erofs-utils: fuse: introduce partial-referenced pclusters ZiyangZhang
2022-09-06 11:40 ` [PATCH 4/4] erofs-utils: mkfs: introduce global compressed data deduplication ZiyangZhang
2022-09-07  5:55   ` Gao Xiang [this message]
2022-09-08  0:56     ` Gao Xiang

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=YxgyZqrZs1X2V1pC@B-P7TQMD6M-0146.local \
    --to=hsiangkao@linux.alibaba.com \
    --cc=ZiyangZhang@linux.alibaba.com \
    --cc=linux-erofs@lists.ozlabs.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).