I have a bunch of databases, each having different access patterns, such that each puts a different amount of load on its database cluster. I would like to distribute them around my set of database clusters such that the workload for the clusters is evenly distributed.

I looked at the k-partition problem, which sounds close to what I want, except each of my database clusters has a different load capacity. That means I need an algorithm that minimizes what percent of load capacity is used on all clusters, whereas the k-partition problem minimizes the integer load on each cluster.

Does such an algorithm exist? And can anyone point me to a sample implementation of it?

  • 2
    $\begingroup$ In the special case that all center capacities are the same your problem is equivalent to k-partition, which is NP-hard (even when weights are polynomially bounded integers). In practice, you might solve the natural LP relaxation, then randomly round the solution. (E.g., Let variable $X_{ij}$ represent the fraction of database $i$ that the LP solution maps to cluster $j$. Choose a single random cluster $\hat j(i)$ to actually use for $i$ by drawing randomly from the distribution $p$ defined by $p_i = X_{ij}$. Maybe polish this solution with some local improvement. $\endgroup$ – Neal Young Nov 21 '12 at 17:03
  • $\begingroup$ Can you please clarify what a "natural LP relaxation" is? $\endgroup$ – spiffytech Nov 26 '12 at 14:30
  • $\begingroup$ If I understand you right, you mean, e.g., if cluster A has a capacity of 1x and cluster B has a capacity of 2x, Xij gives i a probability of 33% of mapping the database to cluster A, and 66% to cluster B, and I randomly choose from that distribution. Correct? $\endgroup$ – spiffytech Nov 26 '12 at 14:35
  • 1
    $\begingroup$ The LP relaxation is $\min\{ \lambda : (\forall i) \sum_{j} X_{ij} \ge 1; (\forall j) \sum_{i} L_{ij} X_{ij} \le \lambda C_{ij}; X \ge 0\}$. The variables are $\lambda$ and the $X_{ij}$'s, where $X_{ij}$ is the fraction of database $i$ mapped to cluster $j$. The constants are $L_{ij}$ (the load that database $i$ would put on cluster $j$ if mapped there), and $C_{ij}$ (the load capacity of cluster $j$). First, use an LP solver to solve this LP relaxation. Then, randomly round it by choosing, for each database $i$, a cluster $\hat j(i)$ as described in my other comment. $\endgroup$ – Neal Young Nov 26 '12 at 18:02
  • $\begingroup$ I suppose a greedy heuristic will give a fast and reasonably good solution most of the time. Do you need an optimal solution? $\endgroup$ – Paresh Dec 23 '12 at 23:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.