[번역] Virtual Nodes Strategies[번역] Virtual Nodes Strategies

Posted at 2013. 4. 10. 12:30 | Posted in Article

redis shard를 virtual node를 입혀보려고 연구중.

사례 및 기술연구를 위해 몇몇 문서를 번역해 본다.


※ 오역에 주의하시고, 잘못 번역된 부분은 댓글로 알려주세요. 





Virtual Nodes Strategies

consistent hasing 에서 각 호스트에 single "token" in a "hash-space" 를 두는 것은 약간 손해가 있는 모델이다.
데이터 추가가 될 때 1/N로 들어가므로 balanced cluster가 된다.
Fig 1. Partitioning of hash-space between 4 hosts in a cluster

그러나 새로운 호스트가 추가되면 unbalanced cluster가 된다.

이를 해결하기 위해 권장되는 방법은 scaling up시 호스트를 2배로 늘리거나, scaling down시 호스트 수를 반으로 줄이는 방법이 있다. 그리고, 모든 다른 호스트로 token을 이동시켜 균형을 잡게 해야 한다. 이 방법은 소규모 클러스터에서나 실행 가능하고, 큰 큐모에서는 사용하기 어렵다.


Fig 2. Balancing a cluster when adding hosts requires moving tokens (top) or doubling the number of hosts (bottom)

이 문제들은 operation들을 매우 복잡하게 만든다. 카산드라 관리자는 balanced load를 보장하는 token들의 주의 깊은 선택을 해야하고, 호스트가 추가될 때 수작업으로 rebalancing을 해줘야 한다. 이런 문제를 해결하는 한가지 방법은 virtual node를 사용하는 것이다. virtual node를 사용하는 consistent hashing schema는 각 호스트가 인접하지 않은 범위에 데이터를 다중으로 둘 수 있게 한다. virtual node를 사용함으로써 얻는 이득은 다음과 같다:
- 클러스터에 추가된 호스트는 서로 다른 호스트로부터 가져온 데이터로 클러스터를 평탄하게(even portion) 만드는 책임을 맡게된다.
- 하나의 호스트에 장애가 발생하면, 클러스터의 다른 호스트들로 로드가 균등 분배될 것이다.
Rebuilding a dead host will be faster as it will involve every other host (뭔소린지..)
- 호스트에 할당되는 파티션 수는 자신의 용량(capacity)에 의해 결정될 수 있다. 이것은 각기 다른 하드웨어의 사용도 허용하게 한다.


Virtual nodes schemes

대체로 다음 세가지 형태로 분류 해볼 수 있다.

Random token assignment
각 호스트에 T 개의 random token들을 할당한다. 파티션은 각 호스트의 token들의 각각에 할당되고, 파티션은 ring에서 하나의 token과 그 이전 token의 구간(interval)로 정의된다. 호스트가 ring에 추가됐을 때, T개의 random token들이 할당된다. T random tokens which will result in a portion of an existing partition being assigned to that host.(뭔소린지..)

이 방식은 memcached server사이의 분배/분산(distribution)를 위한 libketama[2] 에서 사용되고, T=1일때 카산드라 분산(distribution)을 위한 일반화 방법이다. (역주: 카산드라는 호스트 하나가 토큰 구간(interval) 하나를 전담하게 된다는 뜻인 듯 - 카산드라쪽을 더 알아보자.)

Fig 3. Partitioning by random token assignment


Fixed partition assignment

해시 공간을 균등한 크기 Q개로 나누고, 각 호스트에는 Q/N 개씩 할당한다(N는 호스트 수). 호스트가 추가될 때 다른 호스트에서 몇개를 가져와서 Q/N 비율을 맞춘다. 호스트를 제거할 때는 제거되는 호스트의 파티션을 다른 호스트로 재분배해서 Q/N 비율을 맞춘다.

이 방식은 Dynamo[3]와 Voldemort[4]에서 사용된다.

Fig 4. Fixed partitioning assignment


Automatic sharding

각 호스트에 하나의 token을 할당하고, 각 호스트는 하나의 파티션(token의 interval로 정의됨)을 갖는다. 하나의 파티션이 한계를 초과하면, 새로운 파티션을 생성할 수 있게 해당 파티션의 구간에 새 token이 추가된다. (역주: 즉, 파티션은 token의 interval(구간)을 의미하고, 용량 초과된 파티션에 새로운 구간(token)을 생성한다는 의미. Partition dividing assignment라고 해야 의미가 더 맞지 않을까?)

이 방식은 BigTable[5] 또는 Mongo auto-sharding[6] 에서 수행되는 sharding 방식과 비슷하다.

Fig 5. Automatic sharding: when a partition contains too much data it is split into smaller partitions


Evaluation(평가)

