|
ru.unix.bsd
- RU.UNIX.BSD ------------------------------------------------------------------
From : Vlad Gnatov 2:5020/400 24 Jan 2007 18:10:06
To : Alex Semenyaka
Subject : Re: создание/удаление миллиона файлов
--------------------------------------------------------------------------------
Alex Semenyaka пишет:
VG>>>> Алокатор dirhash тупой. Т.к. dirhash при resize создается заново,
VG>>>> то начиная с некоторого размера линейное увеличение невыгодно.
VG>>>> С этим можно бороться как поправив алгоритм, так и более простым
VG>>>> хаком, увеличив expand ratio.
AS>>> send-pr? :)
VG>> Шоб висел годами в трекере?
AS> А хоть бы пусть и висит. Hо возможно же, что висеть не будет, правда?
Жизнь показывает(tm) что небольшие улучшения, да еще и в узкоспециальных
областях, редко комитятся, в отличие от багфиксов.
Hо 'чтоб не пропало' пусть гугель помнит.
При создании dirhash для директории выделяется на 50%
больше элементов чем нужно для ее размера.
Это позволяет повысить производительноть при увеличении
числа файлов. Как только хеш заполнен на 75% он сбрасывается.
После чего его строят заново для нового размера директории.
Для небольшого количества файлов (тысячи - десятки тысяч)
это не составляет проблемы. Hо для сотен тысяч, а тем более
миллионов это приводит к колосальному падению производительности.
Выхода два:
1) Увеличить резерв при создании dirhash
2) При пересоздании хеша копировать данные из старого.
Я пока изучаю вторую возможность, но это нетривиально.
Что до первой, то здесь возможны варианты от тупого
увеличения резерва в 2 - 3 раза(см. первый патч) до кондиционного
увеличения коофициента после достижения определеного числа файлов
и его уменьшения, если при это занимается больше 75% dirhash_maxmem
Hу и сопутствующий механизм уменьшения кооф если при текущем не влазим
в maxmem.
Это конечно прототип, непомешает более широкое тестирование и review
кода.
- --- sys/ufs/ufs/ufs_dirhash.c
+++ ufs_dirhash.c.new
@@ -62,6 +62,12 @@
#define OFSFMT(vp) ((vp)->v_mount->mnt_maxsymlinklen <= 0)
#define BLKFREE2IDX(n) ((n) > DH_NFSTATS ? DH_NFSTATS : (n))
+#define MAX_ERATIO 1000
+#define MIN_ERATIO 120
+#define DEFAULT_ERATIO 150
+#define ERATIO_STEP 20
+#define REQ_FAIL -1
+
static MALLOC_DEFINE(M_DIRHASH, "UFS dirhash", "UFS directory hash tables");
static SYSCTL_NODE(_vfs, OID_AUTO, ufs, CTLFLAG_RD, 0, "UFS filesystem");
@@ -79,7 +85,12 @@
static int ufs_dirhashcheck = 0;
SYSCTL_INT(_vfs_ufs, OID_AUTO, dirhash_docheck, CTLFLAG_RW,
&ufs_dirhashcheck,
0, "enable extra sanity tests");
-
+static int ufs_dirhashextraratio = DEFAULT_ERATIO; /* 150 == ($var * 3 + 1) /
2 */
+SYSCTL_INT(_vfs_ufs, OID_AUTO, dirhash_extraratio, CTLFLAG_RW,
&ufs_dirhashextraratio,
+ 0, "current dirhash extra ratio");
+static int ufs_dirhashfthresh = 250000;
+SYSCTL_INT(_vfs_ufs, OID_AUTO, dirhash_fslotsthresh, CTLFLAG_RW,
&ufs_dirhashfthresh,
+ 0, "current dirhash fileslots threshold before extra ratio will be
increased");
static int ufsdirhash_hash(struct dirhash *dh, char *name, int namelen);
static void ufsdirhash_adjfree(struct dirhash *dh, doff_t offset, int diff);
@@ -126,7 +137,7 @@
struct direct *ep;
struct vnode *vp;
doff_t bmask, pos;
- int dirblocks, i, j, memreqd, nblocks, narrays, nslots, slot;
+ int dirblocks, fileslots, i, j, memreqd, extraratio, nblocks, narrays,
nslots,
slot;
/* Check if we can/should use dirhash. */
if (ip->i_dirhash == NULL) {
@@ -151,28 +162,60 @@
return (-1);
vp = ip->i_vnode;
- /* Allocate 50% more entries than this dir size could ever need. */
KASSERT(ip->i_size >= DIRBLKSIZ, ("ufsdirhash_build size"));
- nslots = ip->i_size / DIRECTSIZ(1);
- nslots = (nslots * 3 + 1) / 2;
- narrays = howmany(nslots, DH_NBLKOFF);
- nslots = narrays * DH_NBLKOFF;
- dirblocks = howmany(ip->i_size, DIRBLKSIZ);
- nblocks = (dirblocks * 3 + 1) / 2;
-
- memreqd = sizeof(*dh) + narrays * sizeof(*dh->dh_hash) +
- narrays * DH_NBLKOFF * sizeof(**dh->dh_hash) +
- nblocks * sizeof(*dh->dh_blkfree);
- DIRHASHLIST_LOCK();
- if (memreqd + ufs_dirhashmem > ufs_dirhashmaxmem) {
- DIRHASHLIST_UNLOCK();
- if (memreqd > ufs_dirhashmaxmem / 2)
- return (-1);
- /* Try to free some space. */
- if (ufsdirhash_recycle(memreqd) != 0)
- return (-1);
- /* Enough was freed, and list has been locked. */
+ extraratio = ufs_dirhashextraratio;
+ fileslots = ip->i_size / DIRECTSIZ(1);
+ /*
+ * If number of fileslots greater than fileslots threshold -
+ * increase extraratio for better productivity.
+ */
+ if (extraratio == DEFAULT_ERATIO &&
+ fileslots > ufs_dirhashfthresh)
+ extraratio *= 3;
+ /*
+ * Allocate extraratio/100 times more entries
+ * than this dir size could ever need.
+ */
+ memreqd = REQ_FAIL;
+ while(memreqd == REQ_FAIL) {
+ nslots = (fileslots * extraratio) / 100;
+ narrays = howmany(nslots, DH_NBLKOFF);
+ nslots = narrays * DH_NBLKOFF;
+ dirblocks = howmany(ip->i_size, DIRBLKSIZ);
+ nblocks = (dirblocks * extraratio) / 100;
+
+ memreqd = sizeof(*dh) + narrays * sizeof(*dh->dh_hash) +
+ narrays * DH_NBLKOFF * sizeof(**dh->dh_hash) +
+ nblocks * sizeof(*dh->dh_blkfree);
+ DIRHASHLIST_LOCK();
+ if (memreqd + ufs_dirhashmem > ufs_dirhashmaxmem) {
+ DIRHASHLIST_UNLOCK();
+ if (memreqd < ufs_dirhashmaxmem / 3) { /* XXX /2 ?*/
+ /* Try to free some space. */
+ if (ufsdirhash_recycle(memreqd) != 0)
+ memreqd = REQ_FAIL;
+ } else
+ memreqd = REQ_FAIL;
+
+
+ } else if (extraratio > DEFAULT_ERATIO &&
+ memreqd + ufs_dirhashmem > ufs_dirhashmaxmem * 3 / 4) {
+ /*
+ * XXX If memory usage greater than 75% maxmem
+ * lower extraratio if it > DEFAULT_ERATIO
+ */
+ DIRHASHLIST_UNLOCK();
+ memreqd = REQ_FAIL;
+ }
+
+ if (memreqd == REQ_FAIL) {
+ /* Lower extraratio and try again */
+ if (extraratio < MIN_ERATIO + ERATIO_STEP)
+ return (-1);
+
+ extraratio -= ERATIO_STEP;
+ }
}
ufs_dirhashmem += memreqd;
DIRHASHLIST_UNLOCK();
- ---
Testcase:
$cat dhtest
#!/bin/sh
umount /tmp/dhtest
rmdir /tmp/dhtest
mdconfig -d -u 666
mdconfig -a -t swap -s1280M -u 666 && \
bsdlabel -w /dev/md666 auto && \
newfs -U -f 512 -b 4096 -i 512 -m 0 /dev/md666a
mkdir /tmp/dhtest && \
mount /dev/md666a /tmp/dhtest && \
chown stalker:stalker /tmp/dhtest && \
cp ~stalker/works/dirhash/test1 /tmp/dhtest/test1
sysctl vfs.ufs
$cat test1.c
#include <sys/types.h>
#include <sys/stat.h>
#include <sys/sysctl.h>
#include <fcntl.h>
#include <time.h>
#include <unistd.h>
#include <stdio.h>
int main(void)
{
static time_t tval;
int fd, n, btime, spent, i, j;
int count = 50;
int step = 20000;
size_t len;
int mem;
len = sizeof(mem);
if (mkdir("d", 0700) < 0)
perror("mkdir");
sysctlbyname("vfs.ufs.dirhash_extraratio", &mem, &len, NULL, 0);
printf("vfs.ufs.ufs.dirhash_extraratio=%d\n", mem);
sysctlbyname("vfs.ufs.dirhash_maxmem", &mem, &len, NULL, 0);
printf("vfs.ufs.dirhash_maxmem=%d\n", mem);
printf("creating...\n");
btime = time(&tval);
n = spent = 0;
for (i=1; i<=count; i++) {
for (j=1; j<=step; j++) {
char name[10];
sprintf(name, "d/%d.%d", i, j);
fd = open(name, O_CREAT, 0600);
close(fd);
}
n += step;
spent = time(&tval) - btime;
if (spent == 0) spent = 1;
printf("created %d: %d sec, %d files/sec, ", n, spent,
n/spent);
sysctlbyname("vfs.ufs.dirhash_mem", &mem, &len, NULL, 0);
//sysctlbyname("vfs.ufs.dirhash_fileslots", &fslots, &len,
NULL, 0);
//printf("dirhash_fileslots=%d dirhash_mem=%d\n", fslots,
mem);
printf("dirhash_mem=%d\n", mem);
}
printf("removing...\n");
btime = time(&tval);
for (i=1; i<=count; i++) {
for (j=1; j<=step; j++) {
char name[10];
sprintf(name, "d/%d.%d", i, j);
unlink(name);
}
}
if (rmdir("d") < 0)
perror("rmdir");
spent = time(&tval) - btime;
printf("removed: %d sec, %d files/sec\n", spent, (count * step) /
spent);
return(0);
}
#vfs.ufs.dirhash_maxmem=15000000
$cd /tmp/dhtest
$./test1
--
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5.3
* Origin: Talk.ru (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
