原題網址:http://www.lintcode.com/en/problem/consistent-hashing/
一般的資料庫進行horizontal shard的方法是指,把 id 對 資料庫伺服器總數 n 取模,然後來得到他在哪台機器上。這種方法的缺點是,當資料繼續增加,我們需要增加資料庫伺服器,将 n 變為 n+1 時,幾乎所有的資料都要移動,這就造成了不 consistent。為了減少這種 naive 的 hash方法(%n) 帶來的缺陷,出現了一種新的hash算法:一緻性哈希的算法——Consistent Hashing。這種算法有很多種實作方式,這裡我們來實作一種簡單的 Consistent Hashing。
- 将 id 對 360 取模,假如一開始有3台機器,那麼讓3台機器分别負責0~119, 120~239, 240~359 的三個部分。那麼模出來是多少,查一下在哪個區間,就去哪台機器。
- 當機器從 n 台變為 n+1 台了以後,我們從n個區間中,找到最大的一個區間,然後一分為二,把一半給第n+1台機器。
- 比如從3台變4台的時候,我們找到了第3個區間0~119是目前最大的一個區間,那麼我們把0~119分為0~59和60~119兩個部分。0~59仍然給第1台機器,60~119給第4台機器。
- 然後接着從4台變5台,我們找到最大的區間是第3個區間120~239,一分為二之後,變為 120~179, 180~239。
假設一開始所有的資料都在一台機器上,請問加到第 n 台機器的時候,區間的分布情況和對應的機器編号分别是多少?
Notice
你可以假設 n <= 360. 同時我們約定,當最大區間出現多個時,我們拆分編号較小的那台機器。
比如0~119, 120~239區間的大小都是120,但是前一台機器的編号是1,後一台機器的編号是2, 是以我們拆分0~119這個區間。
Have you met this question in a real interview? Yes Clarification
If the maximal interval is [x, y], and it belongs to machine id z, when you add a new machine with id n, you should divide [x, y, z] into two intervals:
[x, (x + y) / 2, z]
and
[(x + y) / 2 + 1, y, n]
Example
for n =
1
, return
[
[0,359,1]
]
represent 0~359 belongs to machine 1.
for n =
2
, return
[
[0,179,1],
[180,359,2]
]
for n =
3
, return
[
[0,89,1]
[90,179,3],
[180,359,2]
]
for n =
4
, return
[
[0,89,1],
[90,179,3],
[180,269,2],
[270,359,4]
]
for n =
5
, return
[
[0,44,1],
[45,89,5],
[90,179,3],
[180,269,2],
[270,359,4]
]
方法:使用堆來維護區間。
public class Solution {
/**
* @param n a positive integer
* @return n x 3 matrix
*/
public List<List<Integer>> consistentHashing(int n) {
// Write your code here
PriorityQueue<Range> heap = new PriorityQueue<>(16,
new Comparator<Range>() {
@Override
public int compare(Range r1, Range r2) {
if (r1.to - r1.from > r2.to - r2.from) return -1;
if (r1.to - r1.from < r2.to - r2.from) return 1;
return r1.id - r2.id;
}
}
);
heap.offer(new Range(1, 0, 359));
for(int i = 2; i <= n; i++) {
Range range = heap.poll();
Range range1 = new Range(range.id, range.from, (range.from+range.to)/2);
Range range2 = new Range(i, (range.from+range.to)/2+1, range.to);
heap.offer(range1);
heap.offer(range2);
}
Range[] ranges = heap.toArray(new Range[0]);
List<List<Integer>> results = new ArrayList<>(ranges.length);
for(int i = 0; i < ranges.length; i++) {
List<Integer> result = new ArrayList<>(3);
result.add(ranges[i].from);
result.add(ranges[i].to);
result.add(ranges[i].id);
results.add(result);
}
return results;
}
}
class Range {
int id;
int from, to;
Range(int id, int from, int to) {
this.id = id;
this.from = from;
this.to = to;
}
}