[devel] статистика [2]

[Alexey Tourbin <at@altlinux.ru>]

[-- Attachment #1: Type: text/plain, Size: 10423 bytes --]

On Thu, Aug 23, 2007 at 05:23:04PM +0400, Alexey Tourbin wrote:
> 5) Теперь этот вывод несложно обработать скриптом print-uris-filter.awk,
> чтобы на выходе получить таблицу
> <src-rpm-basename> <inst-rpm-basename>
> Эта таблица означает, что для src.rpm пакета <src-rpm-basename>
> в билдрут будет ставиться собранный rpm пакет <inst-rpm-basename>.
> 
> $ head .pR >.pR1
> $ PATH=$PWD:$PATH $TMPDIR/build/aptbox/apt-get -qq -y script ./print-uris.lua <.pR1 >.uris
> $ awk -f ./print-uris-filter.awk .uris |head    
> 7colors-0.80-alt5.src.rpm       glib-1.2.10-alt12.i586.rpm
> 7colors-0.80-alt5.src.rpm       libORBit-0.5.17-alt3.i586.rpm
> 7colors-0.80-alt5.src.rpm       ORBit-0.5.17-alt3.i586.rpm
> 7colors-0.80-alt5.src.rpm       libfontenc-1.0.4-alt1.i586.rpm
> 7colors-0.80-alt5.src.rpm       libfreetype-2.3.5-alt2.i586.rpm
> 7colors-0.80-alt5.src.rpm       libXfont-1.2.8-alt2.i586.rpm
> 7colors-0.80-alt5.src.rpm       bdftopcf-1.0.1-alt1.i586.rpm
> 7colors-0.80-alt5.src.rpm       libdb1-1.85-alt5.i586.rpm
> 7colors-0.80-alt5.src.rpm       db1-utils-1.85-alt5.i586.rpm
> 7colors-0.80-alt5.src.rpm       libaudiofile-0.2.6-alt2.i586.rpm
> $ awk -f ./print-uris-filter.awk .uris |sort -u -k1,1
> 7colors-0.80-alt5.src.rpm       glib-1.2.10-alt12.i586.rpm
> a2ps-4.13-alt3.src.rpm  libfontenc-1.0.4-alt1.i586.rpm
> aalib-1.4-alt2rc5.src.rpm       libX11-locales-1.1.3-alt3.i586.rpm
> abinit-4.6.5-alt1.src.rpm       gcc-fortran-common-1.4.10-alt2.i586.rpm
> abiword-2.4.6-alt2.src.rpm      libIDL-0.8.8-alt1.i586.rpm
> abook-0.5.6-alt1.src.rpm        libtinfo-devel-5.6-alt3.i586.rpm
> abuse_sdl-0.7.0-alt4.src.rpm    ca-certificates-2007.02.06-alt1.noarch.rpm
> acidrip-0.14-alt1.src.rpm       ca-certificates-2007.02.06-alt1.noarch.rpm
> acl-2.2.39-alt1.0.src.rpm       libattr-devel-2.4.32-alt1.0.i586.rpm
> $
> 
> Теперь задача почти решена.  Мы имеем вновь пришедшие пакеты
> <inst-rpm-basename>, и хотим узнать, какие <src-rpm-basename>
> подлежат пересборке.  Это тривиальный join по этой таблице.

Займемся теперь вопросом, сколько же сизифовских пакетов придётся
тестировать пересборкой на каждый входящий src.rpm пакет.  У меня
есть полная таблица, кусочек которой приведен выше.  Введу новое
обозначение для полей таблицы:
	<test-src-rpm-basename> <incoming-rpm-basename>
Это означает, что собравшийся в incoming'е пакет <incoming-rpm-basename>,
оказывается, встает в чрут для сборки <test-src-rpm-basename>.  Значит,
вследствие прохождения <incoming-rpm-basename> нужно протестировать
пересборкой <test-src-rpm-basename>.

Я дополнил эту таблицу ещё одним полем:
	<test-src-rpm-basename> <incoming-rpm-basename> <incoming-src-rpm-basename>

Последнее поле означает, какой src.rpm пакет собрался в incoming'е.
Это нужно для того, чтобы учитывать, что из одного src.rpm пакета
при сборке в среднем получается больше одного установочного пакета,
которые будут вставать в чрут.  Это не должно искажать статистики.

Я выложил эту таблицу сюда (952K):
ftp://ftp.altlinux.org/pub/people/at/rebuild-map.bz2

Вот несколько случайных строчек этой таблицы:

