From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on dcvr.yhbt.net X-Spam-Level: X-Spam-ASN: AS31976 209.132.180.0/23 X-Spam-Status: No, score=-4.1 required=3.0 tests=AWL,BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,RCVD_IN_DNSWL_HI, RP_MATCHES_RCVD shortcircuit=no autolearn=ham autolearn_force=no version=3.4.0 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by dcvr.yhbt.net (Postfix) with ESMTP id 3D79420899 for ; Wed, 2 Aug 2017 16:51:46 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752492AbdHBQvn (ORCPT ); Wed, 2 Aug 2017 12:51:43 -0400 Received: from pb-smtp2.pobox.com ([64.147.108.71]:51752 "EHLO sasl.smtp.pobox.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1751964AbdHBQvn (ORCPT ); Wed, 2 Aug 2017 12:51:43 -0400 Received: from sasl.smtp.pobox.com (unknown [127.0.0.1]) by pb-smtp2.pobox.com (Postfix) with ESMTP id 6FBD98FCFC; Wed, 2 Aug 2017 12:51:42 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=pobox.com; h=from:to:cc :subject:references:date:in-reply-to:message-id:mime-version :content-type; s=sasl; bh=gldMVSmwEn005ny/HlRScxWjS5A=; b=rDTfC9 3jLOweKGXWKjWVCSFiu0QcEksbjdPmhBKNjRhsRfnOks7IfYhRxeAsUGWLJZoW5F 0p8rYXYMTlNF10OnKIv8UxI0H8HSnNR3fWkd/PjWk6yIL5y0npOYLgS4S46e5r8R LTRLV0x5cvGtru/QEwNV4VTWVkocAFoTz/mAk= DomainKey-Signature: a=rsa-sha1; c=nofws; d=pobox.com; h=from:to:cc :subject:references:date:in-reply-to:message-id:mime-version :content-type; q=dns; s=sasl; b=gbAhYVgL8UVXPoyDbwKaRxEoMsLu3Dm+ ptgd8v3hKrGgxnpLw/ETm7YfF0pQ9pg+5qFflj6TNjBogwnBo/B8KDmjNJCsP7iC 4jJjwWAQTVjJY1tCMRHv6YG1J7NTKrzUQgq3vPFvr2CteHk/jJWLM6+XcAU9b67v STCInRky/So= Received: from pb-smtp2.nyi.icgroup.com (unknown [127.0.0.1]) by pb-smtp2.pobox.com (Postfix) with ESMTP id 66B0E8FCFB; Wed, 2 Aug 2017 12:51:42 -0400 (EDT) Received: from pobox.com (unknown [104.132.0.95]) (using TLSv1.2 with cipher DHE-RSA-AES128-SHA (128/128 bits)) (No client certificate requested) by pb-smtp2.pobox.com (Postfix) with ESMTPSA id CBE6F8FCFA; Wed, 2 Aug 2017 12:51:41 -0400 (EDT) From: Junio C Hamano To: Shawn Pearce Cc: Jeff King , Michael Haggerty , git , David Borowitz Subject: Re: reftable [v4]: new ref storage format References: <20170802092846.u4lyiogvvl7ezdfq@sigill.intra.peff.net> Date: Wed, 02 Aug 2017 09:51:40 -0700 In-Reply-To: (Shawn Pearce's message of "Wed, 2 Aug 2017 08:17:29 -0700") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.2 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-Pobox-Relay-ID: DC0FE8D2-77A2-11E7-9E81-9D2B0D78B957-77302942!pb-smtp2.pobox.com Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Shawn Pearce writes: > On Wed, Aug 2, 2017 at 2:28 AM, Jeff King wrote: >> On Tue, Aug 01, 2017 at 07:38:37PM -0700, Shawn Pearce wrote: >> >>> > OBJS blocks can also be >>> > unbounded in size if very many references point at the same object, >>> > thought that is perhaps only a theoretical problem. >>> >>> Gah, I missed that in reftable. The block id pointer list could cause >>> a single object id to exceed what fits in a block, and that will cause >>> the writer to fail unless its caller sets the block size larger. I >>> basically assumed this overflow condition is very unlikely, as its not >>> common to have a huge number of refs pointing to the same object. >> >> It's actually quite common for us, as we have big shared-object repos >> that contain a copy of the refs of all of their child repos (for >> reachability during packing, etc). So tags, where the value is the same >> in each fork, you have one ref per fork pointing to it. >> >> Just peeking at torvalds/linux, we have some objects with ~35K refs >> pointing to them (e.g., the v2.6.11 tag). > > Oy. I'll bet that every occurrence winds up in its own block due to > the layout of the namespace, and so the obj block list needs 35k > varint pointers. That requires a larger block size if it has any > chance of fitting into the reftable format. > > Another option is disable the obj table for these shared-object repos. > Its an optional part of the format and can be omitted if the reader > isn't likely to need to lookup by SHA-1, or is willing to pay the > brute force cost of scanning every ref. I am wondering if we need the reverse look-up for a regular repository that allows "fetch anything at the tip". It only needs "I got this request for an object name--does it sit at the tip of any ref? Yes/No". It does not need to know exactly which ref points at the asked object. Yes, I know Gerrit has its own ACL that limits the visibility of refs so the question becomes "does it sit at the tip of any ref that is visible to the current user?". An Yes/No answer for "any ref?" may still give you a short-cut when rejecting, but you'd then need to scan to give a positive answer without a full reverse mapping. For the use of "consolidated object store for all forks", I do not think it makes sense to even have "Does it sit at a tip, Yes/No" information. Even when Linus's repository and a fork share the same object store, I do not think anybody expects to be able to fetch a commit at the tip of a branch in the fork but not in Linus's repository.