[Pgpool-hackers] Memory cache structure: on memory cache project

[Tatsuo Ishii]

Committed to CVS HEAD.
--
Tatsuo Ishii
SRA OSS, Inc. Japan
English: http://www.sraoss.co.jp/index_en.php
Japanese: http://www.sraoss.co.jp

> Hi,
> 
> As the mentor of Yamazaki's project, I have designed memory cache
> structure as a starting point(still work in progress). Comments are
> welcome.
> 
> (prototype implementation for this structure as a C header file
> attached)
> 
> Managing table oids
> 
> On memory query cache (OMQC) needs to keep track tables used in
> SELECTs. For this purpose, OMQC extracts table OIDs from RowDescrption
> packet and registers on a hash table on shmem. If corresponding
> DDL/DCL finds target table OID in the table, corresponding cache is
> discarded. The key for the hash table is table OID and data is "cache
> id" (explained later).
>   
> If memcached is used instead of shmem, the hash table can be stored on
> memcached.
> 
> On memory query cache (OMQC) structure
> 
> OMQC is a large one-dimension array on shmem. It is devided into fixed
> length of "cache block". Each block is assigned a "cache block id",
> which is a subscript of the array and starts from 0.
> 
> Each cache block holds several variable length cache data, which is
> essentially RowDescrption and DataRow packets plus some management
> data.
> 
> Each cache block has management space called "cache block header" at
> the very beginning of the cache block. This is an array which points
> to the cache data in the cache block plus special management
> data. Each array item is assigned "cache item id".
> 
> "Cache id", which is consists of cache block id and cache item id,
> uniquely identifies each cache item.
> 
> Cache data is stored in a cache block without gaps or spaces if
> possible.
> 
> If a target table is modified, OMQC gets cache id from the hash table
> explained above and deletes cache entries which uses the tables then
> registers the space into "space management map".
> 
> The space management map
> 
> The space management map(SMM) is placed on shmem and is used to search
> a block which has enough free space. SMM consists of many 1-byte data,
> which corresponds to cache block id. For example, if total cache size
> is 1GB and cache block size if 8KB, we have 131,072 cache blocks and
> the size of SMM is 128KB.
> 
> SMM is managed in a similar way PostgreSQL free space map does.  Each
> SMM entry has an "encoded" value which represents the size range of
> the corresponding cache block. If the encoded value is 0, then free
> space in the cache block is less than 32 bytes. If the encoded value
> is 1, then free space in the cache block is between 32 to 63 bytes.
> If the encoded value is 2, then free space in the cache block is
> between 64 to 96 bytes.  If the encoded value is 255, then free space
> in the cache block is between 8160 to 8192 bytes and so on.
> 
> If we need a cache block which has necessary free space, we search
> SMM. If the free space in the cache block is not continuous, we move
> the cache items in the cache block to make continuous free
> space. Note. As on a running system almost all cache blocks are used,
> we'd better to have "free cache block list".
> 
> If no cache block having enough free space, we discard a cache block
> which is likely least recently used. Because "Pure" LRU is expensive,
> we consider "clock sweep" algorithm, which is used in PostgreSQL
> buffer manager as well.
> --
> Tatsuo Ishii
> SRA OSS, Inc. Japan
> English: http://www.sraoss.co.jp/index_en.php
> Japanese: http://www.sraoss.co.jp