$ perl -MList::Util=shuffle -e 'print +(shuffle<>)[1..10]' <rebuild-map 
qmmp-0.1.3.1-alt1.src.rpm	libxkbfile-devel-1.0.4-alt1.i586.rpm	libxkbfile-1.0.4-alt1.src.rpm
emacs-apel-10.6-alt1.20050606.src.rpm	emacs-devel-0.0.1-alt3.noarch.rpm	emacs-devel-0.0.1-alt3.src.rpm
kde-styles-klearlook-0.9.9.2-alt1.1.src.rpm	libXmu-devel-1.0.3-alt1.i586.rpm	libXmu-1.0.3-alt1.src.rpm
k3b-i18n-full-1.0.3-alt3.src.rpm	gccmakedep-1.0.1-alt1.i586.rpm	gccmakedep-1.0.1-alt1.src.rpm
grip-3.1.3-alt5.src.rpm	libjpeg-6b-alt8.i586.rpm	libjpeg-6b-alt8.src.rpm
wmmemload-0.1.6-alt3.src.rpm	libXext-1.0.3-alt1.i586.rpm	libXext-1.0.3-alt1.src.rpm
xfce4-panel-4.4.1-alt2.src.rpm	libfreetype-devel-2.3.5-alt2.i586.rpm	libfreetype-2.3.5-alt2.src.rpm
mysql-gui-tools-5.0r12-alt1.src.rpm	libXp-1.0.0-alt3.0.i586.rpm	libXp-1.0.0-alt3.0.src.rpm
tracker-0.6.0-alt0.1.src.rpm	libpoppler-glib-devel-0.5.4-alt6.i586.rpm	poppler-0.5.4-alt6.src.rpm
showfont-1.0.1-alt1.src.rpm	libFS-1.0.0-alt2.i586.rpm	libFS-1.0.0-alt2.src.rpm
$

Замечу, что эту таблицу нужно читать в обратном порядке, справа налево:
"пришёл пакет libxkbfile-*.src.rpm, из него собрался пакет libxkbfile-devel-*.i586.rpm,
из-за чего придётся протестировать пересборкой qmmp-*.src.rpm" и т.д.

Среднее поле в таблице на самом деле оказывается не слишком нужным,
я его удалю:

$ cut -f1,3 rebuild-map |sort -u -k2,2 -k1,1 >.ss
$ perl -MList::Util=shuffle -e 'print +(shuffle<>)[1..10]' <.ss
lprof-1.11.4.1-alt1.src.rpm	libxml2-2.6.29-alt2.src.rpm
$

"Пришел пакет libxml2-*.src.rpm, требуется протестировать пересборкой lprof-*.src.rpm".

Теперь несложно для каждого входящего пакета в incoming (справа)
вычислить число src.rpm пакетов (слева), подлежащих пересборке.

$ uniq -c -f1 .ss |head -1
144 alt-docs-main-0.4-alt7.src.rpm  ALDConvert-0.05-alt8.src.rpm
$

Здесь alt-docs-main это просто первый пакет, который попался и поэтому
остался, суть в том, что пакет ALDConvert-*.src.rpm на входе, если он
конечно соберётся, потребует протестировать пересборкой 144 пакетов.

Я теперь сделаю совсем уж интуитивно понятную таблицу
	<incoming-src-rpm-basename> <rebuild-number-src-rpm>

$ uniq -c -f1 .ss |awk '{print$3"\t"$1}' |sort -k2,2n >.sz
$ head -2 .sz
GraphicsMagick-1.1.8-alt1.src.rpm       1
MySQL41-4.1.21-alt5.1.src.rpm   1
$ tail .sz   
libSM-1.0.3-alt1.src.rpm        1952
libICE-1.0.4-alt1.src.rpm       1962
fontconfig-2.4.2-alt3.src.rpm   2120
libXext-1.0.3-alt1.src.rpm      2196
libfreetype-2.3.5-alt2.src.rpm  2203
gcc4.1-4.1.1-alt11.src.rpm      2365
libXau-1.0.3-alt1.src.rpm       2388
libXdmcp-1.0.2-alt1.0.src.rpm   2389
libX11-1.1.3-alt3.src.rpm       2392
expat-2.0.1-alt0.1.src.rpm      2646
$

Видим, что GraphicsMagick на входе потребует пересборки всего одного
src.rpm пакета (кстати, это koffice), а expat на входе потребует
пересобрать уже 2646 src.rpm пакетов.  Всего сейчас в репозитарии 6687
src.rpm пакетов (с точки зрения этой статистики).

ЗДЕСЬ НЕ УЧИТЫВАЮТСЯ ИЗМЕНЕНИЯ В basesystem + rpm-build.
Любой пакет, который попадает в basesystem + rpm-build, потребует,
по идее, полной пересборки сизифа, и этот случай я сейчас специально
отсёк.  Никакой другой пакет, однако, не может зацепить для пересборки
даже и половину сизифа.

