안정해시 가상 노드 공간 변화의 비 증명

 

 

 

 

얼마전 대규모 스터디에서 가상 노드 공간 변화의 비에 대해 공부한 적이 있었다

이론에 따르면 가상 노드의 갯수를 늘릴 수록 데이터가 더욱 더 고르게 분포된다는 것이었다

이 이론을 보면서 느낌이 왔다, 간단한 수학으로 어느 정도 고르게 분포가 되는지를 알아낼 수 있다는 것을...

 

즉, 나는 이 비율을 숫자로 계산을 하고 싶다

실제로 증명을 해보니 어려운 수학은 들어가지 않았다

 

자 같이 증명해보자 ><

 

 

가상 노드가 없는 경우이다

 

서버 s1이 사라지면 s2(?)가 기존 보다 2배의 공간을 커버하게 된다

이런 현상을 가상 노드를 두변 해결할 수 있다

 

 

 

 

임의의 가상노드 s10을 지우고 나면 s2의 영역이 4/12에서 5/12로 늘어나는걸 볼수있다

총 (5/12) / (4/12) = 5/4로 125% 증가함을 알수있다

 

 

 

 

검증 (테스트 코드)

최종 적으로 나온 식은 1+1/n

가상노드가 없을 경우 -> n이 1일때

1+1/1 = 2

책에서는 2라고 나온다! 

 

가상노드가 세 개일 경우 (n이 4일때)

1 + 1/4 = 5/4 = 125%

역시 책에서 나온 것과 일치한다

 

(증명완료)