분산 시스템 (2) - 분포 식 클 러 스 터 컴 퓨 팅 플랫폼

분포 식 시스템 의 가장 중요 한 구성 부분 은 분포 식 계산 이다. 본 고 는 가장 중요 하고 광범 위 하 게 응용 되 는 분포 식 계산 플랫폼 을 소개 했다. MapReduce 와 PageRank 본 고의 모든 자원 은 청화대학 분포 식 계산 과정 사이트 에서 기원 되 었 고 사이트 주 소 는?http://thu-cmu.cs.tsinghua.edu.cn/curriculum/dscourse/index.html
MapReduce
MapReduce 는 분포 식 컴 퓨 팅 플랫폼 으로 사용자 에 게 병렬, 데이터 배포, 잘못 사용, 부하 균형 에 해당 하 는 구체 적 인 세부 사항 을 숨 기 고 사용자 가 단일 컴퓨터 에서 프로그램 을 작성 하 는 것 처럼 분포 식 응용 프로그램 을 작성 할 수 있 도록 합 니 다.
프로 그래 밍 모델

map(in_key,in_value)->(out_key,intermediate_value)list
reduce(in_key,list(intermediate_value))->(out_key,out_value)

mapreduce 는 map 와 reduce 두 함수 로 구성 되 어 있 습 니 다. map 함 수 는 하나의 입력 을 받 아들 입 니 다. 입력 형식 은 키 쌍 입 니 다. 요구 에 부 합 된 중간 결과 키 쌍 을 출력 한 다음 중간 에 하나의 카드 를 섞 는 단 계 를 거 쳐 같은 key 의 키 쌍 을 하나의 (in key, list (out) 로 통합 하여 입력 합 니 다. reduce 는 이러한 처 리 를 한 후에 out 의 값 을 입력 합 니 다.
wordcount
가장 간단 한 Mapreduce 예 는 바로 wordcount 입 니 다. 즉, 모든 단어 가 나타 난 횟수 를 통계 하고 우리 의 글 이 많다 고 가정 합 니 다. 따라서 우 리 는 분포 식 컴 퓨 팅 플랫폼 이 필요 합 니 다. mapreduce 는 이 임 무 를 순조롭게 완성 할 수 있 습 니 다. 예 를 들 어 우리 의 모든 map 작업 과 모든 reduce 작업 이 독립 적 이기 때문에 구체 적 으로 의사 코드 를 실현 하 는 것 은 다음 과 같 습 니 다.

map(String input_key, String input_value):
  // input_key: document name 
  // input_value: document contents 
  for each word w in input_value: 
    EmitIntermediate(w, "1"); 

reduce(String output_key, Iterator intermediate_values): 
  // output_key: a word 
  // output_values: a list of counts 
  int result = 0; 
  for each v in intermediate_values: 
    result += ParseInt(v);
 Emit(AsString(result));

map 함 수 는 각각 (문서 이름, 문서 내용) 의 입력 을 받 아들 인 다음 문서 의 모든 단어 에 하나의 (단어, "1") 키 쌍 을 출력 합 니 다. 이렇게 여러 맵 이 동시에 작 동 하고 수많은 중간 키 쌍 을 출력 합 니 다. 중간 카드 를 섞 는 단 계 를 거 쳐 같은 키 의 모든 키 쌍 이 (키, list (값) 로 통합 되 어 reduce 에 보 냅 니 다.reduce 는 list 의 값 을 더 하면 마지막 으로 얻 은 값 은 이 단어 가 나타 난 횟수 입 니 다.
PageRank
의 원리
pageRank 은 구 글 이 사이트 의 가 치 를 평가 하 는 알고리즘 모델 이다. 예 를 들 어 인터넷 에서 수 억 개의 사이트, 우 리 는 어떻게 이런 사이트 에 대해 평 점 을 한 다음 에 평 점 에 따라 순서대로 사용자 에 게 보 여 줍 니까?
PR(A)=(1−d)+(PR(T1)/C(T1)+...+PR(Tn)/C(Tn))
일단 저희 가 만약 에 링크 T1... Tn 에 링크 가 사이트 A 를 가리 키 고 있어 요.
PR: 사이트 (링크) 의 플랫폼
C (T): 사이트 T 의 출 도, 즉 사이트 T 는 다른 사 이 트 를 가리 키 는 링크 가 몇 개 있 습 니까?
d: 상수 인자
그러면 한 사이트 의 플랫폼 은 그 를 가리 키 는 모든 다른 사이트 의 평 점 에서 사이트 의 출 도 를 나 눌 수 있다. 즉, 몇 개의 중요 한 사이트 (평 점 이 비교적 높 음) 가 이 사 이 트 를 가리 키 면 이 사이트 의 평 점 도 비교적 높 아야 한다.
mapReduce 실현
우 리 는 계산 과정 이 상대 적 으로 복잡 하 다 는 것 을 알 수 있다. 특히 원시 데이터 가 있 을 때 우 리 는 모든 사이트 에 원시 적 인 평 점 을 줄 수 밖 에 없다. 그리고 우 리 는 이 알고리즘 을 한 걸음 한 걸음 반복 해서 모든 데이터 가 수렴 될 때 까지 이 임 무 를 mapReduce 에 맡 길 수 있다.구체 적 인 의사 코드 는 다음 과 같다.

parse(URL,pageContent):
  //URL:        URL
  //pageContent:     
  emit(URL,(PRinit,URLlist))

map(URL,(PR,URLlist)):
  //PR: URL   
  //URLlist： URL          
  for each URL in URLlist:
     emit(URL,PR/|URLlist|)
  //   map            ，           URL   URL  
  emit(URL,URLlist)

reduce(URL,URLlist&&URL,list(prs)):
   //reduce      ，            ，        
   pr=PR(LIST(prs))  //  pageRank         pr 
   emit(URL,(pr,URLlist))

reduce 의 출력 과 map 의 입력 이 같은 형식 임 을 볼 수 있 습 니 다. 따라서 이 작업 을 재 귀적 으로 수행 할 수 있 습 니 다. 해당 하 는 종료 조건 을 설정 하여 순환 을 중지 할 수 있 습 니 다.