From mboxrd@z Thu Jan 1 00:00:00 1970 From: Caleb Ristvedt Subject: Re: guix gc takes long in "deleting unused links ..." Date: Wed, 06 Feb 2019 15:32:51 -0600 Message-ID: <87sgx0ob5o.fsf@cune.org> References: <20190201065332.6d4c9815@alma-ubu> <87womjcfoi.fsf@cune.org> <874l9jqmwp.fsf@gnu.org> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Return-path: Received: from eggs.gnu.org ([209.51.188.92]:58968) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1grUog-0003su-CV for guix-devel@gnu.org; Wed, 06 Feb 2019 16:33:11 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1grUoe-0004qG-83 for guix-devel@gnu.org; Wed, 06 Feb 2019 16:33:09 -0500 Received: from mail-it1-x12b.google.com ([2607:f8b0:4864:20::12b]:38312) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1grUoW-0004lr-20 for guix-devel@gnu.org; Wed, 06 Feb 2019 16:33:02 -0500 Received: by mail-it1-x12b.google.com with SMTP id z20so9715819itc.3 for ; Wed, 06 Feb 2019 13:32:54 -0800 (PST) In-Reply-To: <874l9jqmwp.fsf@gnu.org> ("Ludovic \=\?utf-8\?Q\?Court\=C3\=A8s\=22'\?\= \=\?utf-8\?Q\?s\?\= message of "Mon, 04 Feb 2019 22:11:34 +0100") List-Id: "Development of GNU Guix and the GNU System distribution." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guix-devel-bounces+gcggd-guix-devel=m.gmane.org@gnu.org Sender: "Guix-devel" To: guix-devel@gnu.org, ludo@gnu.org Ludovic Court=C3=A8s writes: > Note that the database would need to contain hashes of individual files, > not just store items (it already contains hashes of store item nars). Indeed! Although last night I thought of a way that it would only need to contain hashes of *unique* individual files, see below. > This issue was discussed a while back at > . Back then we couldn=E2=80=99t ag= ree on > a solution, but it=E2=80=99d be good to have your opinion with your fresh= mind! The main thing that comes to mind is making the amount of time required for deleting links scale with the number of things being deleted rather than the number of "things" in total - O(m) instead of O(n), so to speak. I actually hadn't even considered things like disk access patterns. In my mind, the ideal situation is like this: we get rid of .links, and instead keep a mapping from hashes to inodes in the database. Deduplication would then involve just creating a hardlink to the corresponding inode. The link-deleting phase then becomes entirely unnecessary, as when the last hardlink is deleted the refcount becomes 0 automatically. Unfortunately, this isn't possible, because AFAIK there is no way to create a hardlink to an inode directly; it always has to go through another hardlink. Presumably the necessary system call doesn't exist because there would be permissions / validation issues (if anyone happens to know of a function that does something like this, I'd love to hear about it!). So the second-most-ideal situation would, to me, be to keep a mapping from inodes to hashes in the database. Then, when it becomes known during garbage collection that a file is to be deleted and the refcount for its inode is 2, the file's inode can be obtained from stat(), from that the hash can be looked up, and from that the corresponding link filename can be obtained and removed. After that the inode->hash association can be removed from the database. I think this is a reasonable approach, as such a table in the database shouldn't take up much more disk space than .links does: 8 bytes for an inode, and 32 bytes for the hash (or 52 if we keep the hash in text form), for a total of 60 bytes. Based on the numbers from the linked discussion (10M entries), that's around 400MB or 600MB, plus whatever extra space sqlite uses, kept on the disk. If that's considered too high, we could only store the hashes of relatively large files in the database and fall back to hashing at delete-time for the others. The main limitation is the lack of portability of inodes. That is, when copying a store across filesystems, said table would need to be updated. Also, it requires that everything in the store is on the same filesystem, though this could be fixed by looking up the hash through (inode, device number) pairs instead of just inode. In that case, it would work to copy across filesystems, though I think it still wouldn't work for copying across systems. How does that sound? > The guix-daemon child that handles the session would immediately get > SIGHUP and terminate (I think), but that=E2=80=99s fine: it=E2=80=99s jus= t that files > that could have been removed from .links will still be there. Turns out it's SIGPOLL, actually, but yep. There's a checkInterrupt() that gets run before each attempt to delete a link, and that triggers the exit. - reepca