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

[Tatsuo Ishii]

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
-------------- next part --------------
/* -*-pgsql-c-*- */
/*
 *
 * $Header: /cvsroot/pgpool/pgpool-II/pool.h,v 1.90 2011/05/02 13:31:25 t-ishii Exp $
 *
 * pgpool: a language independent connection pool server for PostgreSQL 
 * written by Tatsuo Ishii
 *
 * Copyright (c) 2003-2011	PgPool Global Development Group
 *
 * Permission to use, copy, modify, and distribute this software and
 * its documentation for any purpose and without fee is hereby
 * granted, provided that the above copyright notice appear in all
 * copies and that both that copyright notice and this permission
 * notice appear in supporting documentation, and that the name of the
 * author not be used in advertising or publicity pertaining to
 * distribution of the software without specific, written prior
 * permission. The author makes no representations about the
 * suitability of this software for any purpose.  It is provided "as
 * is" without express or implied warranty.
 *
 * pool_memqcache.h: on memory query cache related definitions
 *
 */

#ifndef POOL_MEMQCACHE_H
#define POOL_MEMQCACHE_H

#include "pool.h"
#include <sys/time.h>

/*
 * On memory query cache on shmem is devided into fixed length "cache
 * block". Each block is assigned a "cache block id", which is
 * starting with 0.
 */
typedef char *POOL_CACH_BLOCK;		/* pointer to cache block */
typedef unsigned int POOL_CACHE_BLOCKID;		/* cache block id */
typedef unsigned int POOL_CACHE_ITEMID;		/* cache item id */

/*
 * "Cache id" represents "absolute address" of a cache item.
 */
typedef struct {
	POOL_CACHE_BLOCKID	blockid;
	POOL_CACHE_ITEMID	itemid;
} POOL_CACHEID;	/* cache id */

/*
 * Each block has management space called "cache block header" at the
 * very beginning of the cache block.
 */

#define POOL_BLOCK_USED	0x0001		/* is this block used? */

typedef struct {
	unsigned char flags;		/* flags. see above */
	unsigned short num_items;		/* number of items */
	unsigned short free_bytes;		/* total free space in bytes */	
} POOL_CACHE_BLOCK_HEADER;

typedef struct {
	char query_hash[32];
} POOL_QUERY_HASH;

#define POOL_ITEM_USED	0x0001		/* is this item used? */
	
typedef struct {
	POOL_QUERY_HASH query_hash;	/* md5 hashed query signature */
	unsigned short offset;		/* item offset in this block */
	unsigned char flags;		/* flags. see above */
} POOL_CACHE_ITEM_POINTER;

/*
 * Each block holds several "cach item", which is consisted with
 * variable lenghth of Data(header plus RowDescription packet and
 * DataRow packet).  Each cache item is assigned "cache item id",
 * which represents the cache item order in a block.
 */

/*
 * "Cache Item" structure holds a SELECT result having several row
 * data in memory cache.  Cache item can be used with either shmem or
 * memcached.
 */

/*
 * Row description packet
 */
typedef struct {
	unsigned int length;		/* packet length including myself */
	char packet[1];		/* variable length packet */
} POOL_ROW_DESCRIPTION;

/*
 * Single row packet
 */
typedef struct {
	unsigned int length;		/* packet length including myself */
	char packet[1];		/* variable length packet */
} POOL_DATA_ROW;

/*
 * "Cache Item header" structure is used to manage each cache item.
 */
typedef struct {
	unsigned int total_length;	/* total length in bytes including myself */
	struct timeval timestamp;	/* cache creation time */
} POOL_CACHE_ITEM_HEADER;

typedef struct {
	POOL_CACHE_ITEM_HEADER header;		/* cache item header */
	POOL_ROW_DESCRIPTION row_description;		/* after row description, data rows follows... */
	POOL_DATA_ROW data_row[1];	/* variable length data row */
} POOL_CACHE_ITEM;

#endif POOL_MEMQCACHE_H