Linux-ext4 Archive on lore.kernel.org
 help / color / Atom feed
From: Andreas Dilger <adilger@dilger.ca>
To: harshad shirwadkar <harshadshirwadkar@gmail.com>
Cc: linux-ext4 <linux-ext4@vger.kernel.org>
Subject: Re: [PATCH 2/2] ext4: shrink directories on dentry delete
Date: Thu, 26 Mar 2020 15:07:23 -0600
Message-ID: <EAD1A1FC-DCF5-4B2B-BDE9-38E593691E23@dilger.ca> (raw)
In-Reply-To: <CAD+ocbxt5E+v8=zWQGuAPwtJMe_Qa8q9BhP1es05unaQ50ckkQ@mail.gmail.com>

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

On Mar 26, 2020, at 1:49 PM, harshad shirwadkar <harshadshirwadkar@gmail.com> wrote:
> 
> On Wed, Mar 25, 2020 at 3:06 AM Andreas Dilger <adilger@dilger.ca> wrote:
>> 
>> On Mar 25, 2020, at 3:37 AM, Harshad Shirwadkar <harshadshirwadkar@gmail.com> wrote:
>>> But note that most of the shrinking happens during last 1-2% deletions
>>> in an average case. Therefore, the next step here is to merge dx nodes
>>> when possible. That can be achieved by storing the fullness index in
>>> htree nodes. But that's an on-disk format change. We can instead build
>>> on tooling added by this patch to perform reverse lookup on a dx
>>> node and then reading adjacent nodes to check their fullness.
>> 
>> Thank you for updating these patches again.  I haven't had a chance to look
>> at them yet, but I hope to review the patches in the near future.
>> 
>> As for storing the fullness on disk changing the on-disk format...  That is
>> true, but the original htree implementation anticipated this and reserved
>> space in the htree index to store the fullness, so it would not break the
>> ability of older kernels to access directories with the fullness information.
>> 
> Yeah, you are right, good to know that we have bits reserved already
> and that wouldn't break older kernels if we use these in future.
>> I think if you used just a few bits (maybe just 2) to store:
>> 0 = unset (every directory today)
>> 1 = under 20% full
>> 2 = under 40% full
>> 3 = under 60% full
>> 
>> or similar.  It doesn't matter if they are more full since they won't be
>> candidates for merging, and then lazily update the htree index fullness
>> as entries are removed, this will simplify the shrinking process, and will
>> avoid the need to repeatedly scan the leaf blocks to see if they are empty
>> enough for merging.  It wouldn't be any worse *not* to store these values
>> on disk after the first time a "0 = unset" entry was found and not merged,
>> or setting the fullness on the merged block if it is merged, and running
>> "e2fsck -D" can easily update the fullness values.
>> 
>> The benefit of using 20%, 40%, and 60% as the fullness markers is that it
>> is possible to either merge adjacent 60% and 40% blocks or alternately a
>> 60% and two adjacent 20% blocks.  Also, since these values are very coarse
>> they would not need to be updated frequently.  If the values are slightly
>> outdated, then it is again not worse than the "always scan" model (one scan
>> and the fullness would be updated), but more efficient than repeat scanning.
>> 
>> Using only two bits for fullness also leaves two bits free for future use.
> 
> Thanks Andreas, that makes sense. This kind of merging will require
> lot of tooling provided in this patch - for example swapping out freed
> block with last block to not leave any holes. So, my hope is that we
> get this patch in first and thereby get a step closer to coalescing
> solution.

Definitely I *do not* want to block the landing of these initial patches
until a "full featured" directory shrinking is complete.  These patches
at least provide some basic functionality, and will at least shrink a
large directory if it becomes totally empty so I'm in favour of that.

Cheers, Andreas






[-- Attachment #2: Message signed with OpenPGP --]
[-- Type: application/pgp-signature, Size: 873 bytes --]

  reply index

Thread overview: 7+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2020-03-25  9:37 [PATCH 1/2] ext4: return lblk from ext4_find_entry Harshad Shirwadkar
2020-03-25  9:37 ` [PATCH 2/2] ext4: shrink directories on dentry delete Harshad Shirwadkar
2020-03-25 10:06   ` Andreas Dilger
2020-03-26 19:49     ` harshad shirwadkar
2020-03-26 21:07       ` Andreas Dilger [this message]
2020-03-29  0:01   ` Andreas Dilger
2020-03-28 23:24 ` [PATCH 1/2] ext4: return lblk from ext4_find_entry Andreas Dilger

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=EAD1A1FC-DCF5-4B2B-BDE9-38E593691E23@dilger.ca \
    --to=adilger@dilger.ca \
    --cc=harshadshirwadkar@gmail.com \
    --cc=linux-ext4@vger.kernel.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

Linux-ext4 Archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lore.kernel.org/linux-ext4/0 linux-ext4/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 linux-ext4 linux-ext4/ https://lore.kernel.org/linux-ext4 \
		linux-ext4@vger.kernel.org
	public-inbox-index linux-ext4

Example config snippet for mirrors

Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/org.kernel.vger.linux-ext4


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git