{"id":523,"date":"2014-04-18T08:55:48","date_gmt":"2014-04-18T08:55:48","guid":{"rendered":"http:\/\/www.selinuxplus.com\/?p=523"},"modified":"2014-04-18T09:02:33","modified_gmt":"2014-04-18T09:02:33","slug":"ceph%e5%ad%a6%e4%b9%a0-9crush%e7%ae%97%e6%b3%955","status":"publish","type":"post","link":"http:\/\/www.selinuxplus.com\/?p=523","title":{"rendered":"[ceph\u5b66\u4e60-9]crush\u7b97\u6cd5(5)"},"content":{"rendered":"

bucket\u7c7b\u578b
\n CRUSH\u7b97\u6cd5\u7684\u8bbe\u8ba1\u662f\u4e3a\u4e86\u6743\u8861\u4e24\u4e2a\u4e92\u65a5\u7684\u76ee\u6807\uff0c\u6620\u5c04\u7b97\u6cd5\u7684\u6548\u7387\u548c\u53ef\u9760\u6027\uff0c\u589e\u5220\u8bbe\u5907\u5bfc\u81f4\u7684\u96c6\u7fa4\u53d8\u66f4\u65f6\u6062\u590d\u5e73\u8861\u7684\u6570\u636e\u8fc1\u79fb\u6210\u672c\u6700\u5c0f\u5316\u3002CRUSH\u5b9a\u4e49\u4e86\u56db\u79cd\u5177\u6709\u4e0d\u540c\u7b97\u6cd5\u7684buckets\u6765diabetes\u96c6\u7fa4\u5c42\u6b21\u7ed3\u6784\u4e2d\u7684\u4e2d\u95f4\u8282\u70b9\uff0c\u800c\u975e\u53f6\u5b50\u8282\u70b9\u3002uniform\u3001List\u3001Tree\u3001Straw\u3002\u6bcf\u79cd\u6876\u90fd\u57fa\u4e8e\u4e00\u79cd\u4e0d\u540c\u7684\u5185\u90e8\u6570\u636e\u7ed3\u6784\uff0c\u5e76\u4e14\u5206\u522b\u4f7f\u7528\u4e86\u4e0d\u540c\u5728\u5b9a\u4f4d\u8fc7\u7a0b\u4e2d\u9009\u62e9\u5d4c\u5957item\u7684\u4f2a\u968f\u673a\u51fd\u6570c(r,x).\u4f53\u73b0\u4e86\u6548\u7387\u548c\u6570\u636e\u91cd\u7ec4\u6548\u7387\u4e4b\u95f4\u7684\u4e0d\u540c\u6743\u8861\u65b9\u6cd5\u3002
\n uniform buckets\u3002\u8981\u6c42\u6240\u6709\u6876\u5185\u7684item\u6743\u503c\u76f8\u7b49\uff0c\u800c\u4e14bucket\u5f88\u5c11\u6dfb\u52a0\u5220\u9664item\u3002\u5b83\u7684\u67e5\u627e\u901f\u5ea6\u6700\u5feb\u3002\u5927\u5c0f\u5982\u679c\u6539\u53d8\uff0c\u8bbe\u5907\u4e2d\u7684\u6570\u636e\u4f1a\u88ab\u5b8c\u5168\u91cd\u7ec4\u3002
\n List buckets\uff1a\u4ed6\u7684\u7ed3\u6784\u662f\u94fe\u8868\u7ed3\u6784\uff0c\u6240\u5305\u542b\u7684item\u53ef\u4ee5\u5177\u6709\u4efb\u610f\u6743\u503c\u3002CRUSH\u4ece\u8868\u5934\u5f00\u59cb\u67e5\u627e\u526f\u672c\u7684\u4f4d\u7f6e\uff0c\u5b83\u5148\u5f97\u5230\u8868\u5934\u7684Item\u7684\u6743\u91cdWh\uff0c\u5269\u4f59\u94fe\u8868\u4e2d\u6240\u6709\u7684item\u7684\u6743\u91cd\u4e4b\u548cWs\uff0c\u7136\u540e\u6839\u636ehash(x,r,item)\u5f97\u5230\u4e00\u4e2a[0-1]\u7684\u503cv\uff0c\u5047\u5982\u8fd9\u4e2av\u5728[0~Wh\/Ws)\u4e4b\u4e2d\uff0c\u5219\u526f\u672c\u5728\u8868\u5934item\u4e2d\uff0c\u5e76\u53d1\u6325\u8868\u5934item\u7684\u6807\u8bc6\u7b26(id).\u5426\u5219\u673a\u9009\u904d\u5386\u5269\u4f59\u7684\u94fe\u8868\u3002\u8fd9\u79cd\u65b9\u5f0f\u6765\u6e90\u4e8eRUSHp
\n Tree buckets:\u94fe\u8868\u67e5\u627e\u7684\u590d\u6742\u5ea6O(n)\uff0c\u51b3\u7b56\u6811\u7684\u67e5\u627e\u590d\u6742\u5ea6\u4e3aO(logn).item\u662f\u51b3\u7b56\u6811\u7684\u53f6\u5b50\u8282\u70b9\uff0c\u51b3\u7b56\u6811\u4e2d\u7684\u5176\u4ed6\u8282\u70b9\u77e5\u9053\u5b83\u5de6\u53f3\u5b50\u6811\u7684\u6743\u91cd\uff0c\u8282\u70b9\u7684\u6743\u91cd\u7b49\u4e8e\u5de6\u53f3\u5b50\u6811\u7684\u6743\u91cd\u4e4b\u548c\u3002CRUSH\u4eceroot\u8282\u70b9\u5f00\u59cb\u67e5\u627e\u526f\u672c\u7684\u4f4d\u7f6e\uff0c\u5b83\u5148\u5f97\u5230\u8282\u70b9\u7684\u5de6\u5b50\u6811\u7684\u6743\u91cdWl\uff0c\u5f97\u5230\u8282\u70b9\u7684\u6743\u91cdWn\uff0c\u7136\u540e\u6839\u636ehash\uff08x\uff0cr,node_id)\u5f97\u5230\u4e00\u4e2a[0-1]\u7684\u503cy\uff0c\u5047\u5982\u8fd9\u4e2a\u503cv\u5728[0~Wl\/Wn)\u4e2d\uff0c\u5219\u526f\u672c\u5728\u5de6\u5b50\u6811\uff0c\u6216\u8005\u5728\u53f3\u5b50\u6811\u4e2d\u3002\u7ee7\u7eed\u904d\u5386\u8282\u70b9\uff0c\u76f4\u5230\u5230\u8fbe\u53f6\u5b50\u8282\u70b9\u3002treebucket\u7684\u5173\u952e\u662f\u5f53\u6dfb\u52a0\u5220\u9664\u53f6\u5b50\u8282\u70b9\u65f6\uff0c\u51b3\u7b56\u6811\u4e2d\u7684\u5176\u4ed6\u8282\u70b9\u7684node_id\u4e0d\u53d8\u3002\u51b3\u7b56\u6811\u4e2d\u8282\u70b9\u7684node_id\u7684\u6807\u8bc6\u662f\u6839\u636e\u5bf9\u4e8c\u53c9\u6811\u7684\u4e2d\u5e8f\u904d\u5386\u6765\u89c9\u51b3\u5b9a\u7684(node_id\u4e0d\u7b49\u4e8eitem\u7684id\uff0c\u4e5f\u4e0d\u7b49\u4e8e\u6743\u91cd)
\n straw buckets\uff1a\u8fd9\u79cd\u7c7b\u578b\u7684bucket\u6240\u5305\u542b\u7684\u6240\u6709item\u516c\u5e73\u7ade\u4e89\uff0c\uff08\u4e0d\u50cflist\u548ctree\u4e00\u6837\u9700\u8981\u904d\u5386\uff09\u3002\u8fd9\u79cd\u7b97\u6cd5\u5c31\u50cf\u62bd\u7b7e\u4e00\u6837\uff0c\u6240\u6709\u7684item\u90fd\u6709\u673a\u4f1a\u88ab\u62bd\u4e2d\uff08\u53ea\u6709\u6700\u957f\u7684\u7b7e\u624d\u80fd\u88ab\u62bd\u4e2d\uff09\u3002\u6bcf\u4e2a\u7b7e\u7684\u957f\u5ea6\u662f\u6709length= f(Wi)*hash(x,r,i\uff09\u6765\u51b3\u5b9a\u7684\u3002f(Wi)\u548citem\u7684\u6743\u91cd\u6709\u5173\uff0ci\u662fitem\u7684id\u53f7\u3002 <\/p>\n

c(r,x)= max<i>(f(W<i>)hash(x,r,i))\u3002<\/pre>\n
struct crush_bucket {\r\n\t__s32 id;        \/\/ this'll be negative \r\n\t__u16 type;      \/\/non-zero; type=0 is reserved for devices \r\n\t__u8 alg;        \/\/ one of CRUSH_BUCKET_* \r\n\t__u8 hash;       \/\/ which hash function to use, CRUSH_HASH_* \r\n\t__u32 weight;    \/\/ 16-bit fixed point \r\n\t__u32 size;      \/\/ num items \u5047\u5982size\u4e3a0\uff0c\u4e0d\u5305\u542bitem\r\n\t__s32 *items;\t\/\/ \u6570\u7ec4\uff0c\u5b83\u5305\u542bitem\u7684id\u3002\u8fd9\u4e9bid\u53ef\u80fd\u662f\u8d1f\u6570\uff0c\u4e5f\u53ef\u80fd\u90fd\u662f\u81ea\u7136\u6570\u3002\u5982\u679c\u662f\u8d1f\u6570\uff0c\u8868\u793a\u5b83\u5305\u542b\u7684\u90fd\u662fbucket\uff0c\u5982\u679c\u662f\u81ea\u7136\u6570\uff0c\u8868\u793aitem\u90fd\u662fdevice\uff08\u53f6\u8282\u70b9\uff09\r\n\r\n\t\/\/\r\n\t \/\/ cached random permutation: used for uniform bucket and for\r\n\t \/\/ the linear search fallback for the other bucket types.\r\n\t \/\/\r\n\t__u32 perm_x;  \/*  @x for which *perm is defined \/\/\r\n\t__u32 perm_n;  \/*  num elements of *perm that are permuted\/defined \/\/\r\n\t__u32 *perm;\r\n};\r\n<\/pre>\n
crush.c\u6587\u4ef6\u4e2d
\n\/*\u7528\u4e8e\u83b7\u53d6\u6307\u5b9a\u7684bucket\u4e2d\u7684item\u7684weight*\/<\/p>\n
int crush_get_bucket_item_weight(const struct crush_bucket *b, int p) <\/pre>\n
\/*\u7528\u4e8e\u9500\u6bc1bucket\u6570\u636e\u7ed3\u6784*\/<\/p>\n
void crush_destroy_bucket(struct crush_bucket *b)<\/pre>\n
\/**\/\u7528\u4e8e\u9500\u6bc1cursh_map<\/p>\n
void crush_destroy(struct crush_map *map)\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
bucket\u7c7b\u578b CRUSH\u7b97\u6cd5\u7684\u8bbe\u8ba1\u662f\u4e3a\u4e86\u6743\u8861\u4e24…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[84],"tags":[180,97,90],"_links":{"self":[{"href":"http:\/\/www.selinuxplus.com\/index.php?rest_route=\/wp\/v2\/posts\/523"}],"collection":[{"href":"http:\/\/www.selinuxplus.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.selinuxplus.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.selinuxplus.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.selinuxplus.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=523"}],"version-history":[{"count":8,"href":"http:\/\/www.selinuxplus.com\/index.php?rest_route=\/wp\/v2\/posts\/523\/revisions"}],"predecessor-version":[{"id":531,"href":"http:\/\/www.selinuxplus.com\/index.php?rest_route=\/wp\/v2\/posts\/523\/revisions\/531"}],"wp:attachment":[{"href":"http:\/\/www.selinuxplus.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=523"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.selinuxplus.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=523"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.selinuxplus.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=523"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}