分布式存储系统的分容灾块数据分布算法

本算法是基于最小费用最大流算法建模，读者需要对最小费用最大流算法有一定的基础，要能理解这个例题 http://www.cppblog.com/y346491470/articles/153091.html?opt=admin

分布式存储系统为了保证高可用性和数据安全，大都会保存多个副本，但是如果不注意数据的分布策略，遇到机架级别的故障就会导致数据不可用，所以将数据的多个副本分配到属于不同容灾块的机器上应该是多副本分布式存储系统的基本需求。

一种最简单的办法，是直接给集群提供多组机器，每组机器保存所有数据的一个副本，各组机器属于不同的容灾块。腾讯的tfs采用的是这种架构，但是这种架构太依赖机房的规划，不是所有企业都能这么玩的。本文就是要给出一个不依赖机房规划的多副本分容灾块分布算法，实现每个容灾块的机器上没有重复的数据。

现在的分布式存储系统一般有两种数据分组方式：
1.以bigtable为代表的，保证了关键字的有序性的按关键字范围动态分组
2.一致性哈希分组

本文的算法主要针对一致性哈希分组方式。对按关键字范围动态分组的方式，作者没有实际运维经验，就不涉及了。

一致性哈希分组对比按关键字范围动态分组，牺牲了关键字有序性，导致数据库难以支持模糊查询等依赖关键字顺序的操作，好处是实现简单、将容量、读、写三个维度的压力统一到了一个维度上，只要桶的分布均匀，这三个维度的压力就都能均匀分布。所以针对一致性哈希的情况，本算法的目标变成了：实现每个容灾块的机器上没有重复的桶，并且每台机器上桶的数量尽量平均。

再来准确描述一下现在的问题：有n个桶，每个桶有m份副本，集群的机器分布在k（k>=m）个容灾块中，第一个容灾块有a1台机器，第二个容灾块有a2台机器......。现在把这n*m个副本分配到这些机器上，要保证每个容灾块内的机器对任意一个桶至多分到一份副本，每个机器上分到的副本数尽量平均。所谓尽量平均，我量化为“每个机器上分到的副本数的平方和最小”。

本文的问题可以如此建模：
有三类点：每个桶一个点，每个容灾块一个点，每台机器一个点，再加上源和汇
源向每个桶连一条边，容量为m，每个桶向每个容灾块连一条边，容量为1，每个容灾块向属于自己的机器连一条边，容量不限，前面这些边费用都为0，最后每台机器向汇连一条容量不限，费用为流量平方的边，如下图：

Paste_Image.png

图中有三个桶b1、b2、b3，6台机器，机器h1属于容灾块d1，机器h2、h3、h4属于容灾块d2，机器h5、h6属于容灾块d3

求出这个图的最小费用最大流，就可以构造出分布方案了。

许多分布式存储系统会从每个桶的副本中选一个作为主副本，所有读操作只能在主副本上进行，这样能够有效提高读缓存的效果。选主副本也会希望尽量平均地分布在每台机器上，可以用类似上面的算法来做。