PostgreSQL 源码解读（143）- Buffer Manager#8（BufTableHashCode函数）

2024-04-02 19:04:59 134人浏览安东尼

摘要

本节简单介绍了postgresq

本节简单介绍了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))