块存储 资源管理
由IO路径看资源布局。
IO start
Volume层
Pool层
Thin LUN
Meta Volume
-
Root Extent
- Alloc Queue
- Free Queue
- Map Tree Root
- Free Tree Root
Data Volume
Alloc Queue
grain分配队列
使用场景：
写thin lun，在查询map tree对应grain未分配时触发空间分配；
step1：空间以顺序分配的方式进行，分配时，增加offset偏移并可能改变队首（对首Item全部分配完时），并生成grain info返回。
step2：在map tree中插入新的映射项（grain id -> Extent ID + offset）,如果和前一个node满足合并条件则合并。
step3：如果alloc queue中可分配的grain低于阈值，则触发后台空间分配，首先从SPA中获取Extent并生成Item插入alloc queue队尾，如果SPA空间不足，不能分配Extent，则从free tree中取出Item，直接插入到alloc queue。
Item Head
Tier:0，1，2（为0时，一个bit表示一个grain，每升1，乘以64）
Offset:记录Extent已经分配grain的偏移。
Bitmap:0xFFFFFFFFFFFFFFFF(64字节)
Item
Item
...
Item Tail
Item
结构
-
Extent ID
表示归属的Extent ID
-
Tier
多级位图结构
0：bitmap一个bit表示一个grain的分配情况；
1：bitmap一个bit表示64个grain的分配情况；
2：bitmap一个bit表示64*64个grain的分配情况；
以此类推；
-
Offset
grain的分配采用顺序分配的方式
Tier为0时，bitmap的置位便可表示每个grain的分配情况；
Tier为1时，bitmap中为置为1的bit表示相应64个grain均已分配。不存在64个grain部分分配，tier却为1的情况，未集满时tier不会提升。此时bitmap的置位不能表示每个grain的分配情况，需要offset配合，每次分配一个grain，offset++，遇到已经置位的bit，还需++64；
Tier为2时，同上；
-
Bitmap
0xffffffffffffffff(8字节)
对应不同的tier，每个bit置位表示不同数量的grain分配情况，1、64、64*64...
合并
归属于相同的Extent，且表示的grain范围相同的Item可以合并。
tier为0的item，集满64个bit后，tier提升为1，并根据offset将新的item对应位置的1个bit置位；
tier为1的item，集满64*64个bit后，tier提升为2，并根据offset将新的item对应位置的1个bit置位；
以此类推；
分配
Grain Free Tree
资源释放树
使用场景：
删除thin lun，去激活快照等操作，需要释放响应的grain空间，本树中记录了已经释放的grain，释放的grain从map tree摘下放到free queue，free queue将队列中同一个extent的grain合并到一个item，最终和free tree的item合并，当item集满整个Extent时，将Extent释放给SPA。
node
-
leaf node
- key:extent id
- value:item
leaf node
leaf node...
node
node...
Grain Map Tree
thin lun的空间分配树。
使用场景：
1.写thin lun时，查询本树相应grain是否分配，未分配时从alloc queue分配grain并在本树插入相应node。
2.删lun、去激活快照等，需要回收空间，需要查询并删除本树的节点，同时查询free t，如果free queue已经存在 相同的Extent的Item，将相应grain的offset bit置位，否则生成新的Item插入free queue的队尾。
node
-
leaf node
相邻的node，如果属于同一个Extent，且Grain ID也相邻，则合并为一个leaf node以节省空间。
在对Thin LUN做连续写时，从分配队列分配的grain很可能满足合并条件（在资源充足，从SPA分配到整个Extent时，连续写分配的Grain必然可以合并；未从SPA分配到Extent时，去Free Tree取出Item分配，这里由于释放grain时的随机性，能合并的可能较小）。
由于存在合并的情况，使用grain id来map tree查询时，可能响应的grain已经和前面的node合并，所以查询策略略有不同，未查询到时，还需要查询前面的node中value的范围是否包含了查询的grain。
- key:LBA/grain size
- value:Extent Id + offset
- leaf node
- leaf node...
node
node...
Ckg Map Tree
POOL的CKG映射树（ckg id -> disk + lba）
负责ckg id到盘的路由
node
-
leaf node
- key:ckg id
- value:chunks{(diskid,LBA),...}
leaf node...
node
node...
Extent Map Tree
LUN的空间映射树（extent id -> ckg id）
该树负责extent到ckg的路由，由pool管理，物理分布在root extent中，节点有nodeMgr分配在非预留的extent node上。
读写：通过extent id进行索引，查到树上存在对应的节点，获取ckg id和offset，到pool的ckg map tree上进一步查询；
node
-
leaf node
- key:extent id
- value:ckg id + offset
leaf node
leaf node...
node
...
node
Free Queue
grain空间释放队列
使用场景：
删lun或去激活快照时，触发空间释放；
step1:将grain id的映射信息从map tree中摘下，并可能导致map tree node分裂（之前相邻的node满足属于同一个Extent且grain id连续）。
step2:以释放的grain的Extent id + offset去free queue查找，若找到，将相应bit置位，否则，生成新的Item插入队尾。
step3：后台释放：遍历free queue，将同一个extent的Item合并。
step4：将合并的Item去free tree查找，找到对应项则合并，否则新插入Item，若合并后Item集满整个Extent，将Extent释放给SPA。
Question：step2先查询，有相同Extent的Item置位对应bit，为什么step3还可能合并同一Extent的Item？存在同一个Extent的Item不能合并的情况？可能跟Item结构有关。。
Item Tail
Item
Item
...
Item Head
Disks
CowTree(Snapshot)
node
-
leaf node
相邻的node，如果属于同一个Extent，且Grain ID也相邻，则合并为一个leaf node以节省空间。
在对Thin LUN做连续写时，从分配队列分配的grain很可能满足合并条件（在资源充足，从SPA分配到整个Extent时，连续写分配的Grain必然可以合并；未从SPA分配到Extent时，去Free Tree取出Item分配，这里由于释放grain时的随机性，能合并的可能较小）。
由于存在合并的情况，使用grain id来map tree查询时，可能响应的grain已经和前面的node合并，所以查询策略略有不同，未查询到时，还需要查询前面的node中value的范围是否包含了查询的grain。
- key:LBA/grain size
- value:Extent Id + offset
- leaf node
- leaf node...