Я пока объявляю пакеты из basesystem + rpm-build частным случаем, который
в данной статистике не рассматривается.

Сколько же всего имеется "входных" src.rpm пакетов, которые могут
потребовать пересборку чего-либо?

$ wc -l <.sz
2261
$

Это означает, что ТОЛЬКО КАЖДЫЙ ТРЕТИЙ ПАКЕТ просит что-то пересобрать.
Большая половина пакетов являются "листьями" ("приложениями") и заведомо
не влияют на собираемость каких-либо других пакетов.

Значит, будем считать среднее количество пакетов на пересборку для
"каждого третьего" пакета, а на каком-то этапе результат просто поделим
результат на три.  С точки зрения мат. статистики это, наверное, не
совсем правильно, то для грубой оценки сойдет.

Итак, распределение числа пакетов, подлежащих пересборке.
Среднее значение значение 78 пакетов, медиана распределения
5 пакетов, сигма 253 пакета.  Как и со временем сборки пакетов,
получилось распределение с маленьким средним значением и большой
сигмой.  Значит, говорить об "единичном случае" не серьезно,
нужно считать значения для серии пакетов.

Прежде всего однако прикинем порядок среднего значения.
78 пакетов * 74 секунды это порядка 100 минут.

Рационально считать время сборки для серии из 25 входящих src.rpm
пакетов.  Это очень грубо означает, что мы закладываемся на "суточную
норму", и неудачные последовательности входящих пакетов с достаточно
высокой надежностью не должны выбрасывать нас за пределы суток.

Прежняя формула для "достаточно надёжного заклада" говорит:
	P( xi(N) <= N*(mu+2*sigma/sqrt(N) ) >= 0.95

В данном случае xi(N) -- суммарное число src.rpm пакетов, подлежащих
пересборке на серии из N входящих пакетов, N=25; mu=78 пакетов,
sigma=253 пакета.

Вычислим член mu+2*sigma/sqrt(N), он даёт "среднее по выборке из 25"
с надёжностью 95% на превышение суммарного времени.

$ perl -le 'print 78+2*253/5'
179.2
$

Значит, чтобы нас не шатало "по суточной норме", вместо среднего
значения 78 пакетов нужно брать с запасом 179 пакетов.

Сколько времени будут собираться 179 пакетов?  Из предыдущего письма
известно, что t(N) = N*(74+2*189/sqrt(N));
t(179) = 18303 секунды = 5 часов.

Итого, каждый третий входящий src.rpm пакет с вероятностью 95%
уложится на пересборочном тестировании в 5 часов; это усреднение
по 25 входящим пакетам.  То есть на самом деле утверждение состоит
в том, что 25 входящих src.rpm с вероятностью около 95% уложатся
в 25*5=125 часов.

Среднее же время без "суточной надёжности" составляет, как уже
посчитано, 78 пакетов на пересборку * 74 секунды = 100 минут.
ЭТО ОЗНАЧАЕТ, ЧТО СРЕДНЯЯ ЗАГРУЗКА СЕРВЕРОВ на большом промежутке
времени (допустим, месяц) составит 100 минут/25 часов = 7%.
(Имеется в виду загрузка только на пересборочном тестировании.)
Запас серверной мощности, нужен, по сути, для того, чтобы "неудачная
последовательность входящих пакетов" не заставляла нас слишком долго
ждать.

Настало время поделить на 3.  Подумаем, насколько это корректно.
Мы исходили из того, что все входящие пакеты подряд требуют что-то
пересобрать.  Теперь они будут "перемешиваться" с пакетами, которые
пересобрать ничего не требуют.  Значит, это не должно ухудшить
показателя за счёт каких-либо выбросов.

ИТОГО, 5 часов/3 = 100 минут.
ОТВЕТ: на серии из N пакетов, где N порядка 25, суммарное время
пересборочного тестирования с вероятностью 95% не превысит N*100 минут.

Это довольно грубый ответ, и реально он может отличаться раза в два,
но не на порядок.  Завтра я попробую провести численный эксперимент,
который даст альтернативный и реально более правильный ответ.

Теперь настало время понять, чем статистика отличается от наглой лжи.
Ведь если пришёл пакет expat, то придётся ждать 54 часа, что на порядок
больше 5 часов и, похоже, выбрасывает нас за суточную норму.  Просто
expat выбивается за пределы 95-процентной надёжности.  Но в этом году
пакет expat был собран всего один раз.  То есть при случайном
поступлении пакетов появление expat это очень редкое событие.
Придётся подождать.

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]