I apologize in advance - this is a long one - but I think it may have some big ramifications in terms of how jdbm uses disk space. Please let me know what you think:
Currently, once a record is allocated, that is it's size on disk for the=20
rest of time. This can cause some nasty fragmentation problems if=20
records of different sizes are freed and inserted many times - i.e. a 10=20
KB record is created and freed, then allocated again with only 100 bytes=20
of data. This space should be able to hold ~90 100 byte records, but it=20
will only contain 1 - the rest of the space is entirely wasted.
I would like to propose a strategy for ensuring that this fragmentation=20
doesn't get out of hand. The general idea is to combine adjacent freed=20
records. Then, when a record is used for data that requires less space=20
than it has allocated, the record is split into two - one used record=20
containing the required space, and one free record containing the=20
There's two part to this - the thoughts below address only the merging=20
of adjacent freed records. Splitting an existing free record to create=20
a used record and another free record should be relatively easy.
Page/Block - a fixed length holder of data
Record - a variable length holder of data - records reside inside one=20
or more pages, and can start anywhere inside a given page. If the data=20
is larger than the space in the first page, additional pages can be=20
tacked on as needed.
When freeing a record, do two checks:
1. Get the NEXT record (from the length of the record being freed) and=20
see if it is also free. If it is, then:
a) Remove the NEXT record from the free physical and free logical row=20
id lists (more on how to do this in a second)
b) Extend the available length of the record being freed so it includes=20
the NEXT record (including headers)
2. Get the PREVIOUS record (more on how to do this in a second) and see=20
if it is also free. If it is, then:
a) Do NOT add the current record to the free physical and logical row=20
b) Extend the available length of the PREVIOUS record so it includes=20
the current record (including headers)
both of these operations should be performed in order, so 2(b) will pick=20
up the result of 1(b) if we are freeing a record that lands in between=20
two already free records.
OK - details on how to do this tricky stuff:
Getting the PREVIOUS record:
We are going to use the ability of the DataPage class to access it's=20
previous data page, and it's on-page first record. Here's how:
Get the current page's first record
if it is not equal to the record we are freeing, then this is the page=20
that contains the previous record
if it is equal to the record we are freeing, then get the previous page=20
and check it's first record - continue getting previous pages until we=20
get one that has a valid first record (i.e. offset not equal to 0)
We now have the page containing the previous record
Now, start with the first record and get it's next record. Continue=20
doing this until the next record is either past the end of the page, or=20
equal to the record we are freeing.
At this point, we have the previous record
Removing a specific record from the free logical and free physical row=20
Now, how do we remove a given record that has already been freed from=20
the free logical and free physical row id list?
We have a fighting chance of doing the physical list by doing a linear=20
search for the record id we already know, but we have no chance at all=20
of performing a reverse lookup to obtain the logical row id...
I'm going to propose a small change to the behavior of a freed record. =20
When freeing, the id of both the free logical and free physical row id=20
should be written into the record data. Basically, the header structure=20
for a free record changes so it has an additional 2 values.
The tricky part here is what if the data block of the record being freed=20
isn't large enough to hold an additional 2 values?
Maybe there is a way to cram that data into the current header structure...
The record header currently contains 2 short values. One for current=20
size and one for available size. At minimum, we have to hold on to the=20
available size value. That pretty much guarantees that there's no way=20
we can cram that much info in...
To specify an entry in the free list, we could list it's slot number=20
from the first page of the free list. The free list could then be=20
walked relatively quickly to find the entry that needs to be removed. =20
We start to have problems with the size of the free list being limited=20
if we choose a data value that's too small. Realistically, we'd need 4=20
bytes for each value (ideally, we'd have 8 bytes, which would just give=20
us the block id and offset of the slot we want to remove).
So, we would need to ensure that the data size of the record being freed=20
is at least 16 bytes. Now, interestingly, the physical row id manager's=20
allocNew() method actually guarantees that there will be enough space if=20
the record being freed is towards the *end* of it's page (this is good=20
because it means that we don't have to be concerned about the=20
information flowing onto the next page - it's a minor point, but it will=20
simplify the code a tad). That doesn't help us, however, if we have a=20
bunch of tiny (< 16 byte) records all added in a row.
OK - in a worst case scenario, we can always just do a linear search of=20
the entire free list to find what we are looking for. So, we look at=20
the available size of the record being freed. If it's big enough to=20
contain the free phyiscal info, we extract it and use it. If not, we do=20
a linear search.=20
But what about the free logical row id table? The strategy of storing=20
the logical row id in the freed record's data block makes this trivial. =20
However, if we have to do a linear search of the free logical table,=20
then we have a problem, because we don't actually have the logical row=20
id for the record we need to free.
So, I'm going to propose a couple of things:
1. The free logical row info gets stored first - so if the record data=20
size is between 8 and 15 bytes, then we have a somewhat reasonable way=20
to handle this thing (i.e. linear search of free phyiscal table only).
2. If the data size is less than 8 bytes, then we just won't try to do=20
this kind of recovery. We may even want to bump decision #1 up to 16=20
bytes just to get rid of the linear search of the physical table.