new disk cache fixed block size model suggestion

[Aaron Smuts <as...@yahoo.com>]

Since I've been working on the optimization patch,
I've been watching the disk cache behavior for a while
and I noticed a few, relatively obvious things.  If
the objects you put on disk are all the same size,
then the recycle bin is very effective.  When you
reach the max keys, the disk size will stay constant,
since every item put on disk can reuse an existing
spot.  

Overall, the pre-optimized disk size stays much
smaller when the size of the objects is the same,
compared to the situation where the object sizes vary.
 The more variation, the greater the chance that the
recycle bin spot will be a bit larger than you need. 
That means that the extra is wasted.  Do this enough
and you end up with a lot of free, unusable spaces
between items.

Since many real world case will involve items of
varying sizes, the disk will require optimization
eventually.  There may be a way to make optimization
unnecessary.

Rather than using the exactly the amount of space
needed for an item, we could used fixed block sizes. 
If an item fits in a block, great.  At worst we wasted
space in the block, as we almost always do with the
current recycle bin.  If it doesn't fit in a block, it
will be divided between blocks.  

The disadvantages of this model are that a divided
item is slower to write and slower to read, so it is
best if the block sizes are large enough to minimize
splits.  However, if the size is too large, then you
waste to much space.  

The big advantage is that you will never need to
optimize.  The recycle bin can be much larger and very
simple.  It would simply be a list of positions.  No
size data is needed, since all the blocks are the same
size.  We'd never need to optimize since eventually,
all the spaces would be reclaimed if the disk cache
ever reached the same size.  The position simply
becomes an int, since we don't need offset, we merely
need the slot number. . .  The key map would be
smaller and easier to write to disk.  The first 4
bytes on disk would indicate the size of all the other
blocks, so we could determine the size on startup.  

We could also persist the key map in a similar
fashion.  In memory we could keep the key, an array of
spot numbers on disk for the data, and an array of
spot numbers for the key in the key file.  The key
file would have the key and the block number.  If we
could require that all the keys fit into one block,
then we could just use the first block number in the
data file as the key block number.  Either way, we
could bake in key persistence.

The advantages make it worth trying.  I'm considering
building another indexed disk cache that works on the
block model.  By default we would use the size of the
first element inserted as the block size.  We could
also make the block size configurable.

Aaron




---------------------------------------------------------------------
To unsubscribe, e-mail: jcs-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: jcs-dev-help@jakarta.apache.org

Re: new disk cache fixed block size model suggestion

[Aaron Smuts <as...@yahoo.com>]

--- Hanson Char <ha...@gmail.com> wrote:

> >It would simply be a list of positions.  No
> > size data is needed, since all the blocks are the
> same
> > size.
> 
> If an item fits in a block, but has a size smaller
> than the block
> size, you still need to record the size data.  What
> am I missing here
> ?

Right now the recycle bin holds the length of the item
on disk.  Originally the length of the item was only
stored on disk, in the first 4 bytes of the record. 
Now (and for some time I think) the length is stored
along with the key and position in memory so it can be
used in the recycle bin.  This makes the length on
disk redundant.  The alternative would be to look up
the length when an item is removed and then store this
in the recylce bin.  This might be preferable, since
the overall memory usage would be 4 bytes lower per
entry. . . .

In the block model, the recycle bin no longer needs
the size, since all blocks are the same size.  You
still need to store the actual length of the item on
disk, but it would not be redundant.

Aaron

---------------------------------------------------------------------
To unsubscribe, e-mail: jcs-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: jcs-dev-help@jakarta.apache.org

Re: new disk cache fixed block size model suggestion

[Hanson Char <ha...@gmail.com>]

> Rather than using the exactly the amount of space
> needed for an item, we could used fixed block sizes.
> If an item fits in a block, great.  At worst we wasted
> space in the block, as we almost always do with the
> current recycle bin.  If it doesn't fit in a block, it
> will be divided between blocks.
...
>It would simply be a list of positions.  No
> size data is needed, since all the blocks are the same
> size.

If an item fits in a block, but has a size smaller than the block
size, you still need to record the size data.  What am I missing here
?

Hanson

---------------------------------------------------------------------
To unsubscribe, e-mail: jcs-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: jcs-dev-help@jakarta.apache.org