[gentoo-commits] data/glep:glep-mirrors commit in: /

[Michał Górny]

commit:     e4dc2627c8107339b13e20709125e2d9fc91ffde
Author:     Michał Górny <mgorny <AT> gentoo <DOT> org>
AuthorDate: Wed Feb  7 13:20:45 2018 +0000
Commit:     Michał Górny <mgorny <AT> gentoo <DOT> org>
CommitDate: Wed Feb  7 13:22:08 2018 +0000
URL:        https://gitweb.gentoo.org/data/glep.git/commit/?id=e4dc2627

glep-0075: Extend rationale for splitting algorithm

Extend and refactor the rationale for splitting algorithm. Explicitly
state the goals, list all the options that occurred during the ml
discussion.

 glep-0075.rst | 116 +++++++++++++++++++++++++++++++++++++++++++++-------------
 1 file changed, 91 insertions(+), 25 deletions(-)

diff --git a/glep-0075.rst b/glep-0075.rst
index 157514e..00d14c3 100644
--- a/glep-0075.rst
+++ b/glep-0075.rst
@@ -187,43 +187,98 @@ Rationale
 =========
 Algorithm for splitting distfiles
 ---------------------------------
-In the original debate that occurred in bug #534528 [#BUG534528]_,
-three possible solutions for splitting distfiles were listed:
+The possible algorithms were considered with the following goals
+in mind:
 
-a. using initial portion of filename,
+- the number of files in a single directory should not exceed 1000,
 
-b. using initial portion of file hash,
+- the total size of files in a single directory is not considered
+  relevant,
 
-c. using initial portion of filename hash.
+- the solution should preferably be future-proof,
 
-The significant advantage of the filename option was simplicity.  With
-that solution, the users could easily determine the correct subdirectory
-themselves.  However, it's significant disadvantage was very uneven
-shuffling of data.  In particular, the TeΧ Live packages alone count
-almost 23500 distfiles and all use a common prefix, making it impossible
-to split them further.
+- moving distfiles should be avoided once it is deployed.
 
-The alternate option of using file hash has the advantage of having
-a more balanced split.  Furthermore, since hashes are stored
-in Manifests using them is zero-cost.  However, this solution has three
-significant disadvantages:
+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.
 
-1. 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.
+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Χ Live packages share a long common prefix that make it impossible
+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 strictly
+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. Not all files in the distfiles tree are covered by package Manifests
-   --- there are additional files that are injected into distfiles.
+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 both listed problems.  While
-hashes need to be computed manually, hashing short string should not
-cause any performance problems.
+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Χ Live,
+
+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
 
@@ -327,6 +382,17 @@ References
    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 ranges
+   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
 =========