華為創(chuàng)新杯編程大賽--塊分配問題

1、華為創(chuàng)新杯編程大賽-塊分配問題華為公司為客戶提供某存儲解決方案，該方案中的存儲硬件被劃分為若干個級別：存儲硬件 的最大單位是 機柜（rack），每個機柜中有 機框（chassis若干（最少1個，最多不超過42019-4-26華為保密信息，未經(jīng)授權(quán)禁止擴散第12頁，共6頁個），每個機框中有 硬盤（disk）若干（最少1個，最多不超過75個），其物理配置圖如下:1II11IIII X 11IIIIIIII111 11 r1 11 11* h*h*# h#h#1111 r1r111111111 (11_11111 1111 X 11111 f1r111i:i:I1 1 1 1 111 111 11

2、L1 11 111D 1 1 r1 1111 11 11 r1 11NN*h*111 11 ( 111 11 11 11 r1 1 1 1 1 11 1 111 11 1IIItFF11111111 1Rack：包舍4個ch亦希Clias$is：包含75平di或Disk為方便管理，為每一類物理部件編號，每一類物理部件的id從0開始按自然序遞增,并且是連續(xù)唯一的，如現(xiàn)有1個機柜，2個機框，每個機框下2個硬盤，則編號為0號機柜,0號機框，1號機框，0、1、2、3號硬盤，若在此基礎(chǔ)上增加一個新的硬盤，則該硬盤編號為設(shè)備內(nèi)的數(shù)據(jù)以塊（chunk）為單位組織和管理，每32個塊為一組（塊總數(shù)總是能被32整

3、除），被稱為塊組。塊id從0開始，按自然序遞增，如：031號塊屬于組0, 3263號塊屬于組2,依此類推，所有這些塊都被分配到每塊硬盤中，如下圖所示:Group 0Group 】Group 2ctiLinkOchunks2chunk Ich 111山3mchunk?cliLifik*?(ahnAiM 0(dwg 0(ehpi 耐 Q(clniiifc67 0f Disk 2o對于塊分配的要求如下（以下要求考生不需要全部實現(xiàn)，但實現(xiàn)要求的多少及好壞將作為評 價標準，分配結(jié)果將按照以下要求的順序逐個評價）：1塊數(shù)量塊的數(shù)量在初始化塊時確定，之后數(shù)量永遠保持不變，塊數(shù)量的計算方法如下:初始化塊時的理

4、論塊數(shù)量按每個硬盤30個塊計算，如果計算出來的塊總數(shù)不能被 32整除，則塊組的個數(shù)按上述計算出的塊總數(shù)除以32向上取整計算，即實際的塊總數(shù)是塊組數(shù)*32 ;例如，某設(shè)備中有10塊硬盤，則初始化塊時的理論塊數(shù)量是10*30=300個，所以塊組應(yīng)該有30*10/32+1=10個，最終實際的塊數(shù)量為 320個，所以每塊硬盤上的塊數(shù)量為30個左右而非30個。2分配底線塊的分配有分配底線，要求在每個塊組內(nèi)，前后相鄰的 2個塊不能在同一個硬盤上（如果塊id到達該塊組末尾，則相鄰塊為該組的第一個塊，女04號塊與2、3、5、6號塊不能在同一個硬盤上，31號塊與29,30,0,1號塊不能在同一塊硬盤上），否則視

5、為此次塊分配失敗。如果分配失敗，則停止計算,塊分配的結(jié)果依然為上一次分配成功之后的結(jié)果。0( Disk 11( Disk 2) I Disk 3vZz vZ2 vZz3塊平衡在分配時需要考慮塊分配的平衡性，要求在任何情況下每塊硬盤的塊數(shù)量盡量平衡,有硬盤之間在塊數(shù)量上的差距盡可能小，塊平衡的好壞將作為評分標準4安全級別在分配底線的基礎(chǔ)上，塊在硬盤上的分布需要盡可能的安全，如果對于任何一個塊組,在某一級別的物理部件（柜、框或者盤）的任何一個設(shè)備中都沒有超過1個塊在該設(shè)備中,則稱該級別安全。以下圖為例，假設(shè)該圖描述了一個單機柜，單機框,4塊硬盤的環(huán)境，對于塊組0中所有的塊（0、1、2、3）,被合適

6、的分配到了 4個盤中，同理，對于任何一個塊組中的塊，都沒有超過1個塊被分配到同一塊硬盤上，所以該環(huán)境被稱為是硬盤級別安全的要求塊分配后的安全級別盡可能的高，安全級別的高低將作為評分標準 。Group 0Group JGi oup 2chunktgliunkJJthunks0Disk 3V25無效遷移一個塊從一塊硬盤被分配到另一塊硬盤的過程被稱為a遷移”，在塊分配時，不允許沒有發(fā)生變化的硬盤之間的塊出現(xiàn)遷移（無效遷移）。例如有3塊硬盤，現(xiàn)在0號硬盤故障，要把0號硬盤的塊遷移出去，則只允許 0號硬盤的塊被遷移到1,、2號硬盤，不允許1,、2號硬盤之間 的塊出現(xiàn)遷移；又比如，現(xiàn)有 2塊硬盤，新增了

7、1塊硬盤，則只允許0、1號硬盤的塊被遷移到 新增的3號硬盤，不允許0、1號硬盤之間的塊出現(xiàn)遷移。eriunkjjchurarabchunks6減容對于所有設(shè)備組成的集群,集群中的任何一塊硬盤在任何時刻都有可能發(fā)生故障,如果一個機框內(nèi)的所有硬盤都故障,該機框即被視為故障，同理，如果一個機柜內(nèi)的所有機框都故障,則該機柜被視為故障，故障硬盤內(nèi)的塊需要重新遷移到其他正常工作的硬盤上,這種場景被稱為“減容”。7擴容在未超過設(shè)備的最大容量的前提下，客戶在任何時刻都有可能在任一機框內(nèi)恢復(fù)或增加硬盤，或是在任一機柜內(nèi)恢復(fù)/增加機框，或者恢復(fù)/增加機柜，新增/恢復(fù)的機框或者機柜內(nèi)必須至少包含一塊硬盤，同時也需要

8、從其他硬盤中遷移塊到新的或者被恢復(fù)的硬盤上,這種場景被稱為“擴容”。8安全級別提升（加分項）在集群容量擴大到若干規(guī)模后，要求集群的安全級別可以自適應(yīng)提升，例如集群當(dāng)前是機框級別安全，在增加若干機框和硬盤后，能達到機柜級別安全。 在任何場景下，當(dāng)某一個級別的設(shè)備數(shù)量達到64時，必須達到該級別安全 。9整柜/整框故障（加分項）考慮整柜/整框故障的場景。10并發(fā)場景（加分項）同一時刻可能有多塊硬盤同時故障/恢復(fù)/增加，在任一時刻，考慮有硬盤故障/恢復(fù)/增加3種 情況重疊出現(xiàn)的場景。求解：在集群初始化，以及每次減容 /擴容之后的塊分配情況。每次塊分配的計算時間將作 為評價標準給予適當(dāng)加分。11附:可用的測試用例1個機柜、1個機框、每個機框75個硬盤初始Ini tialize(1, 1,75);化，執(zhí)行算法Execute。;將編號為0,1的硬盤故障，執(zhí)行算法remove(2,0);remove(2,1);Execute();將編號為0的硬盤恢復(fù)，執(zhí)行算法recover(2,0);Execute();1個機柜、1個機框、每個機框74個硬盤初始Ini tialize(1, 1,74);Execute();化，執(zhí)行算法在0號機柜，0號機