[devel] cmdcache

[devel] cmdcache

[Alexey Tourbin]

[-- Attachment #1.1: Type: text/plain, Size: 763 bytes --]

On Sun, Sep 11, 2005 at 09:06:44PM +0400, Alexey Tourbin wrote:
> Написал на шелле, с кешированием для каталогов.  Для робота это важно --
> очень долго (с распаковкой всех rpm'ов) только один раз будет работать.

По поводу кеширования мне пришла в голову ещё одна мысль.
Некоторые команды, которые работают долго, и вывод которых стоит
кешировать, имеют вид

	cmd [args...] path

В случае, если состояние сущности path определяется датой модификации
path, то команду можно завернуть в скрипт или функцию, которая перед
запуском команды проверят наличие результата в кеше:

	cmdcache cmd [args...] path

Вот предварительная реализация этой идеи.  Почему-то очень много кода
получилось. :(  Если кто-то знает, как сделать лучше, подскажите плиз.

[-- Attachment #1.2: cmdcache --]
[-- Type: text/plain, Size: 1807 bytes --]

#!/bin/sh -ef

cmdcache()
{
	if [ $# -lt 2 ]; then
		echo "cmdcache: not enough arguments" >&2
		pod2usage --exit=2 cmdcache || [ $? = 2 ]
		return 2
	fi

	local cmd="$1"; shift
	local cdir="$HOME/.cmdcache/${cmd##*/}"
	[ -d "$cdir" ] || mkdir -p -m700 "$cdir" || return 1
	[ -n "${RANDOM##*0}" ] || find "$cdir" -type f -mtime +33 -atime +33 -delete

	local file; for file; do :; done
	if [ ! -e "$file" ]; then
		echo "cmdcache: $file: no such file or directory" >&2
		return 1
	fi

	local cache="$*"; cache="$cdir/${cache//[-.\/ ]/_}"
	if [ -f "$cache" ] && ! [ "$file" -nt "$cache" -o "$cache" -nt "$file" ]; then
		cat "$cache"
		return
	fi

	local rc=0
	local mtime0; mtime0="$(stat --format $'%Y\n' "$file")" || return

	"$cmd" "$@" >"$cache" && touch -r "$file" "$cache" || rc=$?
	cat "$cache"
	
	local mtime1; mtime1="$(stat --format $'%Y\n' "$file")" || rc=$?
	if [ $rc = 0 -a "$mtime0" != "$mtime1" ]; then
		echo "cmdcache: $file has changed" >&2
		rc=1
	fi

	[ $rc = 0 ] || rm -f "$cache"
	return $rc
}

if [ -z "$*" -a "${0##*/}" != cmdcache ]; then
	: okay, maybe I am sourced
elif [ "x$*" = x-h -o "x$*" = x--help ]; then
	pod2usage --exit=0 "$0"
else 
	cmdcache "$@"
fi

: <<'__EOF__'

=head1	NAME

cmdcache - simple command cache based on timestamps

=head1	SYNOPSIS

B<cmdcache> I<cmd> [I<args>...] I<FILE>

B<source> B<cmdcache> ''

=head1	AUTHOR

Written by Alexey Tourbin <at@altlinux.org>.

=head1	COPYING

Copyright (c) 2005 Alexey Tourbin, ALT Linux Team.

This is free software; you can redistribute it and/or modify it under the terms
of the GNU General Public License as published by the Free Software Foundation;
either version 2 of the License, or (at your option) any later version.

=cut

__EOF__

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

[devel] Re: cmdcache

[Alexey Tourbin]

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

On Mon, Sep 12, 2005 at 03:35:51PM +0400, Alexey Tourbin wrote:
> В случае, если состояние сущности path определяется датой модификации
> path, то команду можно завернуть в скрипт или функцию, которая перед
> запуском команды проверят наличие результата в кеше:
> 
> 	cmdcache cmd [args...] path

Насколько надежна такая конструкция вообще, чтобы использовать её
в скриптах по умолчанию?  Я вижу две проблемы:

1) Недостаточно хорошая функция хеширования.  Т.е. для some/file.txt
и some_file.txt получается один и тот же кеш.  Если mtime у этих двух
файлов отличается, то кеш каждый раз пересоздается, в противном случае
получается "самое ужасное": неверный результат из кеша.

2) Изменение формата вывода cmd.  Опять получается неверный результат
из кеша.

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

Re: [devel] Re: cmdcache

[Dmitry V. Levin]

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

On Mon, Sep 12, 2005 at 05:05:20PM +0400, Alexey Tourbin wrote:
> On Mon, Sep 12, 2005 at 03:35:51PM +0400, Alexey Tourbin wrote:
> > В случае, если состояние сущности path определяется датой модификации
> > path, то команду можно завернуть в скрипт или функцию, которая перед
> > запуском команды проверят наличие результата в кеше:
> > 
> > 	cmdcache cmd [args...] path
> 
> Насколько надежна такая конструкция вообще, чтобы использовать её
> в скриптах по умолчанию?  Я вижу две проблемы:
> 
> 1) Недостаточно хорошая функция хеширования.  Т.е. для some/file.txt
> и some_file.txt получается один и тот же кеш.  Если mtime у этих двух
> файлов отличается, то кеш каждый раз пересоздается, в противном случае
> получается "самое ужасное": неверный результат из кеша.

Тщательнее должен быть алгоритм квотирования.

> 2) Изменение формата вывода cmd.  Опять получается неверный результат
> из кеша.

Надо следить за изменением cmd.

3) А что если cmd это wget -O -?  Хорошо ли кэшировать результат работы
браузера удалённых ресурсов? :)


