Commit | Line | Data |
d8db2929 |
1 | =head1 NAME |
2 | |
3 | DBM::Deep::Internals |
4 | |
5 | =head1 DESCRIPTION |
6 | |
7 | This is a document describing the internal workings of L<DBM::Deep/>. It is |
8 | not necessary to read this document if you only intend to be a user. This |
9 | document is intended for people who either want a deeper understanding of |
10 | specifics of how L<DBM::Deep/> works or who wish to help program |
11 | L<DBM::Deep/>. |
12 | |
13 | =head1 CLASS LAYOUT |
14 | |
15 | L<DBM::Deep/> is broken up into five classes in three inheritance hierarchies. |
16 | |
17 | =over 4 |
18 | |
19 | =item * |
20 | |
21 | L<DBM::Deep/> is the parent of L<DBM::Deep::Array/> and L<DBM::Deep::Hash/>. |
22 | These classes form the immediate interface to the outside world. They are the |
23 | classes that provide the TIE mechanisms as well as the OO methods. |
24 | |
25 | =item * |
26 | |
27 | L<DBM::Deep::Engine/> is the layer that deals with the mechanics of reading |
28 | and writing to the file. This is where the logic of the file layout is |
29 | handled. |
30 | |
31 | =item * |
32 | |
33 | L<DBM::Deep::File/> is the layer that deals with the physical file. As a |
34 | singleton that every other object has a reference to, it also provides a place |
35 | to handle datastructure-wide items, such as transactions. |
36 | |
37 | =back |
38 | |
39 | =head1 FILE LAYOUT |
40 | |
41 | DBM::Deep uses a tagged file layout. Every section has a tag, a size, and then |
42 | the data. |
43 | |
44 | =head2 File header |
45 | |
46 | =over 4 |
47 | |
48 | =item * File Signature |
49 | |
50 | The first four bytes are 'DPDB' in network byte order, signifying that this is |
51 | a DBM::Deep file. |
52 | |
53 | =item * File tag/size |
54 | |
55 | This is the tagging of the file header. The file used by versions prior to |
56 | 1.00 had a different fifth byte, allowing the difference to the determined. |
57 | |
58 | =item * Version |
59 | |
60 | This is four bytes containing the header version. This lets the header change over time. |
61 | |
62 | =item * Transaction information |
63 | |
64 | The current running transactions are stored here, as is the next transaction |
65 | ID. |
66 | |
67 | =item * Constants |
68 | |
69 | These are the file-wide constants that determine how the file is laid out. |
70 | They can only be set upon file creation. |
71 | |
72 | =back |
73 | |
74 | =head2 Index |
75 | |
76 | The Index parts can be tagged either as Hash, Array, or Index. The latter |
77 | is if there was a reindexing due to a bucketlist growing too large. The others |
78 | are the root index for their respective datatypes. The index consists of a |
79 | tag, a size, and then 256 sections containing file locations. Each section |
80 | corresponds to each value representable in a byte. |
81 | |
82 | The index is used as follows - whenever a hashed key is being looked up, the |
83 | first byte is used to determine which location to go to from the root index. |
84 | Then, if that's also an index, the second byte is used, and so forth until a |
85 | bucketlist is found. |
86 | |
87 | =head2 Bucketlist |
88 | |
89 | This is the part that contains the link to the data section. A bucketlist |
90 | defaults to being 16 buckets long (modifiable by the I<max_buckets> |
91 | parameter used when creating a new file). Each bucket contains an MD5 and a |
92 | location of the appropriate key section. |
93 | |
94 | =head2 Key area |
95 | |
96 | This is the part that handles transactional awareness. There are |
97 | I<max_buckets> sections. Each section contains the location to the data |
98 | section, a transaction ID, and whether that transaction considers this key to |
99 | be deleted or not. |
100 | |
101 | =head2 Data area |
102 | |
103 | This is the part that actual stores the key, value, and class (if |
104 | appropriate). The layout is: |
105 | |
106 | =over 4 |
107 | |
108 | =item * tag |
109 | |
110 | =item * length of the value |
111 | |
112 | =item * the actual value |
113 | |
114 | =item * keylength |
115 | |
116 | =item * the actual key |
117 | |
118 | =item * a byte indicating if this value has a classname |
119 | |
120 | =item * the classname (if one is there) |
121 | |
122 | =back |
123 | |
124 | The key is stored after the value because the value is requested more often |
125 | than the key. |
126 | |
127 | =head1 PERFORMANCE |
128 | |
129 | L<DBM::Deep/> is written completely in Perl. It also is a multi-process DBM |
130 | that uses the datafile as a method of synchronizing between multiple |
131 | processes. This is unlike most RDBMSes like MySQL and Oracle. Furthermore, |
132 | unlike all RDBMSes, L<DBM::Deep/> stores both the data and the structure of |
133 | that data as it would appear in a Perl program. |
134 | |
135 | =head2 CPU |
136 | |
137 | DBM::Deep attempts to be CPU-light. As it stores all the data on disk, |
138 | DBM::Deep is I/O-bound, not CPU-bound. |
139 | |
140 | =head2 RAM |
141 | |
142 | DBM::Deep uses extremely little RAM relative to the amount of data you can |
143 | access. You can iterate through a million keys (using C<each()>) without |
144 | increasing your memeory usage at all. |
145 | |
146 | =head2 DISK |
147 | |
148 | DBM::Deep is I/O-bound, pure and simple. The faster your disk, the faster |
149 | DBM::Deep will be. Currently, when performing C<my $x = $db-E<gt>{foo}>, there |
150 | are a minimum of 4 seeks and 1332 + N bytes read (where N is the length of your |
151 | data). (All values assume a medium filesize.) The actions take are: |
152 | |
153 | =over 4 |
154 | |
155 | =item 1 Lock the file |
156 | |
157 | =item 1 Perform a stat() to determine if the inode has changed |
158 | |
159 | =item 1 Go to the primary index for the $db (1 seek) |
160 | |
161 | =item 1 Read the tag/size of the primary index (5 bytes) |
162 | |
163 | =item 1 Read the body of the primary index (1024 bytes) |
164 | |
165 | =item 1 Go to the bucketlist for this MD5 (1 seek) |
166 | |
167 | =item 1 Read the tag/size of the bucketlist (5 bytes) |
168 | |
169 | =item 1 Read the body of the bucketlist (144 bytes) |
170 | |
171 | =item 1 Go to the keys location for this MD5 (1 seek) |
172 | |
173 | =item 1 Read the tag/size of the keys section (5 bytes) |
174 | |
175 | =item 1 Read the body of the keys location (144 bytes) |
176 | |
177 | =item 1 Go to the data section that corresponds to this transaction ID. (1 seek) |
178 | |
179 | =item 1 Read the tag/size of the data section (5 bytes) |
180 | |
181 | =item 1 Read the value for this data (N bytes) |
182 | |
183 | =item 1 Unlock the file |
184 | |
185 | =back |
186 | |
187 | Every additional level of indexing (if there are enough keys) requires an |
188 | additional seek and the reading of 1029 additional bytes. If the value is |
189 | blessed, an additional 1 seek and 9 + M bytes are read (where M is the length |
190 | of the classname). |
191 | |
192 | Arrays are (currently) even worse because they're considered "funny hashes" |
193 | with the length stored as just another key. This means that if you do any sort |
194 | of lookup with a negative index, this entire process is performed twice - once |
195 | for the length and once for the value. |
196 | |
1990c72d |
197 | =head1 ACTUAL TESTS |
198 | |
199 | =head2 SPEED |
200 | |
201 | Obviously, DBM::Deep isn't going to be as fast as some C-based DBMs, such as |
202 | the almighty I<BerkeleyDB>. But it makes up for it in features like true |
203 | multi-level hash/array support, and cross-platform FTPable files. Even so, |
204 | DBM::Deep is still pretty fast, and the speed stays fairly consistent, even |
205 | with huge databases. Here is some test data: |
206 | |
207 | Adding 1,000,000 keys to new DB file... |
208 | |
209 | At 100 keys, avg. speed is 2,703 keys/sec |
210 | At 200 keys, avg. speed is 2,642 keys/sec |
211 | At 300 keys, avg. speed is 2,598 keys/sec |
212 | At 400 keys, avg. speed is 2,578 keys/sec |
213 | At 500 keys, avg. speed is 2,722 keys/sec |
214 | At 600 keys, avg. speed is 2,628 keys/sec |
215 | At 700 keys, avg. speed is 2,700 keys/sec |
216 | At 800 keys, avg. speed is 2,607 keys/sec |
217 | At 900 keys, avg. speed is 2,190 keys/sec |
218 | At 1,000 keys, avg. speed is 2,570 keys/sec |
219 | At 2,000 keys, avg. speed is 2,417 keys/sec |
220 | At 3,000 keys, avg. speed is 1,982 keys/sec |
221 | At 4,000 keys, avg. speed is 1,568 keys/sec |
222 | At 5,000 keys, avg. speed is 1,533 keys/sec |
223 | At 6,000 keys, avg. speed is 1,787 keys/sec |
224 | At 7,000 keys, avg. speed is 1,977 keys/sec |
225 | At 8,000 keys, avg. speed is 2,028 keys/sec |
226 | At 9,000 keys, avg. speed is 2,077 keys/sec |
227 | At 10,000 keys, avg. speed is 2,031 keys/sec |
228 | At 20,000 keys, avg. speed is 1,970 keys/sec |
229 | At 30,000 keys, avg. speed is 2,050 keys/sec |
230 | At 40,000 keys, avg. speed is 2,073 keys/sec |
231 | At 50,000 keys, avg. speed is 1,973 keys/sec |
232 | At 60,000 keys, avg. speed is 1,914 keys/sec |
233 | At 70,000 keys, avg. speed is 2,091 keys/sec |
234 | At 80,000 keys, avg. speed is 2,103 keys/sec |
235 | At 90,000 keys, avg. speed is 1,886 keys/sec |
236 | At 100,000 keys, avg. speed is 1,970 keys/sec |
237 | At 200,000 keys, avg. speed is 2,053 keys/sec |
238 | At 300,000 keys, avg. speed is 1,697 keys/sec |
239 | At 400,000 keys, avg. speed is 1,838 keys/sec |
240 | At 500,000 keys, avg. speed is 1,941 keys/sec |
241 | At 600,000 keys, avg. speed is 1,930 keys/sec |
242 | At 700,000 keys, avg. speed is 1,735 keys/sec |
243 | At 800,000 keys, avg. speed is 1,795 keys/sec |
244 | At 900,000 keys, avg. speed is 1,221 keys/sec |
245 | At 1,000,000 keys, avg. speed is 1,077 keys/sec |
246 | |
247 | This test was performed on a PowerMac G4 1gHz running Mac OS X 10.3.2 & Perl |
248 | 5.8.1, with an 80GB Ultra ATA/100 HD spinning at 7200RPM. The hash keys and |
249 | values were between 6 - 12 chars in length. The DB file ended up at 210MB. |
250 | Run time was 12 min 3 sec. |
251 | |
252 | =head2 MEMORY USAGE |
253 | |
254 | One of the great things about L<DBM::Deep/> is that it uses very little memory. |
255 | Even with huge databases (1,000,000+ keys) you will not see much increased |
256 | memory on your process. L<DBM::Deep/> relies solely on the filesystem for storing |
257 | and fetching data. Here is output from I<top> before even opening a database |
258 | handle: |
259 | |
260 | PID USER PRI NI SIZE RSS SHARE STAT %CPU %MEM TIME COMMAND |
261 | 22831 root 11 0 2716 2716 1296 R 0.0 0.2 0:07 perl |
262 | |
263 | Basically the process is taking 2,716K of memory. And here is the same |
264 | process after storing and fetching 1,000,000 keys: |
265 | |
266 | PID USER PRI NI SIZE RSS SHARE STAT %CPU %MEM TIME COMMAND |
267 | 22831 root 14 0 2772 2772 1328 R 0.0 0.2 13:32 perl |
268 | |
269 | Notice the memory usage increased by only 56K. Test was performed on a 700mHz |
270 | x86 box running Linux RedHat 7.2 & Perl 5.6.1. |
271 | |
d8db2929 |
272 | =cut |