Date: Sat, 28 Oct 2000 22:47:53 -0700 (PDT) From: Luigi Rizzo <rizzo@ICSI.Berkeley.EDU> To: Ryan Thompson <ryan@sasknow.com> Cc: freebsd-hackers@FreeBSD.ORG Subject: Re: Filesystem holes Message-ID: <Pine.GSO.4.21.0010282230110.10039-100000@fondue.ICSI.Berkeley.EDU> In-Reply-To: <Pine.BSF.4.21.0010282036360.68895-100000@ren.sasknow.com>
next in thread | previous in thread | raw e-mail | index | archive | help
Hi, how about using an indirect table of 64M 32-bit pointers into the actual blocks being used ? For insertions you just allocate a new fixed size block from the file. For deletion, either keep a list of freed blocks, or provide a back pointer from each entry into the hash table so when you remove a block (creating a hole) you can move the last allocated one into the hole and update the hash table. Kind of quick. You might have to pay an extra disk access on each access but given enough memory you'd save that one as well. cheers luigi ----------------------------------+----------------------------------------- Luigi RIZZO, luigi@iet.unipi.it . ACIRI/ICSI (on leave from Univ. di Pisa) http://www.iet.unipi.it/~luigi/ . 1947 Center St, Berkeley CA 94704 Phone: (510) 666 2927 ----------------------------------+----------------------------------------- On Sat, 28 Oct 2000, Ryan Thompson wrote: > > Hi all... > > One the tasks that I have undertaken lately is to improve the efficiency > of a couple of storage facilities we use internally, here. Basically, > they are moderate-size tables currently implemented in SQL, which is OK in > terms of performance, but the hash function is breaking down and the > storage is rather inefficient for our table of about 2,850,000 members > (~2.1 GB total storage). There are 64M possible hash values in our > current implementation, and our record size is variable, but could be > safely fixed at about 1.5KB... So, total storage if all values were used > would be about 96GB. (See where I'm going with this?) > > One of the options I am considering is actually using address calculation, > and taking advantage of filesystem holes, to keep storage down to what is > actually being used, while providing instant lookups. > > The single file would be about 96G addressable bytes... But the actual > block count would be much lower. I suppose I will have to create a series > of these files and divide the problem into < 4GB chunks, but one > lookup/store will still be done with one calculation and one disk seek > (just more filehandles open). > > Deletes seem problematic. My question is, does the operating system > provide any way to free blocks used in the middle of a file? > > Must I periodically re-create these files (long and slow process, but not > so bad if done infrequently) to reclaim space, or is there a way to free > arbitrary blocks in a file in userland (WITHOUT trashing the filesystem? > :-) > > - Ryan > > -- > Ryan Thompson <ryan@sasknow.com> > Network Administrator, Accounts > Phone: +1 (306) 664-1161 > > SaskNow Technologies http://www.sasknow.com > #106-380 3120 8th St E Saskatoon, SK S7H 0W2 > To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-hackers" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?Pine.GSO.4.21.0010282230110.10039-100000>