ZFS - Space Map以及 Block Allocation - 实现

关于Space Map以及块分配策略的，请参见SpaceMap：http://blog.chinaunix.net/uid-24395800-id-4206221.html

                                                            Block Allocation：http://blog.chinaunix.net/uid-24395800-id-4206309.html

ZFS源码中，metaslab与space map的实现主要包含在以下5个文件中：

• space_map.h
• space_map.c
• metaslab.h
• metaslab_impl.h
• metaslab.c

 

metaslab内存中的表示

按照Space Map的设计原理，每个虚拟设备都被分成几百个metaslab，每个metaslab对应一个Space Map。目前的代码中，每个虚拟设备中metaslab的个数大约是200个，这个在vdev.c的vdev_metaslab_set_size函数中有所体现。

 

metaslab结构体定义如下：

struct metaslab {
    kmutex_t    ms_lock;                           /* metaslab lock */
    space_map_obj_t    ms_smo;                     /* synced space map object */
    space_map_obj_t    ms_smo_syncing;             /* syncing space map object */
    space_map_t *ms_allocmap[TXG_SIZE];         /* allocated this txg */
    space_map_t *ms_freemap[TXG_SIZE];          /* freed this txg */
    space_map_t *ms_defermap[TXG_DEFER_SIZE];   /* deferred frees */
    space_map_t *ms_map;                        /* in-core free space map */
    int64_t        ms_deferspace;                      /* sum of ms_defermap[] space */
    uint64_t    ms_weight;                         /* weight vs. others in group */
    metaslab_group_t *ms_group;                 /* metaslab group */
    avl_node_t    ms_group_node;                   /* node in metaslab group tree */
    txg_node_t    ms_txg_node;                     /* per-txg dirty metaslab links */
};

我们可以看到，metaslab结构体中有4个space_map_t，在初始化过程中，ZFS从磁盘上将space map对象读取出来，首先存放到ms_map中。在使用过程中，如果分配的block，那么就将对应的空间从ms_map中移除，添加到ms_allocmap中，如果有block被释放，则将它移到ms_freemap中，ms_defermap用于延迟释放。

ms_group_node用于将一个磁盘上的metaslab构成一棵AVL树。

 

定义了metaslab之后，ZFS为每个vdev维护一个metaslab_group结构体，详细定义如下：

struct metaslab_group {
    kmutex_t        mg_lock;
    avl_tree_t        mg_metaslab_tree;
    uint64_t        mg_aliquot;
    uint64_t        mg_bonus_area;
    uint64_t        mg_alloc_failures;
    boolean_t        mg_allocatable; /* 是否可以被分配 */
    uint64_t        mg_free_capacity; /* 空闲空间百分比 */
    int64_t            mg_bias;
    int64_t            mg_activation_count;
    metaslab_class_t *mg_class;
    vdev_t *mg_vd;
    metaslab_group_t *mg_prev;
    metaslab_group_t *mg_next;
};

这个结构体可以访问到当前磁盘上的所有metaslab（存储在mg_metaslab_tree中），包括：是否可被分配，使用空间百分比，磁盘选择时的轮转粒子等等。同时与当前pool中的其他磁盘相联系（mg_prev, mg_next）

 

最后，每个ZFS的每个存储池（zpool）都维护了一个metaslab_class（其实有两个，另一个用于ZIL，以后会详细说明）。metaslab_class结构体定义如下：

struct metaslab_class {
    spa_t *mc_spa;
    metaslab_group_t*mc_rotor;
    space_map_ops_t *mc_ops;
    uint64_t    mc_aliquot;
    uint64_t    mc_alloc_groups;/* 可以分配的metaslab_group的数目 */
    uint64_t    mc_alloc; /* 总共分配出去的空间 */
    uint64_t    mc_deferred; /* 总延迟释放的空间 */
    uint64_t    mc_space; /* total space (alloc + free) */
    uint64_t    mc_dspace; /* total deflated space */
};

Space Map内存中的表示

