MapReduce 프로세스에서 "글로벌"또는 "친척"값을 계산하는 방법을 찾고 있습니다 - 평균, 합계, 최고 등. 직원의 급여와 연관된 ID가있는 직원 목록이 있다고 가정 해 봅시다. 다른 것들을 잔뜩). 처리 과정의 일부 단계에서 급여의 상위 10 %를받는 근로자가 누구인지 알고 싶습니다. 이를 위해서는 값을 "글로벌"관점으로 파악해야합니다.MapReduce - 상대 값 (평균, 최고 k 등)을 어떻게 계산합니까?
모든 값을 단일 감속기로 보낸다면 전역보기가 있지만 동시성이 느슨해지며 어색한 것처럼 보입니다. 더 좋은 방법이 있습니까?
(내가 사용하고 싶은 프레임 워크는 구글,하지만 난이 기술을 알아 내려고 노력하고있어 - 아니 프레임 워크 특정 트릭하시기 바랍니다)[편집 : 내가 오해. 상위 10 % 업데이트] "전체"와 관련된 작업을 수행하려면 총합을 먼저 결정한 다음 계산을 수행하는 것 외에 다른 방법이 없습니다.
다음과 같이 그래서 "상위 10 %의 급여는"대략 할 수있다 :
총 결정 :
MAP 출력에 2 개의 레코드 (데이터, 합계)를 지정하면이 작업을 수행 할 수 있으며, 감속기는 집계를 통해 "전체"레코드 만 건 드리면됩니다.
사용 총 :
이런 종류의 처리에 대한 가장 큰 질문은 다음과 같습니다.
스케일 아웃을 위해 가장 큰 "반드시 있어야하는"것을 깨뜨린 것입니다. 정보의 독립적 인 덩어리입니다. 이것에 의해, 「합계」값에 의존하게됩니다. "큰 데이터"에서이 작업을 수행하는 데는 두 번째 단계에서 사용할 수있는 "총"값을 만드는 기술적 방법이 필요합니다.
톰 화이트 (Tom White)의 "Hadoop - The definitive Guide"책에는 2 차 정렬에 관한 아주 좋은 장이 있습니다.
내 첫번째 생각은 이런 일을하는 것입니다 :
MAP : 사용하는 일부 더미 키, 효율성 아마도 빈 문자열로 값과 급여 및 직원 ID를 모두 보유하고 클래스를 만들 수 있습니다. 각 매퍼에서 10 개의 요소를 포함하는 배열을 만듭니다. 보고있는 처음 10 개의 급여로 채우십시오 (위치 0은 가장 높은 급여, 위치 9는 가장 높은 10 번째 임). 그 이후의 모든 급여에 대해 상위 10 위 안에 있는지 확인하고 올바른 경우 올바른 위치에 넣은 다음 적절한 경우 하위 급여를 아래로 이동하십시오.
Combiner/Reducer : 목록을 병합 정렬하십시오. 기본적으로 매퍼에서와 동일한 작업을 수행합니다. 매퍼에서와 동일한 비교/바꾸기/아래로 이동 시퀀스에 따라 병합하여 키와 일치하는 모든 배열을 반복합니다.
하나의 감속기를 사용하여 이것을 실행하는 경우 상위 10 배의 급여가 출력되도록해야합니다.
둘 이상의 감속기를 사용하는 동안이 작업을 수행 할 방법이 없습니다. 결합자를 사용하는 경우 감속기는 매퍼를 실행하는 각 노드에 대해 열 요소 배열 만 병합하면됩니다 (수천 개의 노드에서 실행하지 않는 한 관리가 가능해야 함).
나는 매퍼의 설정() 메소드에서 생성 된 키의 일환으로 UUID를 사용합니다이
맵퍼 같은 것을 할 것입니다. 매퍼는 0 또는 급여가 추가 된 UUID를 키로 내 보냅니다. 매퍼는 카운트와 합계를 누적합니다.
cleanup() 메서드에서 매퍼는 0으로 키를 추가하고 개수 및 합계를 값으로 추가 한 UUID를 내 보냅니다. map() 메서드에서 매퍼는 salary를 키로 사용하고 salary를 값으로 추가 한 UUID를 내 보냅니다.
키가 정렬되었으므로 결합기를 처음 호출 할 때 개수 및 합계가 값으로 사용됩니다. 결합자는 클래스 멤버로 저장할 수 있습니다. 우리는 또한 전체 카운트의 10 %가 무엇인지 알아낼 수 있으며, 클래스 멤버뿐만 아니라 그것을 저장합니다. 우리는 목록을 초기화하고 그것을 반원으로서 저장한다.
이후의 결합 자 호출은 값으로 급여를 포함하며 정렬 된 순서로 도착합니다. 이 값을 목록에 추가하고 동시에 카운터를 증가시킵니다. 카운터가 값 top에 도달하면 더 이상 값을 목록에 저장하지 않습니다. 우리는 나머지 combiner 호출에서 값을 무시합니다.
combiner cleanup()에서 emit을 수행합니다. 결합자는 UUID 만 키로 방출합니다. 값에는 count 및 total과 값의 상위 10 %가옵니다. 따라서 결합기의 출력에는 매퍼를 통과 한 데이터의 하위 집합을 기반으로 한 부분 결과가 있습니다.
각 매퍼/결합기가 하나의 키만 방출하므로이 경우 감속기가 매퍼의 수만큼 호출됩니다.
감속기는 reduce() 메소드에서 개수, 합계 및 상위 10 % 값을 누적합니다. cleanup() 메서드에서 평균값이 계산됩니다. 또한 상위 10 %는 감축 기의 각 호출에 도착하는 상위 10 % 집계에서 정리() 메소드로 계산됩니다. 기본적으로 병합 정렬입니다.
reducer cleanup() 메소드는 평균값이 첫 번째 행에 있고 그 다음에 이어지는 행에서 급여의 상위 10 %가되도록 여러 개의 방출을 수행 할 수 있습니다.
마지막으로 최종 집계 통계가 글로벌임을 확인하려면 축소 자 수를 1로 설정해야합니다.
감속기에는 데이터 누적 및 정렬이 있기 때문에 부분 데이터 세트에서 메모리 문제가있을 수 있습니다.
감사합니다. Niels,하지만 아직 이해가 안됩니다.맵과 무효화의 무국적 특성 때문에 어떤 시점에서도 10 %의 정확한 한계를 알지 못합니다. 목록을 10 % 내가 원하는 값으로 정렬하더라도, 각 감속기는 전체 목록에서 해당 부분의 위치를 알지 못합니다. 단 하나의 감속기 만 사용하지 않으면 실제로 "전역" 전망. –
안녕하세요, 귀하의 질문 "톱 10"을 오해하여 답변을 업데이트했습니다! = "상위 10 %". 닐스 –