-- 
ldv

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

[devel] Re: cmdcache

[Alexey Tourbin]

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

On Mon, Sep 12, 2005 at 05:34:38PM +0400, Dmitry V. Levin wrote:
> > 1) Недостаточно хорошая функция хеширования.  Т.е. для some/file.txt
> > и some_file.txt получается один и тот же кеш.  Если mtime у этих двух
> > файлов отличается, то кеш каждый раз пересоздается, в противном случае
> > получается "самое ужасное": неверный результат из кеша.
> Тщательнее должен быть алгоритм квотирования.

Хочется это сделать исключительно средствами шелла - я даже готов пойти
на башизмы типа ${var//.../_}. :)  Если делать это sed'ом или чем-нибудь
таким, то каждое обращение к cmdcache будет замедляться fork+exec'ом,
а это удовольствие минимум на два порядка дороже встроенных команд.

> > 2) Изменение формата вывода cmd.  Опять получается неверный результат
> > из кеша.
> Надо следить за изменением cmd.

cmd может быть функцией!  Для этого cmdcache надо соурсить.  В этом вся
фишка -- если в кеше все хиты, то будет работать *очень* быстро.  То
есть всё в пределах одного процесса.

> 3) А что если cmd это wget -O -?  Хорошо ли кэшировать результат работы
> браузера удалённых ресурсов? :)

Да нет.  Речь о чем идет.  Что когда мы *явно* знаем, что команда имеет
вид `cmd [args...] path' и именно в таком виде мы используем эту команду
в скрипте, то в том же скрипте можно будет записать что-то вроде

. cmdcache ""		# дай функцию
alias rpmfile='cmdcache rpmfile'

rpmfile()
{
	f="$1"; shift
	...
}

# здесь будет "проксироваться"
for f; do rpmfile "$f"; done

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

[devel] [JT] Re: cmdcache

[Michael Shigorin]

On Mon, Sep 12, 2005 at 05:34:38PM +0400, Dmitry V. Levin wrote:
> 3) А что если cmd это wget -O -?

user education? :)

-- 
 ---- WBR, Michael Shigorin <mike@altlinux.ru>
  ------ Linux.Kiev http://www.linux.kiev.ua/
 ----       visit our conference (Oct 1):
--          http://conference.osdn.org.ua

[devel] Re: [JT] Re: cmdcache

[Alexey Tourbin]

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

On Mon, Sep 12, 2005 at 05:57:06PM +0300, Michael Shigorin wrote:
> On Mon, Sep 12, 2005 at 05:34:38PM +0400, Dmitry V. Levin wrote:
> > 3) А что если cmd это wget -O -?
> user education? :)

Ох.  Ну при чем здесь wget?  Есть команды, которые последним аргументом
имеют *ФАЙЛ* (или каталог, не важно; важно, что у файла или каталога
есть mtime).  Если результат работы команды целиком зависит от
содержимого этого файла или каталога, то такую команду можно "завернуть"
в ещё одну команду -- cmdcache.  Этот wrapper будет проверять, есть ли
вывод этой же команды в кеше и совпадает ли mtime у кеша и ФАЙЛА.
Если не совпадает, то делается кеш и `touch -r ФАЙЛ кеш'.  И отдаётся.
В следующий раз mtime, вероятно, совпадёт.

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

