Postgresql源码（45）SysCache内存结构与搜索流程分析
1 内存结构和查询步骤
查询步骤概要
- 使用SysCacheIdentifier在CatCache数组中找到对应的CatCache
- 计算hash，按数组index找到bucket
- 找到bucket后，在bucket双向链表中遍历找到CatCTup，元组记录在其中；找到后调整到双向链表头（LRU）
多条查询步骤概要
- cc_lists用与多条数据查询
- 计算hash，按顺序匹配每个catclist，找到catclist
- 如果List可用直接返回。注意catclist中再结构体后面记录了该List指向的所有CatCTup的指针，catclist并不维护tuple内存信息，只是指向CatCTup结构，具体的元组信息（封装在CatCTup中）还是放在bucket中维护。
内存结构见下图：
2 单条查询步骤
提供了四个入口函数，用于不同查询条件个数的场景
extern HeapTuple SearchSysCache1(int cacheId,Datum key1);
extern HeapTuple SearchSysCache2(int cacheId,Datum key1, Datum key2);
extern HeapTuple SearchSysCache3(int cacheId,Datum key1, Datum key2, Datum key3);
extern HeapTuple SearchSysCache4(int cacheId,Datum key1, Datum key2, Datum key3, Datum key4);
最后全部调入
static inline HeapTuple
SearchCatCacheInternal(CatCache *cache,int nkeys,Datum v1,Datum v2,Datum v3,Datum v4)
{Datum arguments[CATCACHE_MAXKEYS];uint32 hashValue;Index hashIndex;dlist_iter iter;dlist_head *bucket;CatCTup *ct;/** one-time startup overhead for each cache*/if (unlikely(cache->cc_tupdesc == NULL))CatalogCacheInitializeCache(cache);/* Initialize local parameter array */arguments[0] = v1;arguments[1] = v2;arguments[2] = v3;arguments[3] = v4;【第一步】算hash找桶
hashValue = CatalogCacheComputeHashValue(cache, nkeys, v1, v2, v3, v4);hashIndex = HASH_INDEX(hashValue, cache->cc_nbuckets);
【第二步】遍历桶的dlist，找到和nkeys都匹配的tuple
bucket = &cache->cc_bucket[hashIndex];dlist_foreach(iter, bucket){ct = dlist_container(CatCTup, cache_elem, iter.cur);if (ct->dead)continue; /* ignore dead entries */if (ct->hash_value != hashValue)continue; /* quickly skip entry if wrong hash val */if (!CatalogCacheCompareTuple(cache, nkeys, ct->keys, arguments))continue;【第二步】找到了！放到dlist头部（LRU）
dlist_move_head(bucket, &ct->cache_elem);【第二步】找到的tuple是否有neg标记
- 找到了没有negative标记的，把REF++，返回TUPLE。
- 找到了有negative标记的，这种tuple是SearchCatCacheMiss函数查完系统表后，没有匹配的元组，就会在cache中增加一个negative的tuple，表示系统表中没有，省去了下次还要搜索系统表的操作。
/** If it's a positive entry, bump its refcount and return it. If it's* negative, we can report failure to the caller.*/if (!ct->negative){ResourceOwnerEnlargeCatCacheRefs(CurrentResourceOwner);ct->refcount++;ResourceOwnerRememberCatCacheRef(CurrentResourceOwner, &ct->tuple);return &ct->tuple;}else{return NULL;}}【第三步】没找到，去IO对应的系统表
- 如果去系统表中找到了，构造一个tuple放入bucket的dlist中。
- 如果去系统表中没找到，构造一个neg tuple放入bucket的dlist中，表示这条没有，下次直接返回不必查询系统表。
return SearchCatCacheMiss(cache, nkeys, hashValue, hashIndex, v1, v2, v3, v4);
}
3 多条查询步骤SearchCatCacheList
与#2类似：
CatCList *
SearchCatCacheList(CatCache *cache,int nkeys,Datum v1,Datum v2,Datum v3)
{...lHashValue = CatalogCacheComputeHashValue(cache, nkeys, v1, v2, v3, v4);dlist_foreach(iter, &cache->cc_lists){cl = dlist_container(CatCList, cache_elem, iter.cur);if (cl->dead)continue; /* ignore dead entries */if (cl->hash_value != lHashValue)continue; /* quickly skip entry if wrong hash val *//** see if the cached list matches our key.*/if (cl->nkeys != nkeys)continue;if (!CatalogCacheCompareTuple(cache, nkeys, cl->keys, arguments))continue;-
与上面单条查询不同的是，这里没有bucket，需要按顺序遍历链表，找到hash匹配的。
-
找到后也是LRU到最前，然后返回即可。
dlist_move_head(&cache->cc_lists, &cl->cache_elem);/* Bump the list's refcount and return it */ResourceOwnerEnlargeCatCacheListRefs(CurrentResourceOwner);cl->refcount++;ResourceOwnerRememberCatCacheListRef(CurrentResourceOwner, cl);return cl;}ctlist = NIL;PG_TRY();{ScanKeyData cur_skey[CATCACHE_MAXKEYS];Relation relation;SysScanDesc scandesc;/** Ok, need to make a lookup in the relation, copy the scankey and* fill out any per-call fields.*/memcpy(cur_skey, cache->cc_skey, sizeof(ScanKeyData) * cache->cc_nkeys);cur_skey[0].sk_argument = v1;cur_skey[1].sk_argument = v2;cur_skey[2].sk_argument = v3;cur_skey[3].sk_argument = v4;relation = table_open(cache->cc_reloid, AccessShareLock);scandesc = systable_beginscan(relation,cache->cc_indexoid,IndexScanOK(cache, cur_skey),NULL,nkeys,cur_skey);-
没找到，去系统表里面搜索。
-
注意搜完了都是添加到bucket中的，list需要的只是把指针记录下来。
ordered = (scandesc->irel != NULL);while (HeapTupleIsValid(ntp = systable_getnext(scandesc))){uint32 hashValue;Index hashIndex;bool found = false;dlist_head *bucket;/** See if there's an entry for this tuple already.*/ct = NULL;hashValue = CatalogCacheComputeTupleHashValue(cache, cache->cc_nkeys, ntp);hashIndex = HASH_INDEX(hashValue, cache->cc_nbuckets);bucket = &cache->cc_bucket[hashIndex];dlist_foreach(iter, bucket){ct = dlist_container(CatCTup, cache_elem, iter.cur);if (ct->dead || ct->negative)continue; /* ignore dead and negative entries */if (ct->hash_value != hashValue)continue; /* quickly skip entry if wrong hash val */if (!ItemPointerEquals(&(ct->tuple.t_self), &(ntp->t_self)))continue; /* not same tuple *//** Found a match, but can't use it if it belongs to another* list already*/if (ct->c_list)continue;found = true;break; /* A-OK */}if (!found){ct = CatalogCacheCreateEntry(cache, ntp, arguments,hashValue, hashIndex,false);}ctlist = lappend(ctlist, ct);ct->refcount++;}systable_endscan(scandesc);table_close(relation, AccessShareLock);/* Now we can build the CatCList entry. */oldcxt = MemoryContextSwitchTo(CacheMemoryContext);nmembers = list_length(ctlist);cl = (CatCList *)palloc(offsetof(CatCList, members) + nmembers * sizeof(CatCTup *));/* Extract key values */CatCacheCopyKeys(cache->cc_tupdesc, nkeys, cache->cc_keyno,arguments, cl->keys);MemoryContextSwitchTo(oldcxt);}...cl->cl_magic = CL_MAGIC;cl->my_cache = cache;cl->refcount = 0; /* for the moment */cl->dead = false;cl->ordered = ordered;cl->nkeys = nkeys;cl->hash_value = lHashValue;cl->n_members = nmembers;i = 0;foreach(ctlist_item, ctlist){cl->members[i++] = ct = (CatCTup *) lfirst(ctlist_item);Assert(ct->c_list == NULL);ct->c_list = cl;/* release the temporary refcount on the member */Assert(ct->refcount > 0);ct->refcount--;/* mark list dead if any members already dead */if (ct->dead)cl->dead = true;}Assert(i == nmembers);- 构造完成，挂到cc_lists前面，完成搜索。cl->refcount++
dlist_push_head(&cache->cc_lists, &cl->cache_elem);/* Finally, bump the list's refcount and return it */cl->refcount++;ResourceOwnerRememberCatCacheListRef(CurrentResourceOwner, cl);...return cl;
}
ps. 补充
PG的双向链表的几个宏实现很漂亮，有兴趣可以研究下。
ilist.h
https://github.com/postgres/postgres/blob/master/src/include/lib/ilist.h
使用时只需要将dlist_node放入struct的任意位置即可，该struct就具有了dlist的所有功能。
struct dlist_node
{dlist_node *prev;dlist_node *next;
};typedef struct dlist_head
{dlist_node head;
} dlist_head;// 遍历
dlist_foreach(iter, bucket){ct = dlist_container(CatCTup, cache_elem, iter.cur);
...
...
我的博客即将同步至腾讯云+社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=1tkegkxy1j6as
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！