diff options
Diffstat (limited to 'Master/tlpkg/tlperl/lib/DBM/Deep/Internals.pod')
-rwxr-xr-x | Master/tlpkg/tlperl/lib/DBM/Deep/Internals.pod | 281 |
1 files changed, 0 insertions, 281 deletions
diff --git a/Master/tlpkg/tlperl/lib/DBM/Deep/Internals.pod b/Master/tlpkg/tlperl/lib/DBM/Deep/Internals.pod deleted file mode 100755 index 132bc9eff17..00000000000 --- a/Master/tlpkg/tlperl/lib/DBM/Deep/Internals.pod +++ /dev/null @@ -1,281 +0,0 @@ -=head1 NAME - -DBM::Deep::Internals - -=head1 DESCRIPTION - -B<NOTE>: This document is out-of-date. It describes an intermediate file -format used during the development from 0.983 to 1.0000. It will be rewritten -soon. - -This is a document describing the internal workings of L<DBM::Deep>. It is -not necessary to read this document if you only intend to be a user. This -document is intended for people who either want a deeper understanding of -specifics of how L<DBM::Deep> works or who wish to help program -L<DBM::Deep>. - -=head1 CLASS LAYOUT - -L<DBM::Deep> is broken up into five classes in three inheritance hierarchies. - -=over 4 - -=item * - -L<DBM::Deep> is the parent of L<DBM::Deep::Array> and L<DBM::Deep::Hash>. -These classes form the immediate interface to the outside world. They are the -classes that provide the TIE mechanisms as well as the OO methods. - -=item * - -L<DBM::Deep::Engine> is the layer that deals with the mechanics of reading -and writing to the file. This is where the logic of the file layout is -handled. - -=item * - -L<DBM::Deep::File> is the layer that deals with the physical file. As a -singleton that every other object has a reference to, it also provides a place -to handle datastructure-wide items, such as transactions. - -=back - -=head1 FILE LAYOUT - -DBM::Deep uses a tagged file layout. Every section has a tag, a size, and then -the data. - -=head2 File header - -=over 4 - -=item * File Signature - -The first four bytes are 'DPDB' in network byte order, signifying that this is -a DBM::Deep file. - -=item * File tag/size - -This is the tagging of the file header. The file used by versions prior to -1.00 had a different fifth byte, allowing the difference to the determined. - -=item * Version - -This is four bytes containing the file version. This lets the file format change over time. - -=item * Constants - -These are the file-wide constants that determine how the file is laid out. -They can only be set upon file creation. - -=item * Transaction information - -The current running transactions are stored here, as is the next transaction -ID. - -=item * Freespace information - -Pointers into the next free sectors of the various sector sizes (Index, -Bucketlist, and Data) are stored here. - -=back - -=head2 Index - -The Index parts can be tagged either as Hash, Array, or Index. The latter -is if there was a reindexing due to a bucketlist growing too large. The others -are the root index for their respective datatypes. The index consists of a -tag, a size, and then 256 sections containing file locations. Each section -corresponds to each value representable in a byte. - -The index is used as follows - whenever a hashed key is being looked up, the -first byte is used to determine which location to go to from the root index. -Then, if that's also an index, the second byte is used, and so forth until a -bucketlist is found. - -=head2 Bucketlist - -This is the part that contains the link to the data section. A bucketlist -defaults to being 16 buckets long (modifiable by the I<max_buckets> -parameter used when creating a new file). Each bucket contains an MD5 and a -location of the appropriate key section. - -=head2 Key area - -This is the part that handles transactional awareness. There are -I<max_buckets> sections. Each section contains the location to the data -section, a transaction ID, and whether that transaction considers this key to -be deleted or not. - -=head2 Data area - -This is the part that actual stores the key, value, and class (if -appropriate). The layout is: - -=over 4 - -=item * tag - -=item * length of the value - -=item * the actual value - -=item * keylength - -=item * the actual key - -=item * a byte indicating if this value has a classname - -=item * the classname (if one is there) - -=back - -The key is stored after the value because the value is requested more often -than the key. - -=head1 PERFORMANCE - -L<DBM::Deep> is written completely in Perl. It also is a multi-process DBM -that uses the datafile as a method of synchronizing between multiple -processes. This is unlike most RDBMSes like MySQL and Oracle. Furthermore, -unlike all RDBMSes, L<DBM::Deep> stores both the data and the structure of -that data as it would appear in a Perl program. - -=head2 CPU - -DBM::Deep attempts to be CPU-light. As it stores all the data on disk, -DBM::Deep is I/O-bound, not CPU-bound. - -=head2 RAM - -DBM::Deep uses extremely little RAM relative to the amount of data you can -access. You can iterate through a million keys (using C<each()>) without -increasing your memeory usage at all. - -=head2 DISK - -DBM::Deep is I/O-bound, pure and simple. The faster your disk, the faster -DBM::Deep will be. Currently, when performing C<my $x = $db-E<gt>{foo}>, there -are a minimum of 4 seeks and 1332 + N bytes read (where N is the length of your -data). (All values assume a medium filesize.) The actions taken are: - -=over 4 - -=item 1 Lock the file - -=item 1 Perform a stat() to determine if the inode has changed - -=item 1 Go to the primary index for the $db (1 seek) - -=item 1 Read the tag/size of the primary index (5 bytes) - -=item 1 Read the body of the primary index (1024 bytes) - -=item 1 Go to the bucketlist for this MD5 (1 seek) - -=item 1 Read the tag/size of the bucketlist (5 bytes) - -=item 1 Read the body of the bucketlist (144 bytes) - -=item 1 Go to the keys location for this MD5 (1 seek) - -=item 1 Read the tag/size of the keys section (5 bytes) - -=item 1 Read the body of the keys location (144 bytes) - -=item 1 Go to the data section that corresponds to this transaction ID. (1 seek) - -=item 1 Read the tag/size of the data section (5 bytes) - -=item 1 Read the value for this data (N bytes) - -=item 1 Unlock the file - -=back - -Every additional level of indexing (if there are enough keys) requires an -additional seek and the reading of 1029 additional bytes. If the value is -blessed, an additional 1 seek and 9 + M bytes are read (where M is the length -of the classname). - -Arrays are (currently) even worse because they're considered "funny hashes" -with the length stored as just another key. This means that if you do any sort -of lookup with a negative index, this entire process is performed twice - once -for the length and once for the value. - -=head1 ACTUAL TESTS - -=head2 SPEED - -Obviously, DBM::Deep isn't going to be as fast as some C-based DBMs, such as -the almighty I<BerkeleyDB>. But it makes up for it in features like true -multi-level hash/array support, and cross-platform FTPable files. Even so, -DBM::Deep is still pretty fast, and the speed stays fairly consistent, even -with huge databases. Here is some test data: - - Adding 1,000,000 keys to new DB file... - - At 100 keys, avg. speed is 2,703 keys/sec - At 200 keys, avg. speed is 2,642 keys/sec - At 300 keys, avg. speed is 2,598 keys/sec - At 400 keys, avg. speed is 2,578 keys/sec - At 500 keys, avg. speed is 2,722 keys/sec - At 600 keys, avg. speed is 2,628 keys/sec - At 700 keys, avg. speed is 2,700 keys/sec - At 800 keys, avg. speed is 2,607 keys/sec - At 900 keys, avg. speed is 2,190 keys/sec - At 1,000 keys, avg. speed is 2,570 keys/sec - At 2,000 keys, avg. speed is 2,417 keys/sec - At 3,000 keys, avg. speed is 1,982 keys/sec - At 4,000 keys, avg. speed is 1,568 keys/sec - At 5,000 keys, avg. speed is 1,533 keys/sec - At 6,000 keys, avg. speed is 1,787 keys/sec - At 7,000 keys, avg. speed is 1,977 keys/sec - At 8,000 keys, avg. speed is 2,028 keys/sec - At 9,000 keys, avg. speed is 2,077 keys/sec - At 10,000 keys, avg. speed is 2,031 keys/sec - At 20,000 keys, avg. speed is 1,970 keys/sec - At 30,000 keys, avg. speed is 2,050 keys/sec - At 40,000 keys, avg. speed is 2,073 keys/sec - At 50,000 keys, avg. speed is 1,973 keys/sec - At 60,000 keys, avg. speed is 1,914 keys/sec - At 70,000 keys, avg. speed is 2,091 keys/sec - At 80,000 keys, avg. speed is 2,103 keys/sec - At 90,000 keys, avg. speed is 1,886 keys/sec - At 100,000 keys, avg. speed is 1,970 keys/sec - At 200,000 keys, avg. speed is 2,053 keys/sec - At 300,000 keys, avg. speed is 1,697 keys/sec - At 400,000 keys, avg. speed is 1,838 keys/sec - At 500,000 keys, avg. speed is 1,941 keys/sec - At 600,000 keys, avg. speed is 1,930 keys/sec - At 700,000 keys, avg. speed is 1,735 keys/sec - At 800,000 keys, avg. speed is 1,795 keys/sec - At 900,000 keys, avg. speed is 1,221 keys/sec - At 1,000,000 keys, avg. speed is 1,077 keys/sec - -This test was performed on a PowerMac G4 1gHz running Mac OS X 10.3.2 & Perl -5.8.1, with an 80GB Ultra ATA/100 HD spinning at 7200RPM. The hash keys and -values were between 6 - 12 chars in length. The DB file ended up at 210MB. -Run time was 12 min 3 sec. - -=head2 MEMORY USAGE - -One of the great things about L<DBM::Deep> is that it uses very little memory. -Even with huge databases (1,000,000+ keys) you will not see much increased -memory on your process. L<DBM::Deep> relies solely on the filesystem for storing -and fetching data. Here is output from I<top> before even opening a database -handle: - - PID USER PRI NI SIZE RSS SHARE STAT %CPU %MEM TIME COMMAND - 22831 root 11 0 2716 2716 1296 R 0.0 0.2 0:07 perl - -Basically the process is taking 2,716K of memory. And here is the same -process after storing and fetching 1,000,000 keys: - - PID USER PRI NI SIZE RSS SHARE STAT %CPU %MEM TIME COMMAND - 22831 root 14 0 2772 2772 1328 R 0.0 0.2 13:32 perl - -Notice the memory usage increased by only 56K. Test was performed on a 700mHz -x86 box running Linux RedHat 7.2 & Perl 5.6.1. - -=cut |