From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on dcvr.yhbt.net X-Spam-Level: X-Spam-ASN: AS31976 209.132.180.0/23 X-Spam-Status: No, score=-4.3 required=3.0 tests=AWL,BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI shortcircuit=no autolearn=ham autolearn_force=no version=3.4.2 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by dcvr.yhbt.net (Postfix) with ESMTP id 280631F453 for ; Thu, 24 Jan 2019 21:52:00 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728187AbfAXVv7 (ORCPT ); Thu, 24 Jan 2019 16:51:59 -0500 Received: from mail-ed1-f42.google.com ([209.85.208.42]:42877 "EHLO mail-ed1-f42.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728024AbfAXVv6 (ORCPT ); Thu, 24 Jan 2019 16:51:58 -0500 Received: by mail-ed1-f42.google.com with SMTP id y20so5814256edw.9 for ; Thu, 24 Jan 2019 13:51:55 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=date:message-id:in-reply-to:references:from:subject:mime-version :content-transfer-encoding:fcc:content-transfer-encoding:to:cc; bh=4kFKcdB6xN/aatAiy+QEZHqmnHKNaL0wHvhKsHnYz1E=; b=BekSBCpEb5JR/CAeOanHfs5ylonx/4Mw+gPB7xwq1yl3O91LzfsQdfmPaAM++L/QFK Lcu/INJXqb8WfAErzavisZudkcTCbrdhBGEDNDQdjeh6rEtDR9CwXNHr/4kKzHyU0mlH Yv2+7fNUCbKg5pnfawHw0lLTLMhr21TIzxCuXGMyYm2B07oHEDGLTzpltm5xSN2SfaQ6 eK3MTb8l3ZcAoRRQLpS18/ZwQUhgBgVAPEt2Ton5oDK96aR2Cqkz3ff2US2N8oYJqpzG iSdjrGFdT9aswcMYjG50B8MrRuuj2SEIJSWtMlzso6J9QRt3ofH81fIrARFsLNUMhw+w DBYA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:message-id:in-reply-to:references:from :subject:mime-version:content-transfer-encoding:fcc :content-transfer-encoding:to:cc; bh=4kFKcdB6xN/aatAiy+QEZHqmnHKNaL0wHvhKsHnYz1E=; b=LIaxql4eCEUJUPGsGwDyQXzReXS2VSbgB3uXNApYtuehWvZuTCZzoCstkWyreqOv2L Vo+/3sxmKY0yUixUuW11HDbDNcSk0W5Af7nWKNTVvGmEX4EasAj2NHv6PveqfhAOP4CC ITIRecWeKv7BkyfhIO+WEEUCrrJl0KzY9QyJV3XcLUrkzVg6GvSQRjtAdS0IlP3Pn81A h4C1RqN3UwfpGxCDpU8ftXpl3F6IzfuQVPyZRupMyiaaE+1XOq0grwAM7YTaCwRAaWAR tgndOgsSV0FS1B2IIpTOE+fKjRFQamkvTiCLoz+gpgXo71cYmiFSwBftnCj/cZOEq/NL PwBw== X-Gm-Message-State: AJcUukcIBXxOxHz94CpbJZz5nqiOKPlSdZ9w4/wSP4ou0EdrEoLuZUmV WDbN+hchWLsz2Q/UfsjUb58JT6A3 X-Google-Smtp-Source: ALg8bN5mYPML8y+Bzq093x+xyNI7sRZAE/gh9GcxIDZoM7rosxwDm08AoLmZjxcVYb4Dkll8VNL66w== X-Received: by 2002:a50:8b26:: with SMTP id l35mr7953563edl.146.1548366714699; Thu, 24 Jan 2019 13:51:54 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id c26sm182939edb.15.2019.01.24.13.51.53 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 24 Jan 2019 13:51:54 -0800 (PST) Date: Thu, 24 Jan 2019 13:51:54 -0800 (PST) X-Google-Original-Date: Thu, 24 Jan 2019 21:51:43 GMT Message-Id: In-Reply-To: References: From: "Derrick Stolee via GitGitGadget" Subject: [PATCH v4 00/10] Create 'expire' and 'repack' verbs for git-multi-pack-index MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Fcc: Sent Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit To: git@vger.kernel.org Cc: sbeller@google.com, peff@peff.net, jrnieder@gmail.com, avarab@gmail.com, jonathantanmy@google.com, Junio C Hamano Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org The multi-pack-index provides a fast way to find an object among a large list of pack-files. It stores a single pack-reference for each object id, so duplicate objects are ignored. Among a list of pack-files storing the same object, the most-recently modified one is used. Create new subcommands for the multi-pack-index builtin. * 'git multi-pack-index expire': If we have a pack-file indexed by the multi-pack-index, but all objects in that pack are duplicated in more-recently modified packs, then delete that pack (and any others like it). Delete the reference to that pack in the multi-pack-index. * 'git multi-pack-index repack --batch-size=': Starting from the oldest pack-files covered by the multi-pack-index, find those whose on-disk size is below the batch size until we have a collection of packs whose sizes add up to the batch size. Create a new pack containing all objects that the multi-pack-index references to those packs. This allows us to create a new pattern for repacking objects: run 'repack'. After enough time has passed that all Git commands that started before the last 'repack' are finished, run 'expire' again. This approach has some advantages over the existing "repack everything" model: 1. Incremental. We can repack a small batch of objects at a time, instead of repacking all reachable objects. We can also limit ourselves to the objects that do not appear in newer pack-files. 2. Highly Available. By adding a new pack-file (and not deleting the old pack-files) we do not interrupt concurrent Git commands, and do not suffer performance degradation. By expiring only pack-files that have no referenced objects, we know that Git commands that are doing normal object lookups* will not be interrupted. 3. Note: if someone concurrently runs a Git command that uses get_all_packs(), then that command could try to read the pack-files and pack-indexes that we are deleting during an expire command. Such commands are usually related to object maintenance (i.e. fsck, gc, pack-objects) or are related to less-often-used features (i.e. fast-import, http-backend, server-info). We plan to use this approach in VFS for Git to do background maintenance of the "shared object cache" which is a Git alternate directory filled with packfiles containing commits and trees. We currently download pack-files on an hourly basis to keep up-to-date with the central server. The cache servers supply packs on an hourly and daily basis, so most of the hourly packs become useless after a new daily pack is downloaded. The 'expire' command would clear out most of those packs, but many will still remain with fewer than 100 objects remaining. The 'repack' command (with a batch size of 1-3gb, probably) can condense the remaining packs in commands that run for 1-3 min at a time. Since the daily packs range from 100-250mb, we will also combine and condense those packs. Updates in V2: * Added a method, unlink_pack_path() to remove packfiles, but with the additional check for a .keep file. This borrows logic from builtin/repack.c. * Modified documentation and commit messages to replace 'verb' with 'subcommand'. Simplified the documentation. (I left 'verbs' in the title of the cover letter for consistency.) Updates in V3: * There was a bug in the expire logic when simultaneously removing packs and adding uncovered packs, specifically around the pack permutation. This was hard to see during review because I was using the 'pack_perm' array for multiple purposes. First, I was reducing its length, and then I was adding to it and resorting. In V3, I significantly overhauled the logic here, which required some extra commits before implementing 'expire'. The final commit includes a test that would cover this case. Updates in V4: * More 'verb' and 'command' instances replaced with 'subcommand'. I grepped the patch to check these should be fixed everywhere. * Update the tests to check .keep files (in last patch). * Modify the tests to show the terminating condition of --batch-size when there are three packs that fit under the size, but the first two are large enough to stop adding packs. This required rearranging the packs slightly to get different sizes than we had before. Also, I added 'touch -t' to set the modified times so we can fix the order in which the packs are selected. * Added a comment about the purpose of pack_perm. Thanks, -Stolee Derrick Stolee (10): repack: refactor pack deletion for future use Docs: rearrange subcommands for multi-pack-index multi-pack-index: prepare for 'expire' subcommand midx: simplify computation of pack name lengths midx: refactor permutation logic and pack sorting multi-pack-index: implement 'expire' subcommand multi-pack-index: prepare 'repack' subcommand midx: implement midx_repack() multi-pack-index: test expire while adding packs midx: add test that 'expire' respects .keep files Documentation/git-multi-pack-index.txt | 26 +- builtin/multi-pack-index.c | 14 +- builtin/repack.c | 14 +- midx.c | 399 ++++++++++++++++++------- midx.h | 2 + packfile.c | 28 ++ packfile.h | 7 + t/t5319-multi-pack-index.sh | 165 ++++++++++ 8 files changed, 536 insertions(+), 119 deletions(-) base-commit: 26aa9fc81d4c7f6c3b456a29da0b7ec72e5c6595 Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-92%2Fderrickstolee%2Fmidx-expire%2Fupstream-v4 Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-92/derrickstolee/midx-expire/upstream-v4 Pull-Request: https://github.com/gitgitgadget/git/pull/92 Range-diff vs v3: 1: 62b393b816 = 1: 62b393b816 repack: refactor pack deletion for future use 2: 7886785904 = 2: 7886785904 Docs: rearrange subcommands for multi-pack-index 3: f06382b4ae ! 3: 628ca46036 multi-pack-index: prepare for 'expire' subcommand @@ -16,7 +16,9 @@ Add a test that verifies the 'expire' subcommand is correctly wired, but will still be valid when the verb is implemented. Specifically, create a set of packs that should all have referenced objects and - should not be removed during an 'expire' operation. + should not be removed during an 'expire' operation. The packs are + created carefully to ensure they have a specific order when sorted + by size. This will be important in a later test. Signed-off-by: Derrick Stolee @@ -95,6 +97,8 @@ + ( + cd dup && + git init && ++ test-tool genrandom "data" 4096 >large_file.txt && ++ git update-index --add large_file.txt && + for i in $(test_seq 1 20) + do + test_commit $i @@ -104,24 +108,24 @@ + git branch C HEAD~13 && + git branch D HEAD~16 && + git branch E HEAD~18 && -+ git pack-objects --revs .git/objects/pack/pack-E <<-EOF && -+ refs/heads/E ++ git pack-objects --revs .git/objects/pack/pack-A <<-EOF && ++ refs/heads/A ++ ^refs/heads/B + EOF -+ git pack-objects --revs .git/objects/pack/pack-D <<-EOF && -+ refs/heads/D -+ ^refs/heads/E ++ git pack-objects --revs .git/objects/pack/pack-B <<-EOF && ++ refs/heads/B ++ ^refs/heads/C + EOF + git pack-objects --revs .git/objects/pack/pack-C <<-EOF && + refs/heads/C + ^refs/heads/D + EOF -+ git pack-objects --revs .git/objects/pack/pack-B <<-EOF && -+ refs/heads/B -+ ^refs/heads/C ++ git pack-objects --revs .git/objects/pack/pack-D <<-EOF && ++ refs/heads/D ++ ^refs/heads/E + EOF -+ git pack-objects --revs .git/objects/pack/pack-A <<-EOF && -+ refs/heads/A -+ ^refs/heads/B ++ git pack-objects --revs .git/objects/pack/pack-E <<-EOF && ++ refs/heads/E + EOF + git multi-pack-index write + ) 4: 2a763990ae ! 4: d55c1d7ee7 midx: simplify computation of pack name lengths @@ -12,7 +12,7 @@ dir not already covered by the multi-pack-index. In anticipation of this becoming more complicated with the 'expire' - command, simplify the computation by centralizing it to a single + subcommand, simplify the computation by centralizing it to a single loop before writing the file. Signed-off-by: Derrick Stolee 5: a0d4cc6cb3 ! 5: 3950743b96 midx: refactor permutation logic and pack sorting @@ -282,6 +282,12 @@ + QSORT(packs.info, packs.nr, pack_info_compare); + ++ /* ++ * pack_perm stores a permutation between pack-int-ids from the ++ * previous multi-pack-index to the new one we are writing: ++ * ++ * pack_perm[old_id] = new_id ++ */ + ALLOC_ARRAY(pack_perm, packs.nr); + for (i = 0; i < packs.nr; i++) { + pack_perm[packs.info[i].orig_pack_int_id] = i; 6: 4dbff40e7a ! 6: 6691d97902 multi-pack-index: implement 'expire' verb @@ -1,8 +1,8 @@ Author: Derrick Stolee - multi-pack-index: implement 'expire' verb + multi-pack-index: implement 'expire' subcommand - The 'git multi-pack-index expire' command looks at the existing + The 'git multi-pack-index expire' subcommand looks at the existing mult-pack-index, counts the number of objects referenced in each pack-file, deletes the pack-fils with no referenced objects, and rewrites the multi-pack-index to no longer reference those packs. @@ -18,7 +18,7 @@ Test that a new pack-file that covers the contents of two other pack-files leads to those pack-files being deleted during the - expire command. Be sure to read the multi-pack-index to ensure + expire subcommand. Be sure to read the multi-pack-index to ensure it no longer references those packs. Signed-off-by: Derrick Stolee @@ -161,6 +161,11 @@ + } + } + + /* + * pack_perm stores a permutation between pack-int-ids from the + * previous multi-pack-index to the new one we are writing: +@@ + */ ALLOC_ARRAY(pack_perm, packs.nr); for (i = 0; i < packs.nr; i++) { - pack_perm[packs.info[i].orig_pack_int_id] = i; @@ -273,7 +278,9 @@ + test_cmp expect actual && + ls .git/objects/pack/ | grep idx >expect-idx && + test-tool read-midx .git/objects | grep idx >actual-midx && -+ test_cmp expect-idx actual-midx ++ test_cmp expect-idx actual-midx && ++ git multi-pack-index verify && ++ git fsck + ) +' + 7: b39f90ad09 ! 7: f5a8ff21dd multi-pack-index: prepare 'repack' subcommand @@ -11,7 +11,7 @@ operation does not interrupt concurrent git commands. Introduce a 'repack' subcommand to 'git multi-pack-index' that - takes a '--batch-size' option. The verb will inspect the + takes a '--batch-size' option. The subcommand will inspect the multi-pack-index for referenced pack-files whose size is smaller than the batch size, until collecting a list of pack-files whose sizes sum to larger than the batch size. Then, a new pack-file @@ -26,6 +26,11 @@ we specify a small batch size, we will guarantee that future implementations do not change the list of pack-files. + In addition, we hard-code the modified times of the packs in + the pack directory to ensure the list of packs sorted by modified + time matches the order if sorted by size (ascending). This will + be important in a future test. + Signed-off-by: Derrick Stolee diff --git a/Documentation/git-multi-pack-index.txt b/Documentation/git-multi-pack-index.txt @@ -36,15 +41,15 @@ afterward to remove all references to these pack-files. +repack:: -+ Collect a batch of pack-files whose size are all at most the -+ size given by --batch-size, but whose sizes sum to larger -+ than --batch-size. The batch is selected by greedily adding -+ small pack-files starting with the oldest pack-files that fit -+ the size. Create a new pack-file containing the objects the -+ multi-pack-index indexes into those pack-files, and rewrite -+ the multi-pack-index to contain that pack-file. A later run -+ of 'git multi-pack-index expire' will delete the pack-files -+ that were part of this batch. ++ Create a new pack-file containing objects in small pack-files ++ referenced by the multi-pack-index. Select the pack-files by ++ examining packs from oldest-to-newest, adding a pack if its ++ size is below the batch size. Stop adding packs when the sum ++ of sizes of the added packs is above the batch size. If the ++ total size does not reach the batch size, then do nothing. ++ Rewrite the multi-pack-index to reference the new pack-file. ++ A later run of 'git multi-pack-index expire' will delete the ++ pack-files that were part of this batch. + EXAMPLES @@ -84,11 +89,18 @@ + if (!strcmp(argv[0], "repack")) + return midx_repack(opts.object_dir, (size_t)opts.batch_size); + if (opts.batch_size) -+ die(_("--batch-size option is only for 'repack' verb")); ++ die(_("--batch-size option is only for 'repack' subcommand")); + if (!strcmp(argv[0], "write")) return write_midx_file(opts.object_dir); if (!strcmp(argv[0], "verify")) +@@ + if (!strcmp(argv[0], "expire")) + return expire_midx_packs(opts.object_dir); + +- die(_("unrecognized verb: %s"), argv[0]); ++ die(_("unrecognized subcommand: %s"), argv[0]); + } diff --git a/midx.c b/midx.c --- a/midx.c @@ -125,6 +137,12 @@ +test_expect_success 'repack with minimum size does not alter existing packs' ' + ( + cd dup && ++ rm -rf .git/objects/pack && ++ mv .git/objects/pack-backup .git/objects/pack && ++ touch -m -t 201901010000 .git/objects/pack/pack-D* && ++ touch -m -t 201901010001 .git/objects/pack/pack-C* && ++ touch -m -t 201901010002 .git/objects/pack/pack-B* && ++ touch -m -t 201901010003 .git/objects/pack/pack-A* && + ls .git/objects/pack >expect && + MINSIZE=$(ls -l .git/objects/pack/*pack | awk "{print \$5;}" | sort -n | head -n 1) && + git multi-pack-index repack --batch-size=$MINSIZE && 8: a4c2d5a8e1 ! 8: ba1a1c7bbb midx: implement midx_repack() @@ -149,6 +149,16 @@ diff --git a/t/t5319-multi-pack-index.sh b/t/t5319-multi-pack-index.sh --- a/t/t5319-multi-pack-index.sh +++ b/t/t5319-multi-pack-index.sh +@@ + git pack-objects --revs .git/objects/pack/pack-E <<-EOF && + refs/heads/E + EOF +- git multi-pack-index write ++ git multi-pack-index write && ++ cp -r .git/objects/pack .git/objects/pack-backup + ) + ' + @@ ) ' @@ -156,25 +166,28 @@ +test_expect_success 'repack creates a new pack' ' + ( + cd dup && -+ SECOND_SMALLEST_SIZE=$(ls -l .git/objects/pack/*pack | awk "{print \$5;}" | sort -n | head -n 2 | tail -n 1) && -+ BATCH_SIZE=$(($SECOND_SMALLEST_SIZE + 1)) && -+ git multi-pack-index repack --batch-size=$BATCH_SIZE && + ls .git/objects/pack/*idx >idx-list && + test_line_count = 5 idx-list && ++ THIRD_SMALLEST_SIZE=$(ls -l .git/objects/pack/*pack | awk "{print \$5;}" | sort -n | head -n 3 | tail -n 1) && ++ BATCH_SIZE=$(($THIRD_SMALLEST_SIZE + 1)) && ++ git multi-pack-index repack --batch-size=$BATCH_SIZE && ++ ls .git/objects/pack/*idx >idx-list && ++ test_line_count = 6 idx-list && + test-tool read-midx .git/objects | grep idx >midx-list && -+ test_line_count = 5 midx-list ++ test_line_count = 6 midx-list + ) +' + +test_expect_success 'expire removes repacked packs' ' + ( + cd dup && -+ ls -S .git/objects/pack/*pack | head -n 3 >expect && ++ ls -al .git/objects/pack/*pack && ++ ls -S .git/objects/pack/*pack | head -n 4 >expect && + git multi-pack-index expire && + ls -S .git/objects/pack/*pack >actual && + test_cmp expect actual && + test-tool read-midx .git/objects | grep idx >midx-list && -+ test_line_count = 3 midx-list ++ test_line_count = 4 midx-list + ) +' + 9: b97fb35ba9 = 9: b1c6892417 multi-pack-index: test expire while adding packs -: ---------- > 10: 481b08890f midx: add test that 'expire' respects .keep files -- gitgitgadget