Re: Free Space Map data structure

Pavan Deolasee wrote:
> Can we not use bitmaps to track approximate rather than exact free
> space ? For example, we can have 8 or 16 buckets of free space.
> A page with 1-32 bytes free, goes into bucket 1, a page with at 33-64 bytes
> free, goes into bucket 2 and so on. If you want a page with X bytes free,
> look into the next immediate larger bucket. (the ranges can varry here)

Yep, that's actually what I was planning to do, except I was thinking of
using 8 bits per page, or 256 buckets, because that makes the code a
little bit simpler. 16 buckets would probably be enough in practice, though.

Also, the free space doesn't necessarily need to be divided linearly
into buckets, we could for example use 8 buckets like:

0 32
1 64
2 128
3 256
4 512
5 1024
6 2048
7 4096

> This would give us O(1) time for FSM updates. To speed up lookup, we
> can use hierarchical bitmaps. Lets work through an example for 8 buckets:
>
> At the segment level, we have one FSM page. That can summarize FSM
> info for ~8000 heap page (1 bit per page per bucket). In addition, we
> can have first level hierarchy in the same page where one bit, say
> summarizes info for 100 pages. So if there a page with 'bucket' worth
> of free space in the first 100 pages in the segment, the corresponding
> bit in the first hierarchy will be set. In this case, the first level hierarchy
> would need 80 bits per bucket i.e 80 bytes.
>
> We can then extend the concept of segments to say, 'extents'. One FSM page
> per extent summarizes the FSM info for segments in that extent. With the same
> logic as above, we can have ~8000 segments per extent.
>
> And then one FSM page to summarize info for all extents. I guess at that
> level we would run out of maximum supported file size anyways.

Well, if you add the higher levels, we're no longer talking about O(1),
but O(log n) (for a pretty steep logarithm), just like my proposal.

> Well, this could be completely orthogonal to suggestions you are seeking,
> but nevertheless I had this thought for quite some time.

It's actually not that orthogonal. You describe it as a hierarchical
bitmap, but it's essentially the same idea as the binary heap/tree, just
with way more than 2 children per parent.

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com