1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
|
=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
|