[devel] Re: cmdcache

[Alexey Tourbin]

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

On Mon, Sep 12, 2005 at 05:34:38PM +0400, Dmitry V. Levin wrote:
> > 1) Недостаточно хорошая функция хеширования.  Т.е. для some/file.txt
> > и some_file.txt получается один и тот же кеш.  Если mtime у этих двух
> > файлов отличается, то кеш каждый раз пересоздается, в противном случае
> > получается "самое ужасное": неверный результат из кеша.
> Тщательнее должен быть алгоритм квотирования.

С другой стороны, вообще не обязательно, чтобы имя кеш-файла
генерировалось из имени файла-аргумента.  Каждый файл в пределах машины
уникально идентифицируется st_dev+st_ino.  То есть хеш-функция может
использовать что-то вроде

$ stat --format $'%d.%i.%Y\n' ФАЙЛ

Накладной расход -- один fork+exec.  Поскольку есть как минимум ещё один
fork+exec (cat cache), то получается неплохой вариант.

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

[devel] Re: cmdcache

[Alexey Tourbin]

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

On Tue, Sep 13, 2005 at 09:21:30AM +0400, Alexey Tourbin wrote:
> $ stat --format $'%d.%i.%Y\n' ФАЙЛ
> 
> Накладной расход -- один fork+exec.  Поскольку есть как минимум ещё один
> fork+exec (cat cache), то получается неплохой вариант.

Насколько замедляется доступ к файлам в каталоге, если файлов становится
очень много?  Скажем, порядка 10k?  Скорость доступа для glob(3) и т.п.
не интересует, только stat(2) и open(2) для заранее известных файлов в
каталоге.

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

[devel] Re: cmdcache

[Michael Shigorin]

On Wed, Sep 14, 2005 at 07:35:47PM +0400, Alexey Tourbin wrote:
> > $ stat --format $'%d.%i.%Y\n' ФАЙЛ
> > Накладной расход -- один fork+exec.  Поскольку есть как
> > минимум ещё один fork+exec (cat cache), то получается
> > неплохой вариант.
> Насколько замедляется доступ к файлам в каталоге, если файлов
> становится очень много?  Скажем, порядка 10k?  Скорость доступа
> для glob(3) и т.п.  не интересует, только stat(2) и open(2) для
> заранее известных файлов в каталоге.

Это про %_sourcedir, который почему-то не %_topdir/SOURCES/%name?

-- 
 ---- WBR, Michael Shigorin <mike@altlinux.ru>
  ------ Linux.Kiev http://www.linux.kiev.ua/
 ----       visit our conference (Oct 1):
--          http://conference.osdn.org.ua

[devel] Re: cmdcache

[Alexey Tourbin]

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

On Wed, Sep 14, 2005 at 06:47:13PM +0300, Michael Shigorin wrote:
> > Насколько замедляется доступ к файлам в каталоге, если файлов
> > становится очень много?  Скажем, порядка 10k?  Скорость доступа
> > для glob(3) и т.п.  не интересует, только stat(2) и open(2) для
> > заранее известных файлов в каталоге.
> 
> Это про %_sourcedir, который почему-то не %_topdir/SOURCES/%name?

Нет, это про ~/.cmdcache/rpmfile, в котором число кеш-файлов будет не
меньше числа rpm пакетов в Sisyphus/files.  С %_sourcedir меня всё
устраивает.

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

[devel] Re: cmdcache

[Michael Shigorin]

On Wed, Sep 14, 2005 at 08:12:34PM +0400, Alexey Tourbin wrote:
> > > Насколько замедляется доступ к файлам в каталоге, если
> > > файлов становится очень много?  Скажем, порядка 10k?
> > > Скорость доступа для glob(3) и т.п.  не интересует, только
> > > stat(2) и open(2) для заранее известных файлов в каталоге.
> > Это про %_sourcedir, который почему-то не %_topdir/SOURCES/%name?
> Нет, это про ~/.cmdcache/rpmfile, в котором число кеш-файлов
> будет не меньше числа rpm пакетов в Sisyphus/files.
> С %_sourcedir меня всё устраивает.

