From mboxrd@z Thu Jan 1 00:00:00 1970
Return-Path: <gentoo-dev+bounces-83693-garchives=archives.gentoo.org@lists.gentoo.org>
Received: from lists.gentoo.org (pigeon.gentoo.org [208.92.234.80])
(using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits))
(No client certificate requested)
by finch.gentoo.org (Postfix) with ESMTPS id 2F10F1382C5
for <garchives@archives.gentoo.org>; Mon, 29 Jan 2018 21:00:35 +0000 (UTC)
Received: from pigeon.gentoo.org (localhost [127.0.0.1])
by pigeon.gentoo.org (Postfix) with SMTP id C7954E0ADE;
Mon, 29 Jan 2018 21:00:28 +0000 (UTC)
Received: from mail-vk0-x232.google.com (mail-vk0-x232.google.com [IPv6:2607:f8b0:400c:c05::232])
(using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits))
(No client certificate requested)
by pigeon.gentoo.org (Postfix) with ESMTPS id 37FF3E0A8E
for <gentoo-dev@lists.gentoo.org>; Mon, 29 Jan 2018 21:00:27 +0000 (UTC)
Received: by mail-vk0-x232.google.com with SMTP id z9so5417595vkd.5
for <gentoo-dev@lists.gentoo.org>; Mon, 29 Jan 2018 13:00:27 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=scriptkitty-com.20150623.gappssmtp.com; s=20150623;
h=mime-version:sender:in-reply-to:references:from:date:message-id
:subject:to;
bh=L4vR9IkzQ1hsBv06XGt/esLxprXfdVkWDwLw3OIDpbI=;
b=NZ04Wx9A7E30dL7Tlqhdk/dkELTxTYaXqt0csCP/Znetd3tiQmryFEsF8xo3trxX3i
CgltPBHO/GCgCvi0miigIbQjNfVBlPJk4D3FlYySvfPuOVWOF9GYLrLg2QPm3Ltrre+d
TCDkHZbSEznnHdzCUC0rOIRbe1R4ulBvYNmIrDZObEFW29d021DIwyk5D3G/bjuLK2G7
Zkh/0sh8ATWzAOPikLZVL7IugFg8NE4sIzHkCSittsIY9MDteNQxDZs0izcXO359X98v
wiKN1P04NmtgGyL/+bM8RYBoPkO3y/8j5HfDGG8Jk4cZtn7LFZioiDMUGpTMBhclNiXd
SwVw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:sender:in-reply-to:references:from
:date:message-id:subject:to;
bh=L4vR9IkzQ1hsBv06XGt/esLxprXfdVkWDwLw3OIDpbI=;
b=rVl6Y3LfkpUlX5P8iiBwax3OjdaNtjlu64kMWlYIKanujv2qZmyh8BlMiZ2/gfUIFC
5pxcM6wR1Bv/y52MiZY/2k7MXyTnhQGIAMmQ9X+1If3WoOVo8yWyPIAykZ8AYLQHI3fD
cp4k7ke2sV4I+ddzb6faOPXigim7l5GGg1s2DYHL3F6ndBeZUWwvyvFKIYmlXr4HKFRA
hadw3ipWHmrNtv1+M0fZa38BEmvNaQjF6YNCQf9byLJMFUwdeBdZm4pmt9yEFheScPiA
8M1yy3f9LoXHjW4asAtaoxDEmN3lpqn0NevH/o8U9wtZOJdy1RO1Pb0oOb1HMtTb/mRI
i35w==
X-Gm-Message-State: AKwxyteuBFxiHG6OfMZ4OS1bRbxhGvGC+ExVloSi30n8VSr+9SCJRQmw
QMKHUmjo2qxP0M4dslilAm4obZ8+2EoX2qQblyLmWdk6
X-Google-Smtp-Source: AH8x227s7p8fu9B88wQ62G9fDAvtoX4l/wBBczl7bEdk3u2MOOVcfsjKRFEdvks2lhM3/NPGVaNXeAwBun3XRB2amlQ=
X-Received: by 10.31.52.12 with SMTP id b12mr19198682vka.178.1517259626701;
Mon, 29 Jan 2018 13:00:26 -0800 (PST)
Precedence: bulk
List-Post: <mailto:gentoo-dev@lists.gentoo.org>
List-Help: <mailto:gentoo-dev+help@lists.gentoo.org>
List-Unsubscribe: <mailto:gentoo-dev+unsubscribe@lists.gentoo.org>
List-Subscribe: <mailto:gentoo-dev+subscribe@lists.gentoo.org>
List-Id: Gentoo Linux mail <gentoo-dev.gentoo.org>
X-BeenThere: gentoo-dev@lists.gentoo.org
Reply-to: gentoo-dev@lists.gentoo.org
MIME-Version: 1.0
Sender: antarus@scriptkitty.com
Received: by 10.176.13.139 with HTTP; Mon, 29 Jan 2018 12:55:43 -0800 (PST)
X-Originating-IP: [2620:0:1003:512:4092:948:1f63:8004]
In-Reply-To: <CAAD4mYj=ZDr3WFopvrqHoh7Cg+MeDS+yUKtTMn+-p=8DJuymgw@mail.gmail.com>
References: <1517009079.31015.3.camel@gentoo.org> <1517254667.1187.25.camel@gentoo.org>
<CAAD4mYj=ZDr3WFopvrqHoh7Cg+MeDS+yUKtTMn+-p=8DJuymgw@mail.gmail.com>
From: Alec Warner <antarus@gentoo.org>
Date: Mon, 29 Jan 2018 15:55:43 -0500
X-Google-Sender-Auth: jsi0v7HGeuUrSUHK79LFIC1Opu4
Message-ID: <CAAr7Pr-1PRaeK2--rnNnTFmKhH6WitztoLambUq1tRCK1wjwUg@mail.gmail.com>
Subject: Re: [gentoo-dev] [pre-GLEP] Split distfile mirror directory structure
(draft v2)
To: Gentoo Dev <gentoo-dev@lists.gentoo.org>
Content-Type: multipart/alternative; boundary="001a1143fa4014fcaf0563f08962"
X-Archives-Salt: 1513201d-ef48-490e-a36a-5ea6c86279f5
X-Archives-Hash: e539e3f564031d130d7ac773fb91ce89
--001a1143fa4014fcaf0563f08962
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
On Mon, Jan 29, 2018 at 3:26 PM, R0b0t1 <r030t1@gmail.com> wrote:
> On Monday, January 29, 2018, Micha=C5=82 G=C3=B3rny <mgorny@gentoo.org> w=
rote:
> > Here's an updated version. I've tried to incorporate most
> > of the feedback so far.
> >
> >
> > ---
> > GLEP: 75
> > Title: Split distfile mirror directory structure
> > Author: Micha=C5=82 G=C3=B3rny <mgorny@gentoo.org>,
> > Robin H. Johnson <robbat2@gentoo.org>
> > Type: Standards Track
> > Status: Draft
> > Version: 1
> > Created: 2018-01-26
> > Last-Modified: 2018-01-27
> > Post-History: 2018-01-27
> > Content-Type: text/x-rst
> > ---
> >
> > Abstract
> > =3D=3D=3D=3D=3D=3D=3D=3D
> > This GLEP describes the procedure for splitting the distfiles on mirror=
s
> > into multiple directories with the goal of reducing the number of files
> > in a single directory.
> >
> >
> > Motivation
> > =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
> > At the moment, both the package manager and Gentoo mirrors use flat
> > directory structure to store files. While this solution usually works,
> > it does not scale well. Directories with large number of files usually
> > have significant performance penalty, unless using filesystems
> > specifically designed for that purpose.
> >
> > According to the Gentoo repository state at 2018-01-26 16:23, there
> > was a total of 62652 unique distfiles in the repository. While
> > the users realistically hit around 10% of that, distfile mirrors often
> > hold even more files --- more so if old distfiles are not wiped
> > immediately.
> >
> > While all filesystems used on Linux boxes should be able to cope with
> > a number that large, they may suffer a performance penalty with even
> > a few thousand files. Additionally, if mirrors enable directory indexe=
s
> > then generating the index imposes both a significant server overhead
> > and a significant data transfer. At this moment, the index
> > of distfiles.gentoo.org has around 17 MiB.
> >
> > Splitting the distfiles into multiple directories makes it possible
> > to avoid those problems by reducing the number of files in a single
> > directory. For example, splitting the forementioned set of distfiles
> > into 16 directories that are roughly balanced allows to reduce
> > the number of files in a single directory to around 4000. Splitting
> > them further into 256 directories (16x16) results in 200-300 files
> > per directory which should avoid any performance problems long-term,
> > even assuming 300% growth of number of distfiles.
> >
> >
> > Specification
> > =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
> > Mirror layout file
> > ------------------
> > A mirror adhering to this specification should include a ``layout.conf`=
`
> > file in the top distfile directory. This file uses the format
> > derived from the freedesktop Desktop Entry Specification file format
> > [#DESKTOP_FORMAT]_.
> >
> > Before using each Gentoo mirror, the package manager should attempt
> > to fetch (update) its ``layout.conf`` file and process it to determine
> > how to use the mirror. If the file is not present, the package manager
> > should behave as if it were empty.
> >
> > The package manager should recognize the sections and keys listed below=
.
> > It should ignore any unrecognized sections or keys --- the format
> > is intended to account for future extensions.
> >
> > This specification currently defines one section: ``[structure]``.
> > This section defines one or more repository structure definitions
> > using non-negative sequential integer keys. The definition with
> > the ``0`` key is the most preferred structure. The package manager
> > should ignore any formats it does not recognize. If this section
> > is not present, the package manager should behave as if only ``flat``
> > structure were specified.
> >
> > The following structure definitions are supported:
> >
> > * ``flat`` to indicate the traditional flat structure where all
> > distfiles are located in the top directory,
> >
> > * ``filename-hash <algorithm> <cutoffs>`` to indicate the `filename
> > hash structure`_ explained below.
> >
> >
> > Filename hash structure
> > -----------------------
> > When using the filename hash structure, the distfiles are split
> > into directories whose names are derived from the hash of distfile
> > filename. This structure has two parameters: *algorithm name*
> > and *cutoffs* list.
> >
> > The algorithm name must correspond to a valid Manifest hash name.
> > An informational list of hashes is included in GLEP 74 [#GLEP74]_,
> > and the policies for introducing new hashes are covered by GLEP 59
> > [#GLEP59]_.
> >
> > The cutoffs list specifies one or more integers separated by colons
> > (``:``), indicating the number of bits (starting with the most
> > significant bit) of the hash used to form subsequent subdirectory names=
.
> > For example, the list of ``2:4`` would indicate that top-level director=
y
> > names are formed using 2 most significant bits of the hash (resulting
> > in 2=C2=B2 =3D 4 directories), and each of this directories would have
> > subdirectories formed using the next 4 bits of the hash (resulting
> > in 2=E2=81=B4 =3D 8 subdirectories each).
> >
> > The exact algorithm for determining the distfile location follows:
> >
> > 1. Let the distfile filename be **F**.
> >
> > 2. Compute the hash of **F** and store its binary value as **H**.
> >
> > 3. For each integer **C** in cutoff list:
> >
> > a. Take **C** most significant bits of **H** and store them as **V**=
.
> >
> > b. Convert **V** into hexadecimal integer, left padded with zeros
> > to **C/4** digits (rounded up) and append it to the path, followe=
d
> > by the path separator.
> >
> > c. Shift **H** left **C** bits.
> >
> > 4. Finally, append **F** to the obtained path.
> >
> > In particular, note that when using nested directories
> > the subdirectories do not repeat the hash bits used in parent directory=
.
> >
> >
> > Migrating mirrors to the hashed structure
> > -----------------------------------------
> > Since all distfile mirrors sync to the master Gentoo mirror, it should
> > be enough to perform all the needed changes on the master mirror
> > and wait for other mirrors to sync. The following procedure
> > is recommended:
> >
> > 1. Include the initial ``layout.conf`` listing only ``flat`` layout.
> >
> > 2. Create the new structure alongside the flat structure. Wait for
> > mirrors to sync.
> >
> > 3. Once all mirrors receive the new structure, update ``layout.conf``
> > to list the ``filename-hash`` structure.
> >
> > 4. Once a version of Portage supporting the new structure is stable lon=
g
> > enough, remove the fallback ``flat`` structure from ``layout.conf``
> > and duplicate distfiles.
> >
> > This implies that during the migration period the distfiles will
> > be stored duplicated on the mirrors and therefore will occupy twice
> > as much space. Technically, this could be avoided either by using
> > hard links or symbolic links.
> >
> > The hard link solution allows us to save space on the master mirror.
> > Additionally, if ``-H`` option is used by the mirrors it avoids
> > transferring existing files again. However, this option is known
> > to be expensive and could cause significant server load. Without it,
> > all mirrors need to transfer a second copy of all the existing files.
> >
> > The symbolic link solution could be more reliable if we could rely
> > on mirrors using the ``--links`` rsync option. Without that, symbolic
> > links are not transferred at all.
> >
> >
> > Using hashed structure for local distfiles
> > ------------------------------------------
> > The hashed structure defined above could also be used for local distfil=
e
> > storage as used by the package manager. For this to work, the package
> > manager authors need to ensure that:
> >
> > a. The ``${DISTDIR}`` variable in the ebuild scope points to a temporar=
y
> > directory where distfiles specific to the package are linked
> > in a flat structure.
> >
> > b. All tools are updated to support the nested structure.
> >
> > c. The package manager provides a tool for users to easily manipulate
> > distfiles, in particular to add distfiles for fetch-restricted
> > packages into an appropriate subdirectory.
> >
> > For extended compatibility, the package manager may support finding
> > distfiles in flat and nested structure simultaneously.
> >
> >
> > Rationale
> > =3D=3D=3D=3D=3D=3D=3D=3D=3D
> > Algorithm for splitting distfiles
> > ---------------------------------
> > The possible algorithms were considered with the following goals
> > in mind:
> >
> > - the number of files in a single directory should not exceed 1000,
> >
> > - the total size of files in a single directory is not considered
> > relevant,
> >
> > - the solution should preferably be future-proof,
> >
> > - moving distfiles should be avoided once it is deployed.
> >
> > It should also be noted that at this moment the package having most
> > distfiles in Gentoo at the time is dev-texlive/texlive-latexextra,
> > with the number of 8556 distfiles. All of them start with a common
> > prefix of ``texlive-module-``. This specific prefix is used by a total
> > of 23435 distfiles.
> >
> > In the original debate that occurred in bug #534528 [#BUG534528]_
> > and the mailing list review of the initial version of this GLEP [#ML1]_=
,
> > four fundamental ideas for splitting distfiles were listed:
> >
> > a. using initial portion of filename,
> >
> > b. using initial portion of file hash,
> >
> > c. using initial portion of filename hash,
> >
> > d. using package category (and package name).
> >
> > The initial filename idea was to use the first character of filename,
> > possibly followed by a longer part which was the idea historically
> > used e.g. by PyPI Python package hosting. Its main advantage is
> > simplicity. The users can easily determine the correct subdirectory
> > by just looking at the distfile name. Sadly, this solution is not only
> > very uneven but does not solve the problem. As mentioned above,
> > the Te=CE=A7 Live packages share a long common prefix that make it impo=
ssible
> > to split it properly with other packages on fixed-length prefixes.
> >
> > This idea has been followed by an adaptive proposal by Andrew Barchuk
> > [#ADAPTIVE_FILENAME]_. In this proposal, the filenames are not strictl=
y
> > mapped to groups by a common prefix but instead each group contains
> > all files between two prefixes being used (like in a dictionary).
> > However, it has been pointed out that while this option can provide
> > very even results initially, it is impossible to predict how it would
> > be affected by future distfile changes and there will be a risk of
> > needing to change the groups in the future. Furthermore, it is
> > relatively complex and requires explicitly listing or obtaining used
> > groups.
> >
> > Another option was to use an initial portion of distfile hashes. Its
> > main advantage is that cryptographic hash algorithms can provide
> > a more balanced split with random data. Furthermore, since hashes are
> > stored in Manifests using them has no cost for users. However, this
> > solution has three disadvantages:
> >
> > 1. Not all files in the distfile tree are covered by package Manifests.
> > Additional files are injected into the mirrors, and those will
> > not have a clearly-defined location.
> >
> > 2. User-provided distfiles (e.g. for fetch-restricted packages) with
> > hash mismatches would be placed in the wrong subdirectory,
> > potentially causing confusing errors.
> >
> > 3. The hash values are unknown for newly-downloaded distfiles, so
> > ``repoman`` (or an equivalent tool) would have to use a temporary
> > directory before locating the file in appropriate subdirectory.
> >
> > Using filename hashes has proven to provide a similar balance to using
> > file hashes. Furthermore, since filenames are known up front this
> > solution does not suffer from the listed problems. While hashes need
> > to be computed manually, hashing short string should not cause
> > any performance problems.
> >
> > Jason Zaman has suggested to use package categories (and package names)
> > [#PKGNAME]_. However, this solution has multiple problems:
> >
> > a. it does not solve the problem for large packages such as Te=CE=A7 Li=
ve,
> >
> > b. it introduces many unnecessarily small directories,
> >
> > c. it requires an explicit knowledge of which package distfiles
> > belong to,
> >
> > d. it does not provide an explicit solution to the problem of distfiles
> > shared by multiple packages,
> >
> > e. it does not provide a solution to the problem of injected distfiles.
> >
> > All the options considered, the filename hash solution was selected
> > as one that solves all the forementioned problems while introducing
> > relatively low complexity and being reasonably future-proof.
> >
> > .. figure:: glep-0075-extras/by-filename.png
> >
> > Distribution of distfiles by first character of filenames
> > (note: y axis is on log scale)
> >
> > .. figure:: glep-0075-extras/by-csum.png
> >
> > Distribution of distfiles by first hex-digit of checksum
> > (x --- content checksum, + --- filename checksum)
> >
> > .. figure:: glep-0075-extras/by-csum2.png
> >
> > Distribution of distfiles by two first hex-digits of checksum
> > (x --- content checksum, + --- filename checksum)
> >
> >
> > Layout file
> > -----------
> > The presence of control file has been suggested in the original
> > discussion. Its main purpose is to let package managers cleanly handle
> > the migration and detect how to correctly query the mirrors throughout
> > it. Furthermore, it makes future changes easier.
> >
> > The format lines specifically mean to hardcode as little about
> > the actual algorithm as possible. Therefore, we can easily change
> > the hash used or the exact split structure without having to update
> > the package managers or even provide a compatibility layout.
> >
> > The file is also open for future extensions to provide additional mirro=
r
> > metadata. However, no clear use for that has been determined so far.
> >
> >
> > Hash algorithm
> > --------------
> > The hash algorithm support is fully deferred to the existing code
> > in the package managers that is required to handle Manifests.
> > In particular, it is recommended to reuse one of the hashes that are
> > used in Manifest entries at the time. This avoids code duplication
> > and reuses an existing mechanism to handle hash upgrades.
> >
> > During the discussion, it has been pointed that this particular use cas=
e
> > does not require a cryptographically strong hash and a faster algorithm
> > could be used instead. However, given the short length of hashed
> > strings performance is not a problem, and speed does not justify
> > the resulting code duplication.
> >
> > It has also been pointed out that e.g. the BLAKE2 hash family provides
> > the ability of creating arbitrary length hashes instead of truncating
> > the standard-length hash. However, not all implementations of BLAKE2
> > support that and relying on it could reduce portability for no apparent
> > gain.
> >
> >
> > Backwards Compatibility
> > =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
> > Mirror compatibility
> > --------------------
> > The mirrored files are propagated to other mirrors as opaque directory
> > structure. Therefore, there are no backwards compatibility concerns
> > on the mirroring side.
> >
> > Backwards compatibility with existing clients is detailed
> > in `migrating mirrors to the hashed structure`_ section. Backwards
> > compatibility with the old clients will be provided by preserving
> > the flat structure during the transitional period.
> >
> > The new clients will fetch the ``layout.conf`` file to avoid backwards
> > compatibility concerns in the future. In case of hitting an old mirror=
,
> > the package manager will default to the ``flat`` structure.
> >
> >
> > Package manager storage compatibility
> > -------------------------------------
> > The exact means of preserving backwards compatibility in package manage=
r
> > storage are left to the package manager authors. However, it is
> > recommended that package managers continue to support the flat layout
> > even if it is no longer the default. The package manager may either
> > continue to read files from this location or automatically move them
> > to an appropriate subdirectory.
> >
> >
> > Reference Implementation
> > =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D
> > TODO.
> >
> >
> > References
> > =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
> > .. [#DESKTOP_FORMAT] Desktop Entry Specification: Basic format of the
> file
> > (https://standards.freedesktop.org/desktop-entry-
> spec/latest/ar01s03.html)
> >
> > .. [#GLEP74] GLEP 74: Full-tree verification using Manifest files:
> > Checksum algorithms (informational)
> > (https://www.gentoo.org/glep/glep-0074.html#checksum-
> algorithms-informational)
> >
> > .. [#GLEP59] GLEP 59: Manifest2 hash policies and security implications
> > (https://www.gentoo.org/glep/glep-0059.html)
> >
> > .. [#BUG534528] Bug 534528 - distfiles should be sorted into
> subdirectories
> > of DISTDIR
> > (https://bugs.gentoo.org/534528)
> >
> > .. [#ML1] [gentoo-dev] [pre-GLEP] Split distfile mirror directory
> structure
> > (https://archives.gentoo.org/gentoo-dev/message/
> cfc4f8595df2edf9a25ba9ecae2463ba)
> >
> > .. [#ADAPTIVE_FILENAME] Andrew Barchuk's reply on 'using character rang=
es
> > for each directory computed in a way to have the files distributed
> evenly'
> > (https://archives.gentoo.org/gentoo-dev/message/
> 611bdaa76be049c1d650e8995748e7b8)
> >
> > .. [#PKGNAME] Jason Zamal's reply including 'using the same dir layout
> > as the packages themselves)
> > (https://archives.gentoo.org/gentoo-dev/message/
> f26ed870c3a6d4ecf69a821723642975)
> >
> >
> > Copyright
> > =3D=3D=3D=3D=3D=3D=3D=3D=3D
> > This work is licensed under the Creative Commons Attribution-ShareAlike
> 3.0
> > Unported License. To view a copy of this license, visit
> > http://creativecommons.org/licenses/by-sa/3.0/.
> >
> > --
> > Best regards,
> > Micha=C5=82 G=C3=B3rny
> >
>
> It's going to be hash based? Why? I tried to follow the conversation but
> there's now close to 5 of these posts in the mailing list with different
> conversations in each.
>
The reasoning is embedded in the proposal; search for "Algorithm for
splitting distfiles". Read that section. I think it summarizes the space
well.
-A
>
> Using filename prefixes is boring and not uniform, but I feel I should
> point out that most distfile hosts are still doing fine. Microoptimizing
> this seems like wasted effort.
>
> Cheers,
> R0b0t1
--001a1143fa4014fcaf0563f08962
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quote">On M=
on, Jan 29, 2018 at 3:26 PM, R0b0t1 <span dir=3D"ltr"><<a href=3D"mailto=
:r030t1@gmail.com" target=3D"_blank">r030t1@gmail.com</a>></span> wrote:=
<br><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;bor=
der-left:1px solid rgb(204,204,204);padding-left:1ex"><div class=3D"gmail-H=
OEnZb"><div class=3D"gmail-h5">On Monday, January 29, 2018, Micha=C5=82 G=
=C3=B3rny <<a href=3D"mailto:mgorny@gentoo.org" target=3D"_blank">mgorny=
@gentoo.org</a>> wrote:<br>> Here's an updated version. I've =
tried to incorporate most<br>> of the feedback so far.<br>><br>><b=
r>> ---<br>> GLEP: 75<br>> Title: Split distfile mirror directory =
structure<br>> Author: Micha=C5=82 G=C3=B3rny <<a href=3D"mailto:mgor=
ny@gentoo.org" target=3D"_blank">mgorny@gentoo.org</a>>,<br>> =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 Robin H. Johnson <<a href=3D"mailto:robbat2@gentoo.=
org" target=3D"_blank">robbat2@gentoo.org</a>><br>> Type: Standards T=
rack<br>> Status: Draft<br>> Version: 1<br>> Created: 2018-01-26<b=
r>> Last-Modified: 2018-01-27<br>> Post-History: 2018-01-27<br>> C=
ontent-Type: text/x-rst<br>> ---<br>><br>> Abstract<br>> =3D=3D=
=3D=3D=3D=3D=3D=3D<br>> This GLEP describes the procedure for splitting =
the distfiles on mirrors<br>> into multiple directories with the goal of=
reducing the number of files<br>> in a single directory.<br>><br>>=
;<br>> Motivation<br>> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D<br>> At the =
moment, both the package manager and Gentoo mirrors use flat<br>> direct=
ory structure to store files.=C2=A0 While this solution usually works,<br>&=
gt; it does not scale well.=C2=A0 Directories with large number of files us=
ually<br>> have significant performance penalty, unless using filesystem=
s<br>> specifically designed for that purpose.<br>><br>> According=
to the Gentoo repository state at 2018-01-26 16:23, there<br>> was a to=
tal of 62652 unique distfiles in the repository.=C2=A0 While<br>> the us=
ers realistically hit around 10% of that, distfile mirrors often<br>> ho=
ld even more files --- more so if old distfiles are not wiped<br>> immed=
iately.<br>><br>> While all filesystems used on Linux boxes should be=
able to cope with<br>> a number that large, they may suffer a performan=
ce penalty with even<br>> a few thousand files.=C2=A0 Additionally, if m=
irrors enable directory indexes<br>> then generating the index imposes b=
oth a significant server overhead<br>> and a significant data transfer.=
=C2=A0 At this moment, the index<br>> of <a href=3D"http://distfiles.gen=
too.org" target=3D"_blank">distfiles.gentoo.org</a> has around 17 MiB.<br>&=
gt;<br>> Splitting the distfiles into multiple directories makes it poss=
ible<br>> to avoid those problems by reducing the number of files in a s=
ingle<br>> directory.=C2=A0 For example, splitting the forementioned set=
of distfiles<br>> into 16 directories that are roughly balanced allows =
to reduce<br>> the number of files in a single directory to around 4000.=
=C2=A0 Splitting<br>> them further into 256 directories (16x16) results =
in 200-300 files<br>> per directory which should avoid any performance p=
roblems long-term,<br>> even assuming 300% growth of number of distfiles=
.<br>><br>><br>> Specification<br>> =3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D<br>> Mirror layout file<br>> ------------------<br>> =
A mirror adhering to this specification should include a ``layout.conf``<br=
>> file in the top distfile directory.=C2=A0 This file uses the format<b=
r>> derived from the freedesktop Desktop Entry Specification file format=
<br>> [#DESKTOP_FORMAT]_.<br>><br>> Before using each Gentoo mirro=
r, the package manager should attempt<br>> to fetch (update) its ``layou=
t.conf`` file and process it to determine<br>> how to use the mirror.=C2=
=A0 If the file is not present, the package manager<br>> should behave a=
s if it were empty.<br>><br>> The package manager should recognize th=
e sections and keys listed below.<br>> It should ignore any unrecognized=
sections or keys --- the format<br>> is intended to account for future =
extensions.<br>><br>> This specification currently defines one sectio=
n: ``[structure]``.<br>> This section defines one or more repository str=
ucture definitions<br>> using non-negative sequential integer keys.=C2=
=A0 The definition with<br>> the ``0`` key is the most preferred structu=
re.=C2=A0 The package manager<br>> should ignore any formats it does not=
recognize.=C2=A0 If this section<br>> is not present, the package manag=
er should behave as if only ``flat``<br>> structure were specified.<br>&=
gt;<br>> The following structure definitions are supported:<br>><br>&=
gt; * ``flat`` to indicate the traditional flat structure where all<br>>=
=C2=A0 distfiles are located in the top directory,<br>><br>> * ``fil=
ename-hash <algorithm> <cutoffs>`` to indicate the `filename<br=
>> =C2=A0 hash structure`_ explained below.<br>><br>><br>> File=
name hash structure<br>> -----------------------<br>> When using the =
filename hash structure, the distfiles are split<br>> into directories w=
hose names are derived from the hash of distfile<br>> filename.=C2=A0 Th=
is structure has two parameters: *algorithm name*<br>> and *cutoffs* lis=
t.<br>><br>> The algorithm name must correspond to a valid Manifest h=
ash name.<br>> An informational list of hashes is included in GLEP 74 [#=
GLEP74]_,<br>> and the policies for introducing new hashes are covered b=
y GLEP 59<br>> [#GLEP59]_.<br>><br>> The cutoffs list specifies on=
e or more integers separated by colons<br>> (``:``), indicating the numb=
er of bits (starting with the most<br>> significant bit) of the hash use=
d to form subsequent subdirectory names.<br>> For example, the list of `=
`2:4`` would indicate that top-level directory<br>> names are formed usi=
ng 2 most significant bits of the hash (resulting<br>> in 2=C2=B2 =3D 4 =
directories), and each of this directories would have<br>> subdirectorie=
s formed using the next 4 bits of the hash (resulting<br>> in 2=E2=81=B4=
=3D 8 subdirectories each).<br>><br>> The exact algorithm for determ=
ining the distfile location follows:<br>><br>> 1. Let the distfile fi=
lename be **F**.<br>><br>> 2. Compute the hash of **F** and store its=
binary value as **H**.<br>><br>> 3. For each integer **C** in cutoff=
list:<br>><br>> =C2=A0 =C2=A0a. Take **C** most significant bits of =
**H** and store them as **V**.<br>><br>> =C2=A0 =C2=A0b. Convert **V*=
* into hexadecimal integer, left padded with zeros<br>> =C2=A0 =C2=A0 =
=C2=A0 to **C/4** digits (rounded up) and append it to the path, followed<b=
r>> =C2=A0 =C2=A0 =C2=A0 by the path separator.<br>><br>> =C2=A0 =
=C2=A0c. Shift **H** left **C** bits.<br>><br>> 4. Finally, append **=
F** to the obtained path.<br>><br>> In particular, note that when usi=
ng nested directories<br>> the subdirectories do not repeat the hash bit=
s used in parent directory.<br>><br>><br>> Migrating mirrors to th=
e hashed structure<br>> ------------------------------<wbr>-----------<b=
r>> Since all distfile mirrors sync to the master Gentoo mirror, it shou=
ld<br>> be enough to perform all the needed changes on the master mirror=
<br>> and wait for other mirrors to sync.=C2=A0 The following procedure<=
br>> is recommended:<br>><br>> 1. Include the initial ``layout.con=
f`` listing only ``flat`` layout.<br>><br>> 2. Create the new structu=
re alongside the flat structure. Wait for<br>> =C2=A0 =C2=A0mirrors to s=
ync.<br>><br>> 3. Once all mirrors receive the new structure, update =
``layout.conf``<br>> =C2=A0 =C2=A0to list the ``filename-hash`` structur=
e.<br>><br>> 4. Once a version of Portage supporting the new structur=
e is stable long<br>> =C2=A0 =C2=A0enough, remove the fallback ``flat`` =
structure from ``layout.conf``<br>> =C2=A0 =C2=A0and duplicate distfiles=
.<br>><br>> This implies that during the migration period the distfil=
es will<br>> be stored duplicated on the mirrors and therefore will occu=
py twice<br>> as much space.=C2=A0 Technically, this could be avoided ei=
ther by using<br>> hard links or symbolic links.<br>><br>> The har=
d link solution allows us to save space on the master mirror.<br>> Addit=
ionally, if ``-H`` option is used by the mirrors it avoids<br>> transfer=
ring existing files again.=C2=A0 However, this option is known<br>> to b=
e expensive and could cause significant server load.=C2=A0 Without it,<br>&=
gt; all mirrors need to transfer a second copy of all the existing files.<b=
r>><br>> The symbolic link solution could be more reliable if we coul=
d rely<br>> on mirrors using the ``--links`` rsync option.=C2=A0 Without=
that, symbolic<br>> links are not transferred at all.<br>><br>><b=
r>> Using hashed structure for local distfiles<br>> -----------------=
-------------<wbr>------------<br>> The hashed structure defined above c=
ould also be used for local distfile<br>> storage as used by the package=
manager.=C2=A0 For this to work, the package<br>> manager authors need =
to ensure that:<br>><br>> a. The ``${DISTDIR}`` variable in the ebuil=
d scope points to a temporary<br>> =C2=A0 =C2=A0directory where distfile=
s specific to the package are linked<br>> =C2=A0 =C2=A0in a flat structu=
re.<br>><br>> b. All tools are updated to support the nested structur=
e.<br>><br>> c. The package manager provides a tool for users to easi=
ly manipulate<br>> =C2=A0 =C2=A0distfiles, in particular to add distfile=
s for fetch-restricted<br>> =C2=A0 =C2=A0packages into an appropriate su=
bdirectory.<br>><br>> For extended compatibility, the package manager=
may support finding<br>> distfiles in flat and nested structure simulta=
neously.<br>><br>><br>> Rationale<br>> =3D=3D=3D=3D=3D=3D=3D=3D=
=3D<br>> Algorithm for splitting distfiles<br>> ---------------------=
---------<wbr>---<br>> The possible algorithms were considered with the =
following goals<br>> in mind:<br>><br>> - the number of files in a=
single directory should not exceed 1000,<br>><br>> - the total size =
of files in a single directory is not considered<br>> =C2=A0 relevant,<b=
r>><br>> - the solution should preferably be future-proof,<br>><br=
>> - moving distfiles should be avoided once it is deployed.<br>><br>=
> It should also be noted that at this moment the package having most<br=
>> distfiles in Gentoo at the time is dev-texlive/texlive-<wbr>latexextr=
a,<br>> with the number of 8556 distfiles.=C2=A0 All of them start with =
a common<br>> prefix of ``texlive-module-``.=C2=A0 This specific prefix =
is used by a total<br>> of 23435 distfiles.<br>><br>> In the origi=
nal debate that occurred in bug #534528 [#BUG534528]_<br>> and the maili=
ng list review of the initial version of this GLEP [#ML1]_,<br>> four fu=
ndamental ideas for splitting distfiles were listed:<br>><br>> a. usi=
ng initial portion of filename,<br>><br>> b. using initial portion of=
file hash,<br>><br>> c. using initial portion of filename hash,<br>&=
gt;<br>> d. using package category (and package name).<br>><br>> T=
he initial filename idea was to use the first character of filename,<br>>=
; possibly followed by a longer part which was the idea historically<br>>=
; used e.g. by PyPI Python package hosting.=C2=A0 Its main advantage is<br>=
> simplicity.=C2=A0 The users can easily determine the correct subdirect=
ory<br>> by just looking at the distfile name.=C2=A0 Sadly, this solutio=
n is not only<br>> very uneven but does not solve the problem.=C2=A0 As =
mentioned above,<br>> the Te=CE=A7 Live packages share a long common pre=
fix that make it impossible<br>> to split it properly with other package=
s on fixed-length prefixes.<br>><br>> This idea has been followed by =
an adaptive proposal by Andrew Barchuk<br>> [#ADAPTIVE_FILENAME]_.=C2=A0=
In this proposal, the filenames are not strictly<br>> mapped to groups =
by a common prefix but instead each group contains<br>> all files betwee=
n two prefixes being used (like in a dictionary).<br>> However, it has b=
een pointed out that while this option can provide<br>> very even result=
s initially, it is impossible to predict how it would<br>> be affected b=
y future distfile changes and there will be a risk of<br>> needing to ch=
ange the groups in the future.=C2=A0 Furthermore, it is<br>> relatively =
complex and requires explicitly listing or obtaining used<br>> groups.<b=
r>><br>> Another option was to use an initial portion of distfile has=
hes.=C2=A0 Its<br>> main advantage is that cryptographic hash algorithms=
can provide<br>> a more balanced split with random data.=C2=A0 Furtherm=
ore, since hashes are<br>> stored in Manifests using them has no cost fo=
r users.=C2=A0 However, this<br>> solution has three disadvantages:<br>&=
gt;<br>> 1. Not all files in the distfile tree are covered by package Ma=
nifests.<br>> =C2=A0 =C2=A0Additional files are injected into the mirror=
s, and those will<br>> =C2=A0 =C2=A0not have a clearly-defined location.=
<br>><br>> 2. User-provided distfiles (e.g. for fetch-restricted pack=
ages) with<br>> =C2=A0 =C2=A0hash mismatches would be placed in the wron=
g subdirectory,<br>> =C2=A0 =C2=A0potentially causing confusing errors.<=
br>><br>> 3. The hash values are unknown for newly-downloaded distfil=
es, so<br>> =C2=A0 =C2=A0``repoman`` (or an equivalent tool) would have =
to use a temporary<br>> =C2=A0 =C2=A0directory before locating the file =
in appropriate subdirectory.<br>><br>> Using filename hashes has prov=
en to provide a similar balance to using<br>> file hashes.=C2=A0 Further=
more, since filenames are known up front this<br>> solution does not suf=
fer from the listed problems.=C2=A0 While hashes need<br>> to be compute=
d manually, hashing short string should not cause<br>> any performance p=
roblems.<br>><br>> Jason Zaman has suggested to use package categorie=
s (and package names)<br>> [#PKGNAME]_.=C2=A0 However, this solution has=
multiple problems:<br>><br>> a. it does not solve the problem for la=
rge packages such as Te=CE=A7 Live,<br>><br>> b. it introduces many u=
nnecessarily small directories,<br>><br>> c. it requires an explicit =
knowledge of which package distfiles<br>> =C2=A0 =C2=A0belong to,<br>>=
;<br>> d. it does not provide an explicit solution to the problem of dis=
tfiles<br>> =C2=A0 =C2=A0shared by multiple packages,<br>><br>> e.=
it does not provide a solution to the problem of injected distfiles.<br>&g=
t;<br>> All the options considered, the filename hash solution was selec=
ted<br>> as one that solves all the forementioned problems while introdu=
cing<br>> relatively low complexity and being reasonably future-proof.<b=
r>><br>> .. figure:: glep-0075-extras/by-filename.<wbr>png<br>><br=
>> =C2=A0 =C2=A0Distribution of distfiles by first character of filename=
s<br>> =C2=A0 =C2=A0(note: y axis is on log scale)<br>><br>> .. fi=
gure:: glep-0075-extras/by-csum.png<br>><br>> =C2=A0 =C2=A0Distributi=
on of distfiles by first hex-digit of checksum<br>> =C2=A0 =C2=A0(x --- =
content checksum, + --- filename checksum)<br>><br>> .. figure:: glep=
-0075-extras/by-csum2.png<br>><br>> =C2=A0 =C2=A0Distribution of dist=
files by two first hex-digits of checksum<br>> =C2=A0 =C2=A0(x --- conte=
nt checksum, + --- filename checksum)<br>><br>><br>> Layout file<b=
r>> -----------<br>> The presence of control file has been suggested =
in the original<br>> discussion.=C2=A0 Its main purpose is to let packag=
e managers cleanly handle<br>> the migration and detect how to correctly=
query the mirrors throughout<br>> it.=C2=A0 Furthermore, it makes futur=
e changes easier.<br>><br>> The format lines specifically mean to har=
dcode as little about<br>> the actual algorithm as possible.=C2=A0 There=
fore, we can easily change<br>> the hash used or the exact split structu=
re without having to update<br>> the package managers or even provide a =
compatibility layout.<br>><br>> The file is also open for future exte=
nsions to provide additional mirror<br>> metadata.=C2=A0 However, no cle=
ar use for that has been determined so far.<br>><br>><br>> Hash al=
gorithm<br>> --------------<br>> The hash algorithm support is fully =
deferred to the existing code<br>> in the package managers that is requi=
red to handle Manifests.<br>> In particular, it is recommended to reuse =
one of the hashes that are<br>> used in Manifest entries at the time.=C2=
=A0 This avoids code duplication<br>> and reuses an existing mechanism t=
o handle hash upgrades.<br>><br>> During the discussion, it has been =
pointed that this particular use case<br>> does not require a cryptograp=
hically strong hash and a faster algorithm<br>> could be used instead.=
=C2=A0 However, given the short length of hashed<br>> strings performanc=
e is not a problem, and speed does not justify<br>> the resulting code d=
uplication.<br>><br>> It has also been pointed out that e.g. the BLAK=
E2 hash family provides<br>> the ability of creating arbitrary length ha=
shes instead of truncating<br>> the standard-length hash.=C2=A0 However,=
not all implementations of BLAKE2<br>> support that and relying on it c=
ould reduce portability for no apparent<br>> gain.<br>><br>><br>&g=
t; Backwards Compatibility<br>> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D<br>> Mirror compatibility<br>> -------=
-------------<br>> The mirrored files are propagated to other mirrors as=
opaque directory<br>> structure.=C2=A0 Therefore, there are no backward=
s compatibility concerns<br>> on the mirroring side.<br>><br>> Bac=
kwards compatibility with existing clients is detailed<br>> in `migratin=
g mirrors to the hashed structure`_ section.=C2=A0 Backwards<br>> compat=
ibility with the old clients will be provided by preserving<br>> the fla=
t structure during the transitional period.<br>><br>> The new clients=
will fetch the ``layout.conf`` file to avoid backwards<br>> compatibili=
ty concerns in the future.=C2=A0 In case of hitting an old mirror,<br>> =
the package manager will default to the ``flat`` structure.<br>><br>>=
<br>> Package manager storage compatibility<br>> --------------------=
----------<wbr>-------<br>> The exact means of preserving backwards comp=
atibility in package manager<br>> storage are left to the package manage=
r authors.=C2=A0 However, it is<br>> recommended that package managers c=
ontinue to support the flat layout<br>> even if it is no longer the defa=
ult.=C2=A0 The package manager may either<br>> continue to read files fr=
om this location or automatically move them<br>> to an appropriate subdi=
rectory.<br>><br>><br>> Reference Implementation<br>> =3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D<br>> TOD=
O.<br>><br>><br>> References<br>> =3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D<br>> .. [#DESKTOP_FORMAT] Desktop Entry Specification: Basic format =
of the file<br>> =C2=A0 =C2=A0(<a href=3D"https://standards.freedesktop.=
org/desktop-entry-spec/latest/ar01s03.html" target=3D"_blank">https://stand=
ards.<wbr>freedesktop.org/desktop-entry-<wbr>spec/latest/ar01s03.html</a>)<=
br>><br>> .. [#GLEP74] GLEP 74: Full-tree verification using Manifest=
files:<br>> =C2=A0 =C2=A0Checksum algorithms (informational)<br>> =
=C2=A0 =C2=A0(<a href=3D"https://www.gentoo.org/glep/glep-0074.html#checksu=
m-algorithms-informational" target=3D"_blank">https://www.gentoo.org/glep/<=
wbr>glep-0074.html#checksum-<wbr>algorithms-informational</a>)<br>><br>&=
gt; .. [#GLEP59] GLEP 59: Manifest2 hash policies and security implications=
<br>> =C2=A0 =C2=A0(<a href=3D"https://www.gentoo.org/glep/glep-0059.htm=
l" target=3D"_blank">https://www.gentoo.org/glep/<wbr>glep-0059.html</a>)<b=
r>><br>> .. [#BUG534528] Bug 534528 - distfiles should be sorted into=
subdirectories<br>> =C2=A0 =C2=A0of DISTDIR<br>> =C2=A0 =C2=A0(<a hr=
ef=3D"https://bugs.gentoo.org/534528" target=3D"_blank">https://bugs.gentoo=
.org/<wbr>534528</a>)<br>><br>> .. [#ML1] [gentoo-dev] [pre-GLEP] Spl=
it distfile mirror directory structure<br>> =C2=A0 =C2=A0(<a href=3D"htt=
ps://archives.gentoo.org/gentoo-dev/message/cfc4f8595df2edf9a25ba9ecae2463b=
a" target=3D"_blank">https://archives.gentoo.org/<wbr>gentoo-dev/message/<w=
br>cfc4f8595df2edf9a25ba9ecae2463<wbr>ba</a>)<br>><br>> .. [#ADAPTIVE=
_FILENAME] Andrew Barchuk's reply on 'using character ranges<br>>=
; =C2=A0 =C2=A0for each directory computed in a way to have the files distr=
ibuted evenly'<br>> =C2=A0 =C2=A0(<a href=3D"https://archives.gentoo=
.org/gentoo-dev/message/611bdaa76be049c1d650e8995748e7b8" target=3D"_blank"=
>https://archives.gentoo.org/<wbr>gentoo-dev/message/<wbr>611bdaa76be049c1d=
650e8995748e7<wbr>b8</a>)<br>><br>> .. [#PKGNAME] Jason Zamal's r=
eply including 'using the same dir layout<br>> =C2=A0 =C2=A0as the p=
ackages themselves)<br>> =C2=A0 =C2=A0(<a href=3D"https://archives.gento=
o.org/gentoo-dev/message/f26ed870c3a6d4ecf69a821723642975" target=3D"_blank=
">https://archives.gentoo.org/<wbr>gentoo-dev/message/<wbr>f26ed870c3a6d4ec=
f69a8217236429<wbr>75</a>)<br>><br>><br>> Copyright<br>> =3D=3D=
=3D=3D=3D=3D=3D=3D=3D<br>> This work is licensed under the Creative Comm=
ons Attribution-ShareAlike 3.0<br>> Unported License. To view a copy of =
this license, visit<br>> <a href=3D"http://creativecommons.org/licenses/=
by-sa/3.0/" target=3D"_blank">http://creativecommons.org/<wbr>licenses/by-s=
a/3.0/</a>.<br>><br>> --<br>> Best regards,<br>> Micha=C5=82 G=
=C3=B3rny<br>><br><br></div></div>It's going to be hash based? Why? =
I tried to follow the conversation but there's now close to 5 of these =
posts in the mailing list with different conversations in each.<br></blockq=
uote><div><br></div>The reasoning is embedded in the proposal; search for &=
quot;Algorithm for splitting distfiles". Read that section. I think it=
summarizes the space well.</div><div class=3D"gmail_quote"><div><br></div>=
<div>-A</div><div>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"ma=
rgin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:=
1ex"><br>Using filename prefixes is boring and not uniform, but I feel I sh=
ould point out that most distfile hosts are still doing fine. Microoptimizi=
ng this seems like wasted effort.<br><br>Cheers,<br> =C2=A0 =C2=A0 R0b0t1
</blockquote></div><br></div></div>
--001a1143fa4014fcaf0563f08962--