분산하는 알고리즘에 대해서..
글쓴이: irdeal / 작성시간: 토, 2007/04/07 - 12:30오후
임의의 스트링이 입력됩니다....그걸을 간단하게 해쉬해서 4바이트 정수로 만들었습니다..각각의 스트링을 특정 서버에 분산을 하려고 합니다..
서버가 2대 있다고 가정하면 2대에 분산시키기 위해 %2 연산을 사용했습니다. 그래서 2대로 분산이 되는데 이제 서버가 3대로 늘어납니다. 3대로 늘어날때
기존의 분산을 최대로 유지하면서 확장시키고 싶습니다. 3대에서 4대로...4대에서 5대로...계속 해서 서버는 늘어나게 됩니다..함수가 계속 변해야 할꺼 같은데.
이런 문제를 풀수 있는 방법이 있을가요?
서버가 확장 될 때 기존의 결과에서 조금씩만 확장할 수 있는방법 정도랄까요.....예를 들면 아래와 같은데....4대에서 5대로 넘어갈때는 잘안되네요..그리고..서버가 늘어감에 따라 어떤 함수(?)를
써야 할지도 잘 모르겠고요...방법이 있을꺼 같기도 한데....영 감을 못잡겠습니다...
-----1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 9 0 1 2
2대 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
3대 0 1 2 1 0 2 0 1 2 1 0 2 0 1 2 1 0 2 0 1 2
4대 0 1 2 3 0 2 3 1 2 1 0 3 0 1 2 3 0 2 3 1 2
5대 0 1 2 3 4 2 3 1 4
Forums:
알고리즘도 못하고
알고리즘도 못하고 질문의 내용도 제대로 이해는 못하지만...
간단하게 라운드 로빈을 구현하면 어느정도의 분산을 유도할 수 있을 것 같구요.
입력을 받는 한 대의 서버에서 SNMP(혹은 직접 제작한 부하를 측정하는 프로그램) 를 이용하여 하위 서버들에 대한 부하를 측정하여 부하가 가장 적은 서버들에게 나누어 주는 방법.
또는, 내부 도메인을 이용해서 부하를 분산하는 방법 ( 이역시 라운드 로빈과 비슷하군요... )
대략 이정도가 생각이 나는군요.
그나저나... 위의 예의 규칙은 이해하기가 힘드네요 @..@;;;
제가 파악하기로는 --- 부분의 숫자는 입력값의 갯수. 아래쪽은 모듈러 연산을 통한 어떤 결과값 이라고 판단했습니다.
예로 든 부분을 조금 더 이해하기 쉽게 설명해 주시면 많은 분들이 답을 달아주실 것 같습니다.
그리고.... 분산 알고리즘이라고는 라운드 로빈밖에는 모르지만, 특별한 경우(서버 대수가 이빠시 많은 경우.. )가 아닌 이상 서버가 확장됨에 따라 알고리즘을 수정하는 것은 이해가 안됩니다.
대수가 늘어남에 따라 서버의 정보만 추가하면 동일한 알고리즘으로 돌아가야 정상이 아닐까요 ?
음..
임의의 스트링을 해쉬함수를 돌리면 abc--10000 bcd--10001 cde--10002 def -- 10003 efg --- 10004 와같이 같은 스트링에 대해선 같은 정수값이 나올것입니다.
임의의 스트링이 계속해서 들어오고 그것의 해쉬를 하면 특정정수값이 계속 입력이 될것입니다. 이것을 분산하는 건데요..서버가 두대 있을때
abc == 0 번서버 bcd == 1번서버 cde == 0번 서버로 보내서 서비스를 할 수 있습니다. abc라는 스트링이 입렵되면 0번서버가 무조건 서비스를 하는것이지요..
그런데 서버가 3대로 들어나게 되면..
abc == 0번서버 bcd == 1번서버 cde == 2번 서버에서 서비스를 하게 됩니다. cde만 새로 생긴 서버에서 서비스를 하고 abc, bcd는 기존의 서버에서 서비스를 하게 됩니다.
그런데 단순히 모듈라 연산만을 하게된다면
abc bcd cde def efg fgh
0 1 0 1 0 1
0 1 2 0 1 2
와 같이 되어서 def와 efg같은 경우는 불필요하게 서버가 변경되게 됩니다. 이런 것을 최소화하면서 서버를 늘리는 방법에 대해 알아보고 있습니다. 서버가 2대일때 def는 1번서버에서 서비스를 받는데 서버가 3대로 늘어나게되도 1번서버에서 서비스를 받게 할 수 있는 방법은 없을까요?
May The Force Be With You
irdeal
May The Force Be With You
irdeal
해쉬값이 각각 000,
해쉬값이 각각 000, 001, 011, 101, 110, 111 인 데이터가 있다고 하면,
처음에 서버가 두대일 경우는 가장 아래 비트를 보고 분할합니다.
그럼 다음과 같이 되겠죠.
첫 번째 서버: 000, 110 (마지막 비트가 0인것)
두 번째 서버: 001, 011, 101, 111 (마지막 비트가 1인것)
이 상태에서 서버가 한대 늘어 두번째 서버를 분할하기로 하면, 데이터는 다음과 같이 되겠죠.
첫 번째 서버: 000, 110 (마지막 비트가 0인것)
두 번째 서버: 001, 101 (마지막 비트가 01인것)
세 번째 서버: 011, 111 (마지막 비트가 11인것)
분산이 잘 안될꺼 같은데요...
먼저 답변에 감사드립니다..
답변해주신대로 하게되면...서버를 늘리게 될때 첫번째 서버가 가지고 있던 로드는 분산이 안되는것 같습니다. 첫번째 서버의 로드도 세번째 서버가 좀 가지고 가야 하거든요 ^^;
이런문제를 푸는 알고리즘 같은 것이나 참조할 만한 것이 없을까요?
May The Force Be With You
irdeal
May The Force Be With You
irdeal
http://kmh.ync.ac.kr/comScien
http://kmh.ync.ac.kr/comScience/general/DS/Hash/hash.html
여기에 동적해싱, 확장해싱 설명이 있습니다.
seoleda님의 설명을 정확히 하자면
첫 번째 서버: 000, 110 (마지막 비트가 0인것)
두 번째 서버: 001, 101 (마지막 비트가 01인것)
세 번째 서버: 011, 111 (마지막 비트가 11인것)
가 아니라
1 서버: 00, 10 (마지막 비트가 0인것)
2-1서버: 001, 101 (마지막 비트가 01인것)
2-2서버: 011, 111 (마지막 비트가 11인것)
이런 식으로 되는 것입니다.
서버가 추가되면 기존의 서버가 분할되므로 로드가 분산됩니다.
그런데 구체적으로 무슨 데이터를 분산하려고 하시는 건가요?
재벌 2세가 재벌이 될 확률과
금메달리스트 2세가 금메달을 딸 확률이 비슷해지도록
자유오픈소스 대안화폐를 씁시다.
아이디의 아이디어 무한도전
http://blog.aaidee.com
귀태닷컴
http://www.gwitae.com
매우 랜덤한 url을 분산하기 위함입니다.
서버로 접속하면 분산알고리즘을 통해 어느서버에서 처리할지를 결정해주는 부분입니다. 그런데 2-1과 2-2로 2번서버가 나뉘게 되면 1번서버가 처리하던 부하는 전혀 분산되지 않게 되는것 같군요..
서버를 1,2,4,8,16,32 대로 늘리게 되면 %연산만으로도 가능할텐데...서버의 증가가 하나씩 된다고 할때...적절한게 분산해주면서 기존 서버가 처리하던부분도 유지하는 것이 필요해서요..
테이블을 유지해서 하는 방법도 있겠지만...입력되는 url이 매우 다양하고 많이 들어옵니다. 하루에 유니크한 url이 100만게 정도 들어온다고 생각할 수 있겠군요..
May The Force Be With You
irdeal
May The Force Be With You
irdeal
궁금해서 찾아봤지만
궁금해서 찾아봤지만 잘 모르겠습니다.
동적해싱(Dynamic hashing) 알고리듬의 종류 중에 확장해싱(Extendible hashing), 선형해싱(Linear hashing)이 있습니다.
가상해싱(Virtual hashing)이란 표현도 있는데 어디에 속하는지 모르겠습니다.
seoleda님이 설명하신 알고리듬이 확장해싱이라고 부르는 것 같습니다.
1서버가 오버플로되어서 1-1, 1-2로 스플릿되기 전까지는 부하가 분산되지 않는 것은 맞습니다.
'적절한게 분산해주면서 기존 서버가 처리하던부분도 유지하는 것'
적절한 분산이란 말씀은 기존서버가 처리하던 부분의 일부가 옮겨간다는 뜻이기 때문에 유지된다는 것와 상충합니다.
따라서 그 정도에 대한 더 명확한 설명이 필요합니다.
재벌 2세가 재벌이 될 확률과
금메달리스트 2세가 금메달을 딸 확률이 비슷해지도록
자유오픈소스 대안화폐를 씁시다.
아이디의 아이디어 무한도전
http://blog.aaidee.com
귀태닷컴
http://www.gwitae.com
cleansugar님께서 잘
cleansugar님께서 잘 설명해 주셨습니다만, 위 방법은 데이터의 재 조직화를 줄이기 위한 방법입니다.
단순히 랜덤한 URL을 분산하기 위한 목적이면, 랜덤함수를 사용하거나 라운드로빈 방식을 고려하는 것이 좋을것 같습니다.
다만, URL에 따라서 특정한 데이터가 저장되고, 차후에 그 데이터를 참조해야 한다면, 위 방법은 가장 부하가 많이 걸리는 서버만 분할하기 때문에 데이터의 재 조직화를 최소화 할수 있습니다. 그리고, 각 서버에 걸리는 부하를 살펴보면 동일하게 걸리지는 않지만, 대충 비슷하게는 걸릴겁니다.
예를 들어 3대의 서버에 각각 30% 30% 40%의 부하가 걸린다면, 위 방법으로 서버를 한대 더 추가 함으로서 부하를 각각 30%, 30%, 20%, 20%로 분할 할 수 있고, 첫 번째와 두 번째 서버는 데이터를 재구성할 필요가 없으니깐, 유지보수 측면에서도 유리합니다. 이런방법은 동적해싱, 버디알고리즘에서 사용하고 있습니다.
p.s. 첫 번째 서버의 로드를 가져가야 하는 특별한 이유가 있나요?
그러니까 seoleda님
그러니까 seoleda님 말씀은 읽히기 위한 분산처리면 그냥 랜덤함수나 라운드로빈으로 뿌려주면 된다.
그러나 DB에 저장할꺼면 동적해싱으로 저장하라는 뜻입니다.
재벌 2세가 재벌이 될 확률과
금메달리스트 2세가 금메달을 딸 확률이 비슷해지도록
자유오픈소스 대안화폐를 씁시다.
아이디의 아이디어 무한도전
http://blog.aaidee.com
귀태닷컴
http://www.gwitae.com
댓글 달기