typedef struct space_map {
    avl_tree_t    sm_root; /* offset-ordered segment AVL tree */
    uint64_t    sm_space; /* sum of all segments in the map */
    uint64_t    sm_start; /* start of map */
    uint64_t    sm_size; /* size of map */
    uint8_t        sm_shift; /* unit shift */
    uint8_t        sm_loaded; /* map loaded? */
    uint8_t        sm_loading; /* map loading? */
    uint8_t        sm_condensing; /* map condensing? */
    kcondvar_t    sm_load_cv; /* map load completion */
    space_map_ops_t *sm_ops; /* space map block picker ops vector */
    avl_tree_t *sm_pp_root; /* size-ordered, picker-private tree */
    void *sm_ppd; /* picker-private data */
    kmutex_t *sm_lock; /* pointer to lock that protects map */
} space_map_t;

这里面最重要的就是sm_root，维护了一棵AVL树，里面的节点就是空间段，定义如下：

typedef struct space_seg {
    avl_node_t    ss_node; /* AVL node */
    avl_node_t    ss_pp_node; /* AVL picker-private node */
    uint64_t    ss_start; /* starting offset of this segment */
    uint64_t    ss_end; /* ending offset (non-inclusive) */
} space_seg_t;

space_map_t中有两棵AVL树，他们分别对应space_seg中的ss_node和ss_pp_node。 sm_root是按照offset排序，sm_pp_root是按照块大小排序。一般情况下，space_map_t使用sm_root来进行分配、释放等操作，当metaslab中剩余空间小到一定程度时，ZFS分配空间将会切换分配算法，使用best-fit算法来分配空间，这是就要使用sm_pp_root。

Block Allocation

选择vdev

在分配block，按照分配策略，首先要选择一个虚拟设备（vdev），也就是说要从给定的metaslab_class_t（以下称mc）中选出一个metaslab_group（以下称mg）来。

选择mg的过程中，我们从mc的rotor开始，循环查找所有的mg，直到找到所需的。在这个过程中，不需要锁定mc_rotor或者mc_aliquot，以为就算我们错过一些更新也是没关系的，随着时间的推移，最终会达到平衡状态。

选择磁盘以及分配block的主要流程如以下流程图所示：

说明：流程中有个步骤是设置mg->mg_bias，这里主要用来在分配过程中平衡磁盘的使用率。比如一个设备的空间已经使用了80%，而整个pool才使用20%，那么这个磁盘在分配过程中就要少分配60%，mg_bias = (20-80) * 512K / 100 = -307K，也就是说这次迭代过程中，要少分配307K的空间。（512K是mg->mg_aliquot，即磁盘选择时的轮转因子）

从虚拟设备中分配metaslab

涉及函数为：

static uint64_t metaslab_group_alloc(metaslab_group_t *mg, uint64_t psize, uint64_t asize,

uint64_t txg, uint64_t min_distance, dva_t *dva, int d, int flags)

选择过程其实很简单，在给定的metaslab_group中找出距离给定的所有DVA（最多3个）最近，且权重最高的metaslab，并分配空间（因为离给定的DVA近，需要的寻址时间小，速度就快）。但是如果两者不属于同一个vdev，则不需要考虑距离因素。

选择完成之后，还要进行一系列的判断：

• 被选择的metaslab是否已经达到允许分配失败的最高次数，如果达到了，则需要考虑跳过这个metaslab（当然，还有其他因素需要考虑）。
• 被选择的metaslab权重是否在此过程中被其它线程修改过，如果修改过导致不符合条件，则需要重新选择。
• 如果激活失败，需要重新选择
• 如果选出的metaslab正在被压缩，需要重新选择

检查完毕，都符合条件的情况下，从选择出来的metaslab对应的space_map中分配空间。

 

metaslab权重计算

metaslab权重通过 static uint64_t metaslab_weight(metaslab_t *msp) 函数实现，其实现流程图如下：

块分配策略

First-fit块分配策略

从space map中，使用sm_root（按偏移排序）对应的AVL树，从中选择一个适合大小的块，分配空间。这是ZFS的默认分配策略。

动态分配策略

默认情况下，ZFS是用first-fit分配策略，但是当磁盘空间使用率到达一定程度（空闲空间变小）时，将转换使用Best Fit分配策略。具体转换条件由metaslab_df_alloc_threshold和metaslab_df_free_pct。

本文乃nnusun原创文章，请勿转载。如须转载请详细标明转载出处。