From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from lists.gentoo.org (pigeon.gentoo.org [208.92.234.80]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by finch.gentoo.org (Postfix) with ESMTPS id 09D18138334 for ; Sat, 19 Oct 2019 08:20:57 +0000 (UTC) Received: from pigeon.gentoo.org (localhost [127.0.0.1]) by pigeon.gentoo.org (Postfix) with SMTP id 38935E0976; Sat, 19 Oct 2019 08:20:53 +0000 (UTC) Received: from smtp.gentoo.org (smtp.gentoo.org [140.211.166.183]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by pigeon.gentoo.org (Postfix) with ESMTPS id CE4DAE096B for ; Sat, 19 Oct 2019 08:20:52 +0000 (UTC) Received: from [192.168.5.125] (pool-96-232-115-28.nycmny.fios.verizon.net [96.232.115.28]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) (Authenticated sender: ryao) by smtp.gentoo.org (Postfix) with ESMTPSA id 50D3234C041 for ; Sat, 19 Oct 2019 08:20:51 +0000 (UTC) Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable From: Richard Yao Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-Id: Gentoo Linux mail X-BeenThere: gentoo-dev@lists.gentoo.org Reply-to: gentoo-dev@lists.gentoo.org X-Auto-Response-Suppress: DR, RN, NRN, OOF, AutoReply Mime-Version: 1.0 (1.0) Date: Sat, 19 Oct 2019 04:20:48 -0400 Subject: Re: [gentoo-dev] New distfile mirror layout Message-Id: <988EB80E-A853-400F-91A9-17BEA86C71F3@gentoo.org> References: In-Reply-To: To: gentoo-dev@lists.gentoo.org X-Mailer: iPad Mail (17A860) X-Archives-Salt: 11c7c1ad-3758-4a12-abae-7f7fee1c9f90 X-Archives-Hash: 7aab0543caab6864c5b4472f4b7f35b5 > On Oct 19, 2019, at 2:17 AM, Micha=C5=82 G=C3=B3rny wr= ote: >=20 > =EF=BB=BFOn Fri, 2019-10-18 at 21:09 -0400, Richard Yao wrote: >>>> On Oct 18, 2019, at 4:49 PM, Micha=C5=82 G=C3=B3rny = wrote: >>>=20 >>> =EF=BB=BFOn Fri, 2019-10-18 at 15:53 -0400, Richard Yao wrote: >>>>>>>> On Oct 18, 2019, at 9:42 AM, Micha=C5=82 G=C3=B3rny wrote: >>>>>>> =EF=BB=BFHi, everybody. >>>>>>> It is my pleasure to announce that yesterday (EU) evening we've swit= ched >>>>>>> to a new distfile mirror layout. Users will be switching to the new= >>>>>>> layout either as they upgrade Portage to 2.3.77 or -- if they upgrad= ed >>>>>>> already -- as their caches expire (24hrs). >>>>>>> The new layout is mostly a bow towards mirror admins, for some of wh= om >>>>>>> having a 60000+ files in a single directory have been a problem. >>>>>>> However, I suppose some of you also found e.g. the directory index >>>>>>> hardly usable due to its size. >>>> This sounds like a filesystem issue. Do we know which filesystems are s= uffering? >>>> ZFS should be fine. I believe ext2/ext3 have problems with this many fi= les. ext4 is probably okay, but don=E2=80=99t quote me on that. >>>=20 >>> Ext2, VFAT and NTFS were mentioned on the bug [1], though I suppose this= >>> may apply only to older ntfs versions. NFS has been mentioned too. >>=20 >> ext2 and vfat are not surprises to me (outside of the idea that anyone wo= uld use them for a mirror). NTFS and NFS are though. >=20 > Are you surprised that people use NTFS on Windows? Or that they use > local mirrors over NFS? The latter still needs to be addressed > separatel, provided that they mount it on DISTDIR. I am surprised that it was an issue on NTFS because it uses B-trees. As for N= FS, I had expected that to be more dependent on the local filesystem than on= NFS itself. If it has a slowdown when used on a filesystem that had fast di= rectory operations, that might be a bug. >=20 >>> However, just because modern filesystems can handle them efficiently, it= >>> doesn't mean having directories that huge comes with zero cost. >> While I am okay with the change, what do you mean when you say that havin= g huge directories does not come with zero cost? >>=20 >> Filesystems with O(1) directory lookups like ZFS would probably be hurt b= y this >=20 > O(1) or O(n)? ZFS uses extendible hashing for its directories, so the data structure used i= s amortized O(1). You might consider it O(log n) due to the indirect tree tr= aversal needed to find the direct block containing the hash table entry. Wit= h caching of indirect blocks, it should be amortized O(1) to find the direct= block in practice as far as read IOs are considered. In addition, the base o= f the logarithm is 128 or 1024 depending on the pool feature flags. >=20 >> , but the impact should be negligible. Filesystems with O(log n) director= y lookups would see faster directory lookups. >>=20 >> Outside of directory lookups, this could speed up up searches and sort op= erations when listing everything with just about any filesystem benefiting f= rom the improvement. >>=20 >> Listing directories on such filesystems should not benefit from this unle= ss you are using ls where the default behavior is to sort the directory cont= ents (which is where the improvement when sorting comes into play). The need= to sort the directory contents by default keeps ls from displaying anything= until it has scanned the entire directory. The asymptotic complexity of a f= ast comparison based sort improves in this situation from O(nlogn) to O(nlog= (n/b)) provided that you sort each subdirectory independently. A further spe= ed up could be obtained by doing multithreading to parallelize the sort oper= ations. >>=20 >> Since I know someone will call me out on that comment, I will explain. Ea= ch bucket has roughly n/b items in it where n is the total number and b is t= he number of buckets. Sorting one bucket is O(n/b * log(n/b)). Loop to sort e= ach of the b buckets. The buckets are pre-sorted by prefix, so the result is= now sorted. You therefore get O(nlog(n/b)) time complexity out of an O(nlog= n) comparison sort on this very special case where you call it multiple time= s on data that has been persorted by prefix into buckets. >>=20 >> Is there any other benefit to this or did I get everything? >=20 > Listings for individual directories won't cause major pain to browsers > anymore. Not that there's much reason to do them. That makes sense. >=20 > All kinds of per-direction operations will consume less memory > and be potentially faster. Userland would save memory when sorting or grepping a directory listing by v= irtue of having to process less data for grep and less data at a time for so= rting (if it takes advantage of this). That would have performance benefits i= n userland. The kernel would have little memory savings and in some cases might be sligh= tly worse. It is negligible. Performance in the kernel ought to be slightly b= etter on filesystems with O(log n) directory operations, but I would only ex= pect the really bad ones to show much improvement. > --=20 > Best regards, > Micha=C5=82 G=C3=B3rny >=20