本节简单介绍了PostgreSQL缓存管理(Buffer Manager)中的实现函数ReadBuffer_common->BufferAlloc->BufTableHashCode,该函数根据BufferTag计算Hash Code。
一、数据结构
BufferDesc
共享缓冲区的共享描述符(状态)数据
//buffer header锁定
#define BM_LOCKED (1U << 22)
//数据需要写入(标记为DIRTY)
#define BM_DIRTY (1U << 23)
//数据是有效的
#define BM_VALID (1U << 24)
//已分配buffer tag
#define BM_TAG_VALID (1U << 25)
//正在R/W
#define BM_IO_IN_PROGRESS (1U << 26)
//上一个I/O出现错误
#define BM_IO_ERROR (1U << 27)
//开始写则变DIRTY
#define BM_JUST_DIRTIED (1U << 28)
//存在等待sole pin的其他进程
#define BM_PIN_COUNT_WAITER (1U << 29)
//checkpoint发生,必须刷到磁盘上
#define BM_CHECKPOINT_NEEDED (1U << 30)
//持久化buffer(不是unlogged或者初始化fork)
#define BM_PERMANENT (1U << 31)
typedef struct BufferDesc
{
//buffer tag
BufferTag tag;
//buffer索引编号(0开始),指向相应的buffer pool slot
int buf_id;
//tag状态,包括flags/refcount和usagecount
pg_atomic_uint32 state;
//pin-count等待进程ID
int wait_backend_pid;
//空闲链表链中下一个空闲的buffer
int freeNext;
//缓冲区内容锁
LWLock content_lock;
} BufferDesc;
BufferTag
Buffer tag标记了buffer存储的是磁盘中哪个block
typedef struct buftag
{
//物理relation标识符
RelFileNode rnode;
ForkNumber forkNum;
//相对于relation起始的块号
BlockNumber blockNum;
} BufferTag;
HTAB
哈希表的顶层控制结构.
struct HTAB
{
//指向共享的控制信息
HASHHDR *hctl;
//段开始目录
HASHSEGMENT *dir;
//哈希函数
HashValueFunc hash;
//哈希键比较函数
HashCompareFunc match;
//哈希键拷贝函数
HashCopyFunc keycopy;
//内存分配器
HashAllocFunc alloc;
//内存上下文
MemoryContext hcxt;
//表名(用于错误信息)
char *tabname;
//如在共享内存中,则为T
bool isshared;
//如为T,则固定大小不能扩展
bool isfixed;
//不允许冻结共享表,因此这里会保存相关状态
bool frozen;
//保存这些固定值的本地拷贝,以减少冲突
//哈希键长度(以字节为单位)
Size keysize;
//段大小,必须为2的幂
long ssize;
//段偏移,ssize的对数
int sshift;
};
struct HASHHDR
{
FreeListData freeList[NUM_FREELISTS];
//这些域字段可以改变,但不适用于分区表
//同时,就算是非分区表,共享表的dsize也不能改变
//目录大小
long dsize;
//已分配的段大小(<= dbsize)
long nsegs;
//正在使用的最大桶ID
uint32 max_bucket;
//进入整个哈希表的模掩码
uint32 high_mask;
//进入低于半个哈希表的模掩码
uint32 low_mask;
//下面这些字段在哈希表创建时已固定
//哈希键大小(以字节为单位)
Size keysize;
//所有用户元素大小(以字节为单位)
Size entrysize;
//分区个数(2的幂),或者为0
long num_partitions;
//目标的填充因子
long ffactor;
//如目录是固定大小,则该值为dsize的上限值
long max_dsize;
//段大小,必须是2的幂
long ssize;
//端偏移,ssize的对数
int sshift;
//一次性分配的条目个数
int nelem_alloc;
#ifdef HASH_STATISTICS
long accesses;
long collisions;
#endif
};
typedef struct HASHELEMENT
{
//链接到相同桶中的下一个条目
struct HASHELEMENT *link;
//该条目的哈希函数结果
uint32 hashvalue;
} HASHELEMENT;
//哈希表头部结构,非透明类型,用于dynahash.c
typedef struct HASHHDR HASHHDR;
//哈希表控制结构,非透明类型,用于dynahash.c
typedef struct HTAB HTAB;
//hash_create使用的参数数据结构
//根据hash_flags标记设置相应的字段
typedef struct HASHCTL
{
//分区个数(必须是2的幂)
long num_partitions;
//段大小
long ssize;
//初始化目录大小
long dsize;
//dsize上限
long max_dsize;
//填充因子
long ffactor;
//哈希键大小(字节为单位)
Size keysize;
//参见上述数据结构注释
Size entrysize;
//
HashValueFunc hash;
HashCompareFunc match;
HashCopyFunc keycopy;
HashAllocFunc alloc;
MemoryContext hcxt;
//共享内存中的哈希头部结构地址
HASHHDR *hctl;
} HASHCTL;
//哈希桶是HASHELEMENTs链表
typedef HASHELEMENT *HASHBUCKET;
//hash segment是桶数组
typedef HASHBUCKET *HASHSEGMENT;
typedef uint32 (*HashValueFunc) (const void *key, Size keysize);
typedef int (*HashCompareFunc) (const void *key1, const void *key2,
Size keysize);
typedef void *(*HashCopyFunc) (void *dest, const void *src, Size keysize);
typedef void *(*HashAllocFunc) (Size request);
FreeListData
在一个分区哈希表中,每一个空闲链表与特定的hashcodes集合相关,通过下面的FREELIST_IDX()宏进行定义.
nentries跟踪有这些hashcodes的仍存活的hashtable条目个数.
typedef struct
{
//该空闲链表的自旋锁
slock_t mutex;
//相关桶中的条目个数
long nentries;
//空闲元素链
HASHELEMENT *freeList;
} FreeListData;
BufferLookupEnt
//检索hash表的条目
typedef struct
{
//磁盘page的tag
BufferTag key;
//相关联的buffer ID
int id;
} BufferLookupEnt;
二、源码解读
BufTableHashCode
BufTableHashCode函数根据BufferTag计算Hash Code,主要的逻辑在函数hash_any中实现
uint32
BufTableHashCode(BufferTag *tagPtr)
{
return get_hash_value(SharedBufHash, (void *) tagPtr);
}
uint32
get_hash_value(HTAB *hashp, const void *keyPtr)
{
return hashp->hash(keyPtr, hashp->keysize);
}
uint32
tag_hash(const void *key, Size keysize)
{
return DatumGetUInt32(hash_any((const unsigned char *) key,
(int) keysize));
}
#define DatumGetUInt32(X) ((uint32) (X))
hash_any
hash_any函数hash一个可变长键值到一个32位值
Datum
hash_any(register const unsigned char *k, register int keylen)
{
register uint32 a,
b,
c,
len;
//设置内部状态,初始化a/b/c
len = keylen;
a = b = c = 0x9e3779b9 + len + 3923095;
//如果源指针是字对齐的,那么我们使用字宽提取
if (((uintptr_t) k & UINT32_ALIGN_MASK) == 0)
{
//源数据是对齐的
register const uint32 *ka = (const uint32 *) k;
while (len >= 12)
{
a += ka[0];
b += ka[1];
c += ka[2];
mix(a, b, c);
ka += 3;
len -= 12;
}
//处理后面11个字节
k = (const unsigned char *) ka;
#ifdef WORDS_BIGENDIAN//大码端
switch (len)
{
case 11:
c += ((uint32) k[10] << 8);
case 10:
c += ((uint32) k[9] << 16);
case 9:
c += ((uint32) k[8] << 24);
case 8:
b += ka[1];
a += ka[0];
break;
case 7:
b += ((uint32) k[6] << 8);
case 6:
b += ((uint32) k[5] << 16);
case 5:
b += ((uint32) k[4] << 24);
case 4:
a += ka[0];
break;
case 3:
a += ((uint32) k[2] << 8);
case 2:
a += ((uint32) k[1] << 16);
case 1:
a += ((uint32) k[0] << 24);
}
#else
switch (len)
{
case 11:
c += ((uint32) k[10] << 24);
case 10:
c += ((uint32) k[9] << 16);
case 9:
c += ((uint32) k[8] << 8);
case 8:
b += ka[1];
a += ka[0];
break;
case 7:
b += ((uint32) k[6] << 16);
case 6:
b += ((uint32) k[5] << 8);
case 5:
b += k[4];
case 4:
a += ka[0];
break;
case 3:
a += ((uint32) k[2] << 16);
case 2:
a += ((uint32) k[1] << 8);
case 1:
a += k[0];
}
#endif
}
else//---------- 非字对齐
{
while (len >= 12)
{
#ifdef WORDS_BIGENDIAN
a += (k[3] + ((uint32) k[2] << 8) + ((uint32) k[1] << 16) + ((uint32) k[0] << 24));
b += (k[7] + ((uint32) k[6] << 8) + ((uint32) k[5] << 16) + ((uint32) k[4] << 24));
c += (k[11] + ((uint32) k[10] << 8) + ((uint32) k[9] << 16) + ((uint32) k[8] << 24));
#else
a += (k[0] + ((uint32) k[1] << 8) + ((uint32) k[2] << 16) + ((uint32) k[3] << 24));
b += (k[4] + ((uint32) k[5] << 8) + ((uint32) k[6] << 16) + ((uint32) k[7] << 24));
c += (k[8] + ((uint32) k[9] << 8) + ((uint32) k[10] << 16) + ((uint32) k[11] << 24));
#endif
mix(a, b, c);
k += 12;
len -= 12;
}
#ifdef WORDS_BIGENDIAN
switch (len)
{
case 11:
c += ((uint32) k[10] << 8);
case 10:
c += ((uint32) k[9] << 16);
case 9:
c += ((uint32) k[8] << 24);
case 8:
b += k[7];
case 7:
b += ((uint32) k[6] << 8);
case 6:
b += ((uint32) k[5] << 16);
case 5:
b += ((uint32) k[4] << 24);
case 4:
a += k[3];
case 3:
a += ((uint32) k[2] << 8);
case 2:
a += ((uint32) k[1] << 16);
case 1:
a += ((uint32) k[0] << 24);
}
#else
switch (len)
{
case 11:
c += ((uint32) k[10] << 24);
case 10:
c += ((uint32) k[9] << 16);
case 9:
c += ((uint32) k[8] << 8);
case 8:
b += ((uint32) k[7] << 24);
case 7:
b += ((uint32) k[6] << 16);
case 6:
b += ((uint32) k[5] << 8);
case 5:
b += k[4];
case 4:
a += ((uint32) k[3] << 24);
case 3:
a += ((uint32) k[2] << 16);
case 2:
a += ((uint32) k[1] << 8);
case 1:
a += k[0];
}
#endif
}
final(a, b, c);
return UInt32GetDatum(c);
}
#define mix(a,b,c) \
{ \
a -= c; a ^= rot(c, 4); c += b; \
b -= a; b ^= rot(a, 6); a += c; \
c -= b; c ^= rot(b, 8); b += a; \
a -= c; a ^= rot(c,16); c += b; \
b -= a; b ^= rot(a,19); a += c; \
c -= b; c ^= rot(b, 4); b += a; \
}
#define UInt32GetDatum(X) ((Datum) (X))
三、跟踪分析
N/A
四、参考资料
PG Source Code
Buffer Manager
免责声明：
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
软考中级精品资料免费领
历年真题答案解析
备考技巧名师总结
高频考点精准押题
- 资料下载
- 历年真题
193.9 KB下载数265
191.63 KB下载数245
143.91 KB下载数1148
183.71 KB下载数642
644.84 KB下载数2756
相关文章
发现更多好内容猜你喜欢
AI推送时光机 咦！没有更多了？去看看其它编程学习网 内容吧
