22. 13장 : EXTERNAL SORTING (5) - 병렬처리

병렬 시스템에서 하는 작업이 곧 앞에서 배운 알고리즘이랑 매우매우 유사하다고한다!

Hash

새로운 해시함수 hn을 이용해서 각각의 컴퓨터의 디스크에 있는 데이터들을, 다른 컴퓨터로 전송한다 (네크워크로!)

=> 즉, hn는 데이터를 컴퓨터간에 파티셔닝하는것! (두 레코드가 동일하면, 해시값도 같으니까 같은 컴퓨터로감)

=> 똑같은 레코드는 같은 컴퓨터로 가니까, 이 다음부터는 각 컴퓨터가 알아서 hash과정을 진행한다 (hp부터 시작해서 hr까지)

이 때, hn을 진행할 때 각 컴퓨터에서 전송하는거니까 병렬로 처리된다.

그리고 각 컴퓨터에서 따로 hash알고리즘 (hp, hr)을 적용하므로, 이 또한 병렬로 처리된다.

즉 전체적으로 봤을때 여전히 4N I/O가 필요하다.

근데, 전체 I/O 비용은 같은데, 이걸 각 컴퓨터마다 병렬처리를 진행하므로...

=> 컴퓨터의 개수만큼 처리속도가 빨라진다!

Sort

각 컴퓨터에게 데이터를 나눠주는 단계가 hash와 차이가 있다.

맨 처음에 컴퓨터에게 데이터를 나눠줄 때, hash처럼 냅다 보내는게 아니라 나름의 범위를 정해서 보내준다!!

(0-10은 1번컴퓨터로, 10-20은 2번컴퓨터로,, 같은 느낌으로)

그리고 각 컴퓨터에서 정렬 알고리즘을 실행한 다음에 합쳐주기만 하면 된다. (컴퓨터마다 범위별로 나눠놨기 때문에)

단점

sort의 단점은 hash와 다르게 모든 컴퓨터가 동일한 양의 일을 받는걸 보장할수가 없다.

즉 특정 범위에 데이터가 몰려있으면,, 어떤 컴퓨터 혼자 많은 일을 해야할수가 있다. == 데이터 편향 (data skrew)

해결방법은 값의 분포를 파악해서 어디서 분할할지 분할key를 파악해서 나눠주면 된다.