From owner-freebsd-fs@FreeBSD.ORG Sun Mar 27 18:39:01 2005 Return-Path: Delivered-To: freebsd-fs@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 75D1E16A4CE; Sun, 27 Mar 2005 18:39:01 +0000 (GMT) Received: from pooker.samsco.org (pooker.samsco.org [168.103.85.57]) by mx1.FreeBSD.org (Postfix) with ESMTP id 9376143D58; Sun, 27 Mar 2005 18:38:58 +0000 (GMT) (envelope-from scottl@samsco.org) Received: from [192.168.254.201] ([192.168.254.201]) (authenticated bits=0) by pooker.samsco.org (8.13.1/8.13.1) with ESMTP id j2RIaq9E095814; Sun, 27 Mar 2005 11:36:52 -0700 (MST) (envelope-from scottl@samsco.org) Message-ID: <4247D19F.6010502@samsco.org> Date: Mon, 28 Mar 2005 02:42:55 -0700 From: Scott User-Agent: Mozilla/5.0 (X11; U; FreeBSD amd64; en-US; rv:1.7.5) Gecko/20050321 X-Accept-Language: en-us, en MIME-Version: 1.0 To: Robert Watson References: In-Reply-To: Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Status: No, score=-2.8 required=3.8 tests=ALL_TRUSTED autolearn=failed version=3.0.2 X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on pooker.samsco.org cc: David Malone cc: freebsd-fs@FreeBSD.org Subject: Re: UFS Subdirectory limit. X-BeenThere: freebsd-fs@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: Filesystems List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 27 Mar 2005 18:39:01 -0000 Robert Watson wrote: > On Sat, 26 Mar 2005, David Malone wrote: > > >>>Also, the more important >>>concern is that large directories simply don't scale in UFS. Lookups >>>are a linear operation, and while DIRHASH helps, it really doesn't scale >>>well to 150k entries. >> >>It seems to work passably well actually, not that I've benchmarked it >>carefully at this size. My junkmail maildir has 164953 entries at the >>moment, and is pretty much continiously appended to without creating any >>problems for the machine it lives on. Dirhash doesn't care if the >>entries are subdirectories or files. >> >>If the directory entries are largely static, the name cache should do >>all the work, and it is well capable of dealing with lots of files. >> >>We should definitely look at what sort of filesystem features we're >>likely to need in the future, but I just wanted to see if we can offer >>people a sloution that doesn't mean waiting for FreeBSD 6 or 7. > > > FWIW, I regularly use directories with several hundred thousand files in > them, and it works quite well for the set of operations I perform > (typically, I only append new entries to the directory). This is with a > cyrus server hosting fairly large shared folders -- in Cyrus, a > maildir-like format is used. For example, the lists.linux.kernel > directory references 430,000 individual files. Between UFS_DIRHASH and > Cyrus's use of a cache file, opening the folder primarily consists of > mmap'ing the cache file and then doing lookups, which occur quite quickly. > My workload doesn't currently require large numbers of directories > referenced by a similar directory, but based on the results I've had with > large numbers of files, I can say it likely would work fine subject to the > ability for UFS to express it. > > Robert N M Watson > > Luckily, linear reads through a directory are nearly O(1) in UFS since ufs_lookup() caches the offset to the last entry read so that a subsequent call doesn't have to start from the beginning. I would suspect that this, along with the namei cache, DIRHASH, and cyrus's cache, all contribute together to make reading the spool directories non-painful for you. I would also suspect that there is little manual sorting going on since cyrus chooses names for new entries that are naturally sorted. I'm still not sure I would consider these behaviours to be representative of the normal, though. It would be quite interesting to profile the system while cyrus is trying to append or delete a mail file into one of your large spool directories. Would an application that isn't as well-written as cyrus behave as well? What about an application like Squid? Scott