From owner-freebsd-hackers Fri Jun 1 9:40: 5 2001 Delivered-To: freebsd-hackers@freebsd.org Received: from fledge.watson.org (fledge.watson.org [204.156.12.50]) by hub.freebsd.org (Postfix) with ESMTP id A08F437B423 for ; Fri, 1 Jun 2001 09:39:57 -0700 (PDT) (envelope-from robert@fledge.watson.org) Received: from fledge.watson.org (robert@fledge.pr.watson.org [192.0.2.3]) by fledge.watson.org (8.11.3/8.11.3) with SMTP id f51Gdif82022; Fri, 1 Jun 2001 12:39:45 -0400 (EDT) (envelope-from robert@fledge.watson.org) Date: Fri, 1 Jun 2001 12:39:44 -0400 (EDT) From: Robert Watson X-Sender: robert@fledge.watson.org To: Ian Dowse Cc: freebsd-hackers@freebsd.org Subject: Re: UFS large directory performance In-Reply-To: <200106011541.aa41502@salmon.maths.tcd.ie> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: owner-freebsd-hackers@FreeBSD.ORG Precedence: bulk List-ID: List-Archive: (Web Archive) List-Help: (List Instructions) List-Subscribe: List-Unsubscribe: X-Loop: FreeBSD.ORG This is great -- once I finish moving back to Maryland (sometime mid-next-week) I'd be very interested in running this code on a -CURRENT mock-up of my Cyrus server, which regularly runs with 65,000+ file directories. I assume this is a -CURRENT patch set? (Mind you, I've found that most of the perceived "large directory suffering" people tell me about is running ls with sorting enabled :-). Robert N M Watson FreeBSD Core Team, TrustedBSD Project robert@fledge.watson.org NAI Labs, Safeport Network Services On Fri, 1 Jun 2001, Ian Dowse wrote: > > Prompted by the recent discussion about performance with large > directories, I had a go at writing some code to improve the situation > without requiring any filesystem changes. Large directories can > usually be avoided by design, but the performance hit is very > annoying when it occurs. The namei cache may help for lookups, but > each create, rename or delete operation always involves a linear > sweep of the directory. > > The idea of this code is to maintain a throw-away in-core data > structure for large directories, allowing all operations to be > performed quickly without the need for a linear search. The > experimental (read 'may trash your system'!) proof-of-concept patch > is available at: > > http://www.maths.tcd.ie/~iedowse/FreeBSD/dirhash.diff > > The implementation uses a hash array that maps filenames to the > directory offset where the corresponding directory entry exists. > A simple spillover mechanism is used to deal with hash collisions, > and some extra summary information permits the quick location of > free space within the directory itself for create operations. > > The in-core data structures have a memory requirement approximately > equal to half of the on-disk directory size. Currently there are > two sysctls that determine when directories get hashed: > > vfs.ufs.dirhashminsize Minimum directory on-disk size for which > hashing should be used (default 2.5k). > vfs.ufs.dirhashmaxmem Maximum system-wide amount of memory to > use for directory hashes (default 2Mb). > > Even on a relatively slow machine (200Mhz P5), I'm seeing a file > creation speed that remains at around 1000 creations/second for > directories with more than 100,000 entries. Without this patch, I > get less than 20 creations per second on the same directory (in > both cases soft-updates is enabled). > > To test, apply the patch, and add "options UFS_DIRHASH" to the > kernel config. > > Currently there are a number of features missing, and there is a > lot of code for debugging and sanity checking that may affect > performance. The main issues I'm aware of are: > - There is no LRU mechanism for directory hash data structures. The > hash tables get freed when the in-code inode is recycled, but no > attempt is made to free existing memory when the dirhashmaxmem limit > is reached. > - The lookup code does not optimise the case where successive > offsets from the hash table are in the same filesystem block. > > Ian > > To Unsubscribe: send mail to majordomo@FreeBSD.org > with "unsubscribe freebsd-hackers" in the body of the message > To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-hackers" in the body of the message