이 스키마들을 평가하기 위해 구현의 차이에 대한 생각(idea)과 이들이 클러스터의 성능에 어떻게 영향을 미치는지에 대한 것들이 필요하다. 이 스키마들의 주요 차이점은 파티션 size와 파티션들의 수이고, 이 두가지가 어떻게 클러스터 size와 데이터 size를 변하게 하는지 살펴본다.

Number of Partitions(파티션 수)
클러스터 메타데이터의 일부분으로써 그것이 저장된 호스트에 파티션의 할당 매핑을 저장해야 한다(must store the assignment mapping of partition to the host on which it is stored). 카산드라에서 이 매핑의 배치는 호스트간에 gossip을 이용한다. 모든 호스트는 클라이언트의 요청은 정확한 replica로 한 홉에 라우팅할 수 있어야 하고, 모든 데이터 위치를 인지하고 있어야 한다. 만약 파티셔닝 스키마가 더 많은 파티션을 요구하면, 카산드라 gossip 시스템에 더 많은 부하와 더 많은 메모리를 사용하게 될 것이다. (If our partitioning scheme results in more partitions then this placement metadata will be larger, will put more load on Cassandra's gossip system, and will use more memory to store.)

Partition Size(파티션 크기)
카산드라에서는 한 번 실행될 때 전체 파티션으로 수행되는 프로세스들이 있다. 예를 들면, 다른 replica의 데이터와 비교할 수 있도록 저장되는 모든 데이터를 위한 digest를 계산하는 repair 같은 것이다. 클러스터에 참여하는 새로운 호스트의 bootstrapping 같은 스트리밍 operation들도 전체 파티션을 읽을 것이다. 매우 큰 파티션을 가지기에 몇가지 불리함(disadvantages)이 있다: 이런 프로세스들 중 하나가 실패하거나 에러가 발생하게 되면 반드시 재시도해야 한다. 큰 파티션에서, 에러로 인해 더 많은 작업이 낭비되게 된다. 새로운 호스트의 bootstrapping(bootstrapping a new host)이 많은 시간을 소비할 때, 한 파티션의 전송 에러는 매우 높은 비용이 들게한다. 작은 파티션에서는 balancing을 위해 클러스터내 다른 호스트에 영향을 주는 이런 operation들을 늦출 수도 있다.
하지만, 우리는 파티션을 매우 작게 만들 수 없다. 많은 작은 파티션들을 읽는 것은 데이터를 전송하기보다 파티션들을 탐색하느라 디스크에서 대부분의 시간을 소비하는 결과를 만들 수 있다. 우리는 random disk access보다는 sequential disk access로 읽으면서 충분히 큰 파티션이 되기를 원한다.

Comparison
Table1은 


<진행중>...













//

3G 모바일 네트워크에 대한 이해3G 모바일 네트워크에 대한 이해

Posted at 2012. 9. 20. 14:49 | Posted in Article

3G 모바일 네트워크에 대한 이해(NHN개발자블로그)

http://helloworld.naver.com/helloworld/111111


3G 네트워크에 대한 이야기+a (deview 2012)

http://deview.kr/2012/xe/index.php?mid=track&document_srl=397&time_srl=260


살펴보고 내용 정리하기.




//

Chat Server with ErlangChat Server with Erlang

Posted at 2012. 9. 8. 23:37 | Posted in Article

http://www.erlang-factory.com/upload/presentations/31/EugeneLetuchy-ErlangatFacebook.pdf
http://blog.whatsapp.com/index.php/2011/09/one-million/

//

망하는 제품의 흔한 개발 과정망하는 제품의 흔한 개발 과정

Posted at 2012. 3. 5. 00:07 | Posted in Article

출처: http://wangsy.com/blog/2012/01/how-to-make-totally-shitty-things/

망하는 제품의 흔한 개발 과정

  • 리더 : 요즘 유행하는 대세를 들고 온다. 이것이 대세다!
  • 리더 : 속으로는 이런 것들을 쓰는 사람들은 사회부적응자라 생각하고 본인은 정작 써 본 적이 없다.
  • 기획 : 써 본적은 없지만 들어는 봤다. 이런 것을 쓰는 사람은 격이 떨어지는 사람이라 생각하고, 내가 우아하고도 유럽 명품에 견줄 수 있는 것을 보여주어야 겠다 생각한다.
  • 기획 : 해당 제품군을 모조리 조사한다. 그래서 해당 제품군의 모든 특징을 합한 고질라 같은 것을 그려 낸다.
  • 리더 : 그것만으로는 뛰어 넘을 수 없다고 한다.
  • 기획 : 아이디어를 동원한다. 이제 그 고질라에 스타워즈, 반지의 제왕, 해리포터를 더하기 시작한다. 자신의 상상력의 끝은 어디인가 하면서 스스로 놀라워 한다.
  • 리더 : 고질라에서 빠진 게 없나 살핀다. 다소 억지 스럽지만, 비슷한류의 제품을 가져와 하나 더 붙인다. 이런게 바로 리더의 통찰력이라 으쓱거린다. 기획자의 아이디어를 보고는 기획자가 미쳐 생각하지 못한 경우의 수를 생각해서, 더 복잡하게 만든다. 아직 가르칠게 많다고 생각한다.
  • 개발 : 그런건 못만들어요 불평을 늘어놓는다.
  • 리더 : 내앞에서 안된다는 말은 하지 말라고 하며, 할 수 없다는 것부터 이야기하는 태도가 문제라고 한다. 그리고는, 자신의 인생 역정기를 늘어 놓는다.
  • 개발 : 기획에 대한 조언을 해 줘야 겠다고 생각한다. (사실 해당 제품군을 사용해 본 유일한 사람이다.)
  • 리더 : 넌 아직 인지과학, 심리학을 모른다고 일축한다.
  • 기획 : 파워포인트로 찍어 내는 노가다를 시작한다.
  • 리더 : 문서에서 오타를 찾아 낸다.
  • 개발 : 이 프로젝트는 어짜피 산으로 갈 것이라고 떠들어 대기 시작한다.
  • 리더 : 최근 세미나에서 본 솔루션들을 쓰면 금방 할 것이라고 말한다. 그리고 비싼 돈을 들여 도입을 추진한다.
  • 개발 : 그게 뭔지 모른다. 다만, 대충 들어보니, 그것 보다는 자기간 만들어 놓은 자작 솔루션이 훨씬 더 좋은거라고 속으로 생각한다.(사실 지금 이 상황에 그걸 배워서 만드는 것은 엄두가 나지 않는다) 그리고, 쓰는 척 시늉만 하기로 결심한다. 타인이 만든 것을 사용하는 것은 하수들이나 하는 짓이라 생각한다.
  • 리더 : 개발기간은 3개월이라 한다.
  • 개발 : 불가능한 일정이라 하고, 기획안을 조정하라고 주장한다.
  • 리더 : 나는 어찌 저런 무능하고 게으른 개발자만 옆에 있는지 탄식한다. 나에게 해외 유수기업의 개발자를 붙여주면 단박에 성공 할 수 있으리라 생각한다.
  • 개발 : 투덜거리며 밤 샌다. 불행하게도 고질라를 만들어 내는 과정과 SF 가 붙여 지는 과정은 개발 과정 진행중에 병행해서 발행하는 일이다. 스타워즈를 다 붙여놓으면, 어느덧 스토리는 해리포터로 바뀌어 있다. 다시 밤을 샌다.
  • 리더 : 3개월 후면 다 되어 있겠지 생각을 한다. 개발 과정에는 관심이 없다. 개발이 진행되는 중간 중간, 어제밤 자다가 생각난 환타스틱한 장면을 기획자에게 넣으라고 말한다. 이 장면을 놓쳤으면 이번 제품에 핵심이 빠졌을 거라고 생각하고, 이제라도 넣게 되어 다행이다 생각한다. 그리고, 자신이 얼마나 디테일에 강한가 다시 한번 생각해 본다.
  • 개발 : 코드는 개떡이 되어 간다. 어짜피 이건 내탓이 아니다. 정말 제대로 된 환경에서 했다면, 난 정말 멋지게 해 낼 수 있었을 텐데, 운없이 이런 놈들이랑 팀을 해서 이렇게 된거라 생각한다. 이 제품은 내 손에서 나왔지만, 내가 만든건 아니라 생각한다.
  • 리더 : 3개월후, 생각했던게 안나오자 개발자에게 책임 추궁을 해야겠다 생각한다. 처음부터 태도도 안좋았고, 자기가 말한 것을 구현해 낼 실력도 없었던 사람이었다 생각한다. 후회한다. 이 모든 것은 개발의 문제다. 하지만, 일단 출하한다.
  • 기획 : 자신의 유럽 명품적 감각의 파워포인트를 어떻게 이런 제3세계 제품으로 만들어 냈는지 의아해 한다.
  • 리더 : 다시 시작하자 으쌰 으쌰 해 본다. 그리고, 그 사이 대세가 바뀌지 않았다 살펴 본다.
  • 개발 : 어짜피 이렇게 된거, 처음부터 다시 시작하자고 한다. 나는 다시 내가 만든 것을 들여다 보고 싶지 않다.
  • 리더 : 역시 중요한 것은 사람이다 라고 생각한다.


흥하는 제품의 흔한 개발 과정

  • 리더 : 자신에게 꼭 필요했던 핵심가치(기능)을 발견한다. 현존하는 타 제품에서는 발견할 수 없기에, 만들어야 겠다고 결심한다.
  • 기획,개발 : 자신도 꼭 필요했던 것이라 생각하고, 만들면 정작 자신이 가장 큰 혜택을 받을 것이라 생각한다.
  • 리더,기획,개발 : 다 같이 모여서 기존 제품들을 맹렬히 비판해 낸다. 왜 다 이렇게 될 수 밖에 없었는지 생각해 본다.
  • 개발 : 관련된 기술을 조사한다. 그리고, 조사한 결과를 공유한다.
  • 기획 : 수없이 많은 기술을 가지고, 두개의 연결(조합)을 시도한다. 전혀 상관없을 것이라 생각했던 두가지 기술을 합하니, 매우 멋진 모습이 되었다.
  • 리더 : 이 멋진 조합이 핵심가치를 구현하는 결정적 요소가 아니면, 버리자고 한다. 핵심가치에만 촛점을 맞춘다.
  • 개발 : 핵심가치를 구현할 가장 단순한 방법을 찾는다. 구현이 단순할 수록 생각치 못한 일이 발생할 가능성이 줄어 든다.
  • 리더 : 개발된 시제품을 써 본다. 하루고 이틀이고 계속 써 본다. 불편한 점을 찾거나, 그 보다 더 단순하게 할 방법을 생각해 낸다.
  • 개발 : 반복적으로 만들어 낸다. 구현 방법이 단순하였기에, 이 반복과정이 고통스럽지 않다. 이 반복과정을 더 쉽게 할 수 있는 방법을 계속 추가해 낸다.
  • 기획 : 이 단순한 핵심가치를 제공하는 이 제품이 생각보다 많은 곳에서 응용될 수 있다는 것을 찾아 낸다.
  • 리더 : 기쁘지만, 처음 생각한 것에 집중하기로 한다.
  • 리더 : 충분히 만족스러운 상태가 되면 제품으로 출하한다. 충분히 고민한 것이기 때문에, 아주 오랫동안 다시 이 문제를 생각할 필요가 없을 거라 생각한다. 누군가 흉내내면서 새로운 것을 덧붙여 내거나 변형을 시켜내도 크게 신경 쓰지 않는다.
  • 기획 : 현재까지 이룩한 것에서 최소한의 노력으로 추가할 수 있는 핵심가치를 다시 찾기 시작한다.
  • 리더 : 역시 중요한 것은 사람이다 라고 생각한다.

//

클라우드, 빅데이터 관련 기사/글클라우드, 빅데이터 관련 기사/글

Posted at 2012. 3. 4. 20:43 | Posted in Article
//

Chat Server with ErlangChat Server with Erlang

Posted at 2011. 12. 14. 11:12 | Posted in Article
http://www.erlang-factory.com/upload/presentations/31/EugeneLetuchy-ErlangatFacebook.pdf
http://blog.whatsapp.com/index.php/2011/09/one-million/

 
//

C500k in Action at Urban AirshipC500k in Action at Urban Airship

Posted at 2011. 11. 23. 19:26 | Posted in Article
//

Why mobile apps suck when you're mobileWhy mobile apps suck when you're mobile

Posted at 2011. 11. 23. 19:26 | Posted in Article
http://blog.davidsingleton.org/mobiletcp


- small packet (request/response workload): short timeout
   iPhone의 TCP rexmit timout은 1, 1, 3, 6, ... 이렇게 되니까 오늘 세미나 내용에서도 나왔던
   sleep -> connected state로 가는 데 3초 정도이라면 1+1+3 초 timeout에 성공하게 되고요,
   
5초입니다. short timeout을 잘 define해야 하는데요. 
   Android는 TCP rexmit TO이 3,3,6,9... 이기에 3+3 인 6초에 성공하게 됩니다. 
   여기에 실제 RTT 200-500ms 를 더하면 7-8초는 기본 mobile timeout이 되어야 한다로 정리될 것 같네요.

- Try to use underlying TCP socket instead of HTTP: HTTP layer가 기존의 TCP session을 재 사용하기 때문에.
   이건 2가지 상반되는 이야기기 있는데, socket reuse하면 congestion window가 full open되어 있기에
   bandwidth sensitive 한 workload에 좋은 반면에 문제가 있는 TCP session은 다시 맺는 게 좋을 것 같다인데
   이것도 위의 sleep -> connected state의 시차 때문에 생기는 illusion인 것 같네요. 6초 timeout에 걸리는 
   connection이 다시 열면 바로 연결되겠죠.

 
//

A Day in the Life of a Mobile Device: IP ConnectivityA Day in the Life of a Mobile Device: IP Connectivity

Posted at 2011. 11. 23. 19:26 | Posted in Article
//

Facebook Developers - Social DesignFacebook Developers - Social Design

Posted at 2011. 11. 23. 19:25 | Posted in Article
//