本篇内容介绍了“PostgreSQL中fsm_search函数有什么作用”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！

宏定义
包括FSM页面的叶子节点数/非叶子节点数/FSM树深度等等.

#defineMaxFSMRequestSizeMaxHeapTupleSize#defineMaxHeapTupleSize(BLCKSZ-MAXALIGN(SizeOfPageHeaderData+sizeof(ItemIdData)))#defineFSM_CAT_STEP(BLCKSZ/FSM_CATEGORIES)#defineFSM_CATEGORIES256//块大小为8K则FSM_CAT_STEP=32#defineSlotsPerFSMPageLeafNodesPerPage#defineLeafNodesPerPage(NodesPerPage-NonLeafNodesPerPage)=8156-4095=4061#defineNodesPerPage(BLCKSZ-MAXALIGN(SizeOfPageHeaderData)-\offsetof(FSMPageData,fp_nodes))=8192-32-4=8156#defineNonLeafNodesPerPage(BLCKSZ/2-1)=4095/**Depthoftheon-disktree.Weneedtobeabletoaddress2^32-1blocks,*and1626isthesmallestnumberthatsatisfiesX^3>=2^32-1.Likewise,*216isthesmallestnumberthatsatisfiesX^4>=2^32-1.Inpractice,*thismeansthat4096bytesisthesmallestBLCKSZthatwecangetaway*witha3-leveltree,and512isthesmallestwesupport.*存储在磁盘上的树深度.*我们需要为2^32-1个块定位寻址,1626是可以满足X^3>=2^32-1的最小数字.*另外,216是可以满足X^4>=2^32-1的最小数字.*在实践中,这意味着4096字节是三层数可以支撑的最小BLCKSZ,512是最小可支持的.*/#defineFSM_TREE_DEPTH((SlotsPerFSMPage>=1626)?3:4)

FSMAddress
内部的FSM处理过程以逻辑地址scheme的方式工作,树的每一个层次都可以认为是一个独立的地址文件.

