华为创新杯编程大赛-块分配问题.doc

华为创新杯编程大赛--块分配问题华为公司为客户提供某存储解决方案，该方案中的存储硬件被划分为若干个级别：存储硬件的最大单位是机柜（rack），每个机柜中有机框（chassis）若干（最少1个，最多不超过4个），每个机框中有硬盘（disk）若干（最少1个，最多不超过75个），其物理配置图如下：为方便管理，为每一类物理部件编号，每一类物理部件的id从0开始按自然序递增，并且是连续唯一的，如现有1个机柜，2个机框，每个机框下2个硬盘，则编号为0号机柜，0号机框，1号机框，0、1、2、3号硬盘，若在此基础上增加一个新的硬盘，则该硬盘编号为4设备内的数据以块（chunk）为单位组织和管理，每32个块为一组（块总数总是能被32整除），被称为块组块id从0开始，按自然序递增，如：0~31号块属于组0，32~63号块属于组2，依此类推，所有这些块都被分配到每块硬盘中，如下图所示：对于块分配的要求如下（以下要求考生不需要全部实现，但实现要求的多少及好坏将作为评价标准，分配结果将按照以下要求的顺序逐个评价）：1 块数量块的数量在初始化块时确定，之后数量永远保持不变，块数量的计算方法如下：初始化块时的理论块数量按每个硬盘30个块计算，如果计算出来的块总数不能被32整除，则块组的个数按上述计算出的块总数除以32向上取整计算，即实际的块总数是块组数*32；例如，某设备中有10块硬盘，则初始化块时的理论块数量是10*30=300个，所以块组应该有[30*10/32]+1=10个，最终实际的块数量为320个，所以每块硬盘上的块数量为30个左右而非30个。

2 分配底线块的分配有分配底线，要求在每个块组内，前后相邻的2个块不能在同一个硬盘上（如果块id到达该块组末尾，则相邻块为该组的第一个块，如4号块与2、3、5、6号块不能在同一个硬盘上，31号块与29,30,0,1号块不能在同一块硬盘上），否则视为此次块分配失败如果分配失败，则停止计算，块分配的结果依然为上一次分配成功之后的结果3 块平衡在分配时需要考虑块分配的平衡性，要求在任何情况下每块硬盘的块数量尽量平衡，所有硬盘之间在块数量上的差距尽可能小，块平衡的好坏将作为评分标准4 安全级别在分配底线的基础上，块在硬盘上的分布需要尽可能的安全，如果对于任何一个块组，在某一级别的物理部件（柜、框或者盘）的任何一个设备中都没有超过1个块在该设备中，则称该级别安全以下图为例，假设该图描述了一个单机柜，单机框，4块硬盘的环境，对于块组0中所有的块（0、1、2、3），被合适的分配到了4个盘中，同理，对于任何一个块组中的块，都没有超过1个块被分配到同一块硬盘上，所以该环境被称为是硬盘级别安全的 ，要求块分配后的安全级别尽可能的高，安全级别的高低将作为评分标准5 无效迁移一个块从一块硬盘被分配到另一块硬盘的过程被称为“迁移”，在块分配时，不允许没有发生变化的硬盘之间的块出现迁移（无效迁移）。

例如有3块硬盘，现在0号硬盘故障，要把0号硬盘的块迁移出去，则只允许0号硬盘的块被迁移到1,、2号硬盘，不允许1,、2号硬盘之间的块出现迁移；又比如，现有2块硬盘，新增了1块硬盘，则只允许0、1号硬盘的块被迁移到新增的3号硬盘，不允许0、1号硬盘之间的块出现迁移6 减容对于所有设备组成的集群，集群中的任何一块硬盘在任何时刻都有可能发生故障，如果一个机框内的所有硬盘都故障，该机框即被视为故障，同理，如果一个机柜内的所有机框都故障，则该机柜被视为故障，故障硬盘内的块需要重新迁移到其他正常工作的硬盘上，这种场景被称为“减容”7 扩容在未超过设备的最大容量的前提下，客户在任何时刻都有可能在任一机框内恢复或增加硬盘，或是在任一机柜内恢复/增加机框，或者恢复/增加机柜，新增/恢复的机框或者机柜内必须至少包含一块硬盘，同时也需要从其他硬盘中迁移块到新的或者被恢复的硬盘上，这种场景被称为“扩容”8 安全级别提升（加分项）在集群容量扩大到若干规模后，要求集群的安全级别可以自适应提升，例如集群当前是机框级别安全，在增加若干机框和硬盘后，能达到机柜级别安全在任何场景下，当某一个级别的设备数量达到64时，必须达到该级别安全。

9 整柜/整框故障（加分项）考虑整柜/整框故障的场景10 并发场景（加分项）同一时刻可能有多块硬盘同时故障/恢复/增加，在任一时刻，考虑有硬盘故障/恢复/增加3种情况重叠出现的场景求解：在集群初始化，以及每次减容/扩容之后的块分配情况每次块分配的计算时间将作为评价标准给予适当加分11 附:可用的测试用例用例编号用例描述命令11个机柜、1个机框、每个机框75个硬盘初始化,执行算法Initialize(1, 1, 75);Execute();将编号为0,1的硬盘故障，执行算法remove(2,0);remove(2,1);Execute();将编号为0的硬盘恢复，执行算法recover(2,0);Execute();21个机柜、1个机框、每个机框74个硬盘初始化，执行算法Initialize(1, 1, 74);Execute();在0号机柜，0号机框新增一个硬盘（硬盘编号应该被编为74），执行算法add(0,0,74);Execute();将74号硬盘故障，执行算法remove(2,74);38个机柜、每个机柜内4个机框、每个机框内75个硬盘初始化，执行算法Initialize(1, 4, 75);Execute();。