Структурировать по первым буквам?

-- 
 ---- WBR, Michael Shigorin <mike@altlinux.ru>
  ------ Linux.Kiev http://www.linux.kiev.ua/
 ----       visit our conference (Oct 1):
--          http://conference.osdn.org.ua

[devel] Re: cmdcache

[Alexey Tourbin]

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

On Wed, Sep 14, 2005 at 07:38:54PM +0300, Michael Shigorin wrote:
> > Нет, это про ~/.cmdcache/rpmfile, в котором число кеш-файлов
> > будет не меньше числа rpm пакетов в Sisyphus/files.
> > С %_sourcedir меня всё устраивает.
> Структурировать по первым буквам?

Букв нет, есть только st_ino+st_size+st_mtime.

at@solemn ~/.cmdcache 4 $ ls -1 rpmfile |head
i10003s62465m1079085926
i10226s323862m1079960217
i10287s367587m1080138012
i10366s1535556m1077197737
i10552s68368m1077197738
i10580s107898m1078145421
i10723s828128m1076422307
i1090192s13734m1125334673
i11055s406941m1079109059
i1166331s4611m1125335339
at@solemn ~/.cmdcache 4 $

К тому же по буквам получится плохое распределение, а кеш всё равно
"не прозрачный" (то есть reverse lookup затруднён).  Можно сделать
одноуровневую прослойку из каталогов по последним цифрам ino и size.
Получится 100 файлов на 100 каталогов для 10k capacity.  Надо посмотреть
как в ccache сделано.

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

[devel] Re: cmdcache hash function

[Alexey Tourbin]

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

On Wed, Sep 14, 2005 at 09:10:04PM +0400, Alexey Tourbin wrote:
> Букв нет, есть только st_ino+st_size+st_mtime.
> 
> at@solemn ~/.cmdcache 4 $ ls -1 rpmfile |head
> i10003s62465m1079085926
> i10226s323862m1079960217
> i10287s367587m1080138012
> i10366s1535556m1077197737
> i10552s68368m1077197738
> i10580s107898m1078145421
> i10723s828128m1076422307
> i1090192s13734m1125334673
> i11055s406941m1079109059
> i1166331s4611m1125335339
> at@solemn ~/.cmdcache 4 $
> 
> К тому же по буквам получится плохое распределение, а кеш всё равно
> "не прозрачный" (то есть reverse lookup затруднён).  Можно сделать
> одноуровневую прослойку из каталогов по последним цифрам ino и size.
> Получится 100 файлов на 100 каталогов для 10k capacity.  Надо посмотреть
> как в ccache сделано.

Okay, есть три числа: st_ino, st_size и st_mtime.  Как их по-грамотному
захешировать?  Нужно сделать одноуровневую прослойку из каталогов.  Для
capacity порядка 10k выбираем число каталогов (buckets) в районе 100:

$ for n in `seq 50 150`; do factor $n; done |awk NF==2
53: 53
59: 59
61: 61
67: 67
71: 71
73: 73
79: 79
83: 83
89: 89
97: 97
101: 101
103: 103
107: 107
109: 109
113: 113
127: 127
131: 131
137: 137
139: 139
149: 149
$

Значит хешируем по модулю например 97.

cmdcache_hash()
{
	local c_st
	c_st="$(stat -L -c '%i %s %Y' -- "$1")" || return
	set -- $c_st
	local c_hashfile="i${1}s${2}m${3}"
	local c_hashdir=$(( ( $1 + $2 + $3 ) % 97 ))
	echo "$c_hashdir/$c_hashfile"
}

bash-2.05b$ cmdcache_hash /etc/passwd
70/i22612s2957m1119749776
bash-2.05b$ exit

Коллеги!  Как по-грамотному три числа захешировать?

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

[devel] Re: cmdcache hash function

[Alexey Tourbin]

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

On Thu, Sep 15, 2005 at 01:26:51PM +0400, Alexey Tourbin wrote:
> Коллеги!  Как по-грамотному три числа захешировать?

Что, никто не подкован?  Попробовал несколько вариантов, наименьшая
стандартная девиация (т.е. в данном случае это неравномерность коллизий
по bucket'ам) получается с обычным xor'ом.

( ino ^ size ^ mtime ) % prime

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