/**TheinternalFSMroutinesworkonalogicaladdressingscheme.Each*levelofthetreecanbethoughtofasaseparatelyaddressablefile.*内部的FSM处理过程工作在一个逻辑地址scheme上.*树的每一个层次都可以认为是一个独立的地址文件.*/typedefstruct{//层次intlevel;/*level*///该层次内的页编号intlogpageno;/*pagenumberwithinthelevel*/}FSMAddress;/*Addressoftherootpage.*///根页地址staticconstFSMAddressFSM_ROOT_ADDRESS={FSM_ROOT_LEVEL,0};

FSMPage
FSM page数据结构.详细可参看src/backend/storage/freespace/README.

/**StructureofaFSMpage.Seesrc/backend/storage/freespace/READMEfor*details.*FSMpage数据结构.详细可参看src/backend/storage/freespace/README.*/typedefstruct{/**fsm_search_avail()triestospreadtheloadofmultiplebackendsby*returningdifferentpagestodifferentbackendsinaround-robin*fashion.fp_next_slotpointstothenextslottobereturned(assuming*there'senoughspaceonitfortherequest).It'sdefinedasanint,*becauseit'supdatedwithoutanexclusivelock.uint16wouldbemore*appropriate,butintismorelikelytobeatomically*fetchable/storable.*fsm_search_avail()函数尝试通过在一轮循环中返回不同的页面到不同的后台进程,*从而分散在后台进程上分散负载.*该字段因为无需独占锁,因此定义为整型.*unit16可能会更合适,但整型看起来更适合于原子提取和存储.*/intfp_next_slot;/**fp_nodescontainsthebinarytree,storedinarray.Thefirst*NonLeafNodesPerPageelementsareuppernodes,andthefollowing*LeafNodesPerPageelementsareleafnodes.Unusednodesarezero.*fp_nodes以数组的形式存储二叉树.*第一个NonLeafNodesPerPage元素是上一层的节点,接下来的LeafNodesPerPage元素是叶子节点.*未使用的节点为0.*/uint8fp_nodes[FLEXIBLE_ARRAY_MEMBER];}FSMPageData;typedefFSMPageData*FSMPage;

FSMLocalMap
对于小表,不需要创建FSM来存储空间信息,使用本地的内存映射信息.

/*Eitheralreadytried,orbeyondtheendoftherelation*///已尝试或者已在表的末尾之后#defineFSM_LOCAL_NOT_AVAIL0x00/*Availabletotry*///可用于尝试#defineFSM_LOCAL_AVAIL0x01/**Forsmallrelations,wedon'tcreateFSMtosavespace,insteadweuse*localin-memorymapofpagestotry.Tolocatefreespace,wesimplytry*pagesdirectlywithoutknowingaheadoftimehowmuchfreespacetheyhave.*对于小表,不需要创建FSM来存储空间信息,使用本地的内存映射信息.*为了定位空闲空间,我们不需要知道他们有多少空闲空间而是直接简单的对page进行尝试.**Notethatthismapisusedtothefindtheblockwithrequiredfreespace*foranygivenrelation.Weclearthismapwhenwehavefoundablockwith*enoughfreespace,whenweextendtherelation,orontransactionabort.*Seesrc/backend/storage/freespace/READMEforfurtherdetails.*注意这个map用于搜索给定表的请求空闲空间.*在找到有足够空闲空间的block/扩展了relation/在事务回滚时,则清除这个map的信息.*详细可查看src/backend/storage/freespace/README.*/typedefstruct{BlockNumbernblocks;//块数uint8map[HEAP_FSM_CREATION_THRESHOLD];//数组}FSMLocalMap;staticFSMLocalMapfsm_local_map={0,{FSM_LOCAL_NOT_AVAIL}};#defineFSM_LOCAL_MAP_EXISTS(fsm_local_map.nblocks>0)

通用例程
包括获取左子节点/右子节点/父节点等

/*Macrostonavigatethetreewithinapage.Roothasindexzero.*///在page中遍历树.Root编号为0#defineleftchild(x)(2*(x)+1)#definerightchild(x)(2*(x)+2)#defineparentof(x)(((x)-1)/2)/**Findrightneighborofx,wrappingaroundwithinthelevel*搜索x右边的邻居,如需要在同一个层次上需回卷*/staticintrightneighbor(intx){/**Moveright.Thismightwraparound,steppingtotheleftmostnodeat*thenextlevel.*移到右边.这可能会引起回卷,调到下一个层次最左边的节点上.*/x++;/**Checkifwesteppedtotheleftmostnodeatnextlevel,andcorrectif*so.Theleftmostnodesateachlevelarenumberedx=2^level-1,so*checkif(x+1)isapoweroftwo,usingastandard*twos-complement-arithmetictrick.*检查是否跳转到下一个层次最左边的节点上,如是则修正x.*每一个层次上最左边的节点编号为x=2^level-1,*因此检查(x+1)是否为2的幂,使用标准的twos-complement-arithmetic技巧即可.*/if(((x+1)&x)==0)//有符号整型,全1为0x=parentof(x);returnx;}/**ReturnsthephysicalblocknumberofaFSMpage*返回FSMpage的物理块号*//*计算公式:Tofindthephysicalblock#correspondingtoleafpagen,weneedtocountthenumberofleafandupper-levelpagesprecedingpagen.Thisturnsouttobey=n+(n/F+1)+(n/F^2+1)+...+1whereFisthefanout.Thefirsttermnisthenumberofprecedingleafpages,thesecondtermisthenumberofpagesatlevel1,andsoforth.*/staticBlockNumberfsm_logical_to_physical(FSMAddressaddr){BlockNumberpages;//块号intleafno;//页号intl;//临时变量/**Calculatethelogicalpagenumberofthefirstleafpagebelowthe*givenpage.*在给定的page下,计算第一个叶子页面的逻辑页号*/leafno=addr.logpageno;for(l=0;l<addr.level;l++)leafno*=SlotsPerFSMPage;/*Countupperlevelnodesrequiredtoaddresstheleafpage*///统计用于定位叶子页面的上层节点数pages=0;for(l=0;l<FSM_TREE_DEPTH;l++){pages+=leafno+1;leafno/=SlotsPerFSMPage;}/**Ifthepagewewereaskedforwasn'tatthebottomlevel,subtractthe*additionallowerlevelpageswecountedabove.*如果请求的页面不在底层,减去上面技术的额外的底层页面数.*/pages-=addr.level;/*Turnthepagecountinto0-basedblocknumber*///计数从0开始(减一)returnpages-1;}/**ReturntheFSMlocationcorrespondingtogivenheapblock.*返回给定堆block的FSM位置.*///addr=fsm_get_location(oldPage,&slot);staticFSMAddressfsm_get_location(BlockNumberheapblk,uint16*slot){FSMAddressaddr;addr.level=FSM_BOTTOM_LEVEL;//#defineSlotsPerFSMPageLeafNodesPerPage//#defineLeafNodesPerPage(NodesPerPage-NonLeafNodesPerPage)=8156-4095=4061//#defineNodesPerPage(BLCKSZ-MAXALIGN(SizeOfPageHeaderData)-\offsetof(FSMPageData,fp_nodes))=8192-32-4=8156//#defineNonLeafNodesPerPage(BLCKSZ/2-1)=4095addr.logpageno=heapblk/SlotsPerFSMPage;*slot=heapblk%SlotsPerFSMPage;returnaddr;}二、源码解读

fsm_search函数搜索FSM,找到有足够空闲空间(min_cat)的堆page.

/**Searchthetreeforaheappagewithatleastmin_catoffreespace*搜索FSM,找到有足够空闲空间(min_cat)的堆page*///returnfsm_search(rel,search_cat);staticBlockNumberfsm_search(Relationrel,uint8min_cat){intrestarts=0;FSMAddressaddr=FSM_ROOT_ADDRESS;for(;;){//---------循环intslot;Bufferbuf;uint8max_avail=0;/*ReadtheFSMpage.*///读取FSMpagebuf=fsm_readbuf(rel,addr,false);/*Searchwithinthepage*///页内搜索if(BufferIsValid(buf)){LockBuffer(buf,BUFFER_LOCK_SHARE);//搜索可用的slotslot=fsm_search_avail(buf,min_cat,(addr.level==FSM_BOTTOM_LEVEL),false);if(slot==-1)//获取最大可用空间max_avail=fsm_get_max_avail(BufferGetPage(buf));UnlockReleaseBuffer(buf);}else//buffer无效,则设置为-1slot=-1;if(slot!=-1){/**Descendthetree,orreturnthefoundblockifwe'reatthe*bottom.*如在树的底部,则返回找到的块.*/if(addr.level==FSM_BOTTOM_LEVEL)returnfsm_get_heap_blk(addr,slot);addr=fsm_get_child(addr,slot);}elseif(addr.level==FSM_ROOT_LEVEL){/**Attheroot,failuremeansthere'snopagewithenoughfree*spaceintheFSM.Giveup.*处于根节点,失败意味着FSM中没有足够空闲空间的页面存在,放弃.*/returnInvalidBlockNumber;}else{uint16parentslot;FSMAddressparent;/**Atlowerlevel,failurecanhappenifthevalueintheupper-*levelnodedidn'treflectthevalueonthelowerpage.Update*theuppernode,toavoidfallingintothesametrapagain,and*startover.*在低层上,如果上层节点没有反映更低层页面的值则会出现失败.*更新高层节点,避免重复掉入同一个陷阱,重新开始.**There'saraceconditionhere,ifanotherbackendupdatesthis*pagerightafterwereleaseit,andgetsthelockontheparent*pagebeforeus.We'llthenupdatetheparentpagewiththenow*staleinformationwehad.It'sOK,becauseitshouldhappen*rarely,andwillbefixedbythenextvacuum.*在我们释放后,另外的后台进程更新这个页面同时在我们之前锁定了父节点的话,会存在条件竞争.*然后我们使用现有已知稳定的信息更新父页面.*如OK,因为这种很少出现,那么会在下一个vacuum中修复此问题.*/parent=fsm_get_parent(addr,&parentslot);fsm_set_and_search(rel,parent,parentslot,max_avail,0);/**Iftheupperpagesarebadlyoutofdate,wemightneedtoloop*quiteafewtimes,updatingthemaswego.Anyinconsistencies*shouldeventuallybecorrectedandtheloopshouldend.Looping*indefinitelyisneverthelessscary,soprovideanemergency*valve.*如果上层页面过旧,可能需要循环很多次,更新上层页面信息.*不一致性会被周期性的纠正,循环会停止.*但无限循环是很可怕的,因此设置阈值,超过此阈值则退出循环.*/if(restarts++>10000)returnInvalidBlockNumber;/*Startsearchalloverfromtheroot*///从root开始搜索addr=FSM_ROOT_ADDRESS;}}}

“PostgreSQL中fsm_search函数有什么作用”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站，小编将为大家输出更多高质量的实用文章！