Cosequential Processing이란, 2개 이상의 리스트를 입력으로 받아서, 각각의 리스트에 대해 선형적인 작업을 한 뒤 단일한 하나의 출력을 내는 것을 말한다. 왜 이런 작업이 필요한 것일까? 예를 들어, 현재 사용 가능한 메모리보다 다루어야 하는 데이터가 훨씬 크다면, 어쩔 수 없이 분할된 형태로 읽어들일 수 밖에 없을 것이다. 그러나, 만약 전체 데이터에 대해 정렬 작업을 해야 한다면 이것은 복잡한 문제가 된다. 어떤 정렬 알고리즘은 데이터 전체가 메모리에 올려져 있어야 하며, 전체 데이터의 일부분만 메모리에 올려져 있는 이와 같은 경우, 그러한 알고리즘은 사용할 수 없다. 즉, 전체가 아닌, 각각의 분할에 대해 작업을 한 뒤 그것을 합쳐서 하나의 완전한 형태의 출력물을 내야 하는데, 그럴 경우 Cosequential 접근법을 택해야 한다.
또, 이런 경우 적용할 수 있는 알고리즘은 일단 분할에 대해 작업을 하고, 그것을 합쳐서 최종적인 결과를 낼 수 있는 병합 정렬(Merge Sort)이나, 힙 정렬(Heap Sort)과 같은 것이다. 이런 알고리즘은 전체가 아닌 부분적으로 작업을 할 수 있고, 바로 이런 경우에 딱 맞는 해결 방법이 된다.
물론, 정렬해야 할 데이터가 사용 가능한 메모리보다 훨씬 큰 경우, 전체 데이터가 아닌 데이터에 대한 키만을 대상 키 정렬을 시도할 수 있지만, 키와 데이터의 물리적 위치를 가진 데이터 자체가 사용 가능한 메모리보다 더 클 경우 문제는 원점으로 돌아간다.
다음과 같은 예를 들어보자. 현재 사용 가능한 메모리는 10MB이고, 정렬 대상이 되는 파일은 8000000개의 레코드를 가지고 있고, 각각의 레코드는 100 바이트의 길이이며, 각 레코드는 10 바이트의 키 필드를 가지고 있다고 하자. 이 파일의 전체 길이는 약 800MB 정도 될 것이다. 이 경우, 전체 파일을 메모리에 올려서 정렬할 수 없으며, 키만 대상으로 정렬을 하더라도 해당 테이블의 크기 역시 사용 가능한 메모리보다 훨씬 크다.
이 문제를 해결하기 위한 첫 단계로, 먼저 메모리에 올릴 수 있는 최대 분할 크기를 구해보자. 10MB의 메모리는 대략 100000개의 레코드를 읽어들일 수 있으며, 80개의 분할이 생기게 된다. 만약, 정렬 알고리즘으로 병합 정렬을 사용한다면, 최종적으로 어느 정도의 디스크 접근 비용이 발생하는가?
정렬 단계 동안,
1. 정렬과 분할을 형성하기 위해서 모든 레코드들을 메모리 안으로 읽어야 하며,
2. 정렬된 분할들을 다시 디스크로 기록해야 한다.
그리고 병합 단계 동안,
3. 합병을 위한 정렬된 분할들을 메모리로 읽어들여야 하고,
4. 정렬된 파일을 디스크로 기록해야 한다.
먼저, 10MB의 메모리는 일반적인 의미의 전체 메모리 크기를 의미하는 것이 아니라, 순수하게 입출력에 사용할 수 있는 버퍼를 의미한다. 따라서, 800MB 크기의 데이터를 모두 읽어들이는데 모두 80번의 디스크 접근이 필요하다. 즉, 80번의 탐색 시간과 10MB씩 80번 전송하는데 소모되는 시간을 계산해보면, 1 단계에서 필요한 디스크 비용을 알 수 있다.
2 단계는 1 단계와 크게 다르지 않다. 즉, 저장될 적절한 위치를 찾는 탐색시간과 데이터를 저장하는데 걸리는 시간을 생각해보면 여기서의 디스크 접근 비용도 알 수 있다.
3 단계는 병합 단계인데, 다음과 같은 의문이 떠오를 것이다. 80개로 나뉘어진 분할을 하나의 파일로 정렬하면서 합치기 위해서, 어떻게 80개의 분할을 동시에 메모리에 올릴 수 있다는 말인가? 그 대답은, 80개의 분할을 읽어들이기 위한 IO 버퍼의 재구성에 있다. 즉, 80개의 각각의 분할 전체를 한번에 읽을 수 있도록 단일한 하나의 버퍼를 유지하는게 아니라, 10MB의 IO 버퍼를 80개로 재구성하여 각각의 분할에서 데이터를 하나씩 읽어들일 수 있도록 한다. 이 경우, 하나의 분할을 완전히 읽어들이기 위해서는 80번의 접근이 필요하다. 왜냐하면, 하나의 분할은 10MB 크기를 가지고 있기 때문에, 이것을 1 / 80 크기로 분할한 버퍼를 사용해 하나의 분할을 완전히 읽어들이기 위해서는 80번의 디스크 탐색이 필요하기 때문이다. 즉, 전체 데이터를 완전히 읽어들이기 위해서는 하나의 분할을 완전히 읽어들이는데 필요한 80번의 디스크 탐색 * 80개의 분할 = 6400번의 디스크 탐색이 필요하다.
4 단계에서는 출력 버퍼의 크기를 알 수 있다면, 전체 데이털르 전송하기 위한 디스크 비용이 어느 정도인지 쉽게 계산할 수 있다.
그렇다면, 디스크 비용을 좀 더 절약할 수 있는, 즉 성능을 향샹시키는 방법은 없을까? 사용 가능한 메모리를 늘린다면 당연히 디스크 탐색을 훨씬 줄일 수 있으며, 이것은 가장 확실한 해결 방법이다. 또, IO 채널을 증가하는 것도 디스크 접근 비용을 줄여주기 때문에, 실질적인 성능 향상을 기대할 수 있다.
그러나 이러한 방법들은 하드웨어적인 지원을 필요로 한다. 다른 방법으로, 소프트웨어적으로 다단계 병합(multiple step merge)을 통해 디스크 탐색 수를 줄일 수 있다. 위의 문제로 다시 돌아가보자. 만일, 80개의 단일 분할이 아니라, 10 분할씩 8개의 집합으로 구성된 2 패스 분할이라면 어떨까? 이러한 2 패스 분할 방법은 모든 레코드를 두 번 읽어야 하는 단점이 있다. 즉, 중간 분할을 형성하기 위해 한번, 그리고 마지막으로 정렬된 파일을 형성하기 위해 다시 한번 더 읽어야 한다. 그러나, 각 병합 단계에서 좀 더 많은 메모리를 사용할 수 있기 때문에, 디스크 접근 비용을 감소시킬 수 있다.
먼저, 최초의 분할이 80개인 것은 변함이 없다. 2 패스 병합을 선택할 경우, 한번에 80개의 분할을 모두 병합하는게 아니라, 두 단계로 나누어서 병합하는 과정을 거친다. 위의 경우 10 분할씩 8개의 집합을 만드는데, 먼저 10개의 분할을 먼저 가져온다. IO 버퍼는 이 10개를 동시에 읽어들여서 하나의 출력을 만들어야 하기 때문에, 10개의 버퍼로 재구성되어야 하며, 버퍼 하나당 크기는 1MB가 될 것이다. 따라서, 위의 경우와 마찬가지로 가져온 10개의 분할은 그 크기가 각각 10MB, 입력 버퍼는 10개로 한번에 각 분할에서 하나의 데이터를 읽어들인다. 즉, 각각의 분할을 완전히 읽어들이기 위해 필요한 10번의 디스크 탑색 * 10개의 분할 = 100번의 디스크 탑색이 필요하며, 이 분할 집합은 8개가 존재하기 때문에 필요한 첫 번째 병합 단계에서 필요한 디스크 탐색은 총 800번이 된다. 결과물로서의 분할 각각은 100MB가 된다.
두 번째 병합 단계에서는, 8개의 분할 집합을 대상으로 작업하게 되는데, 이 분할을 읽어들이기 위해 IO 버퍼는 8개로 구성되며, 각 크기는 사용 가능한 메모리인 10MB의 1 / 8 크기가 된다. 전 단계와 마찬가지로, 하나의 100MB로 구성된 분할을 완전히 읽어들이기 위해서 분할 당 80번의 디스크 탐색이 필요하며, 이런 분할이 8개 존재하기 떄문에 모두 640번의 디스크 탐색이 필요하다.
결과적으로, 이 두 단계의 디스크 탐색 횟수를 모두 더해보면 800 + 640 = 1440번의 디스크 탐색이 필요하며, 이것은 80개의 단일한 분할을 한번에 병합하는 것보다 훨씬 적은 횟수이다.
이러한 멀티 패스 병합의 핵심은, 결국 사용 가능한 버퍼의 크기를 늘려서 디스크로의 접근 횟수를 최소한으로 줄이는데 있다. 그렇다면, 병합의 횟수를 2 패스가 아니라 3 패스, 4 패스로 늘리면 더 성능을 향상시킬 여지가 있을까? 일반적으로, 패스의 수를 늘릴 수록 처리해야 하는 중간 단계 데이터가 늘어난다. 즉, 이 데이터들의 전송 시간이 디스크 탐색 시간과 회전 지연 시간보다 더 커질 수 있기 때문에 패스를 늘린다고 언제나 성능 향상 효과를 볼 수 있는 것은 아니다.
Reference
Michael J. Folk, Bill Zoellick, Greg Riccardi, File Structure, Addison Wesley
또, 이런 경우 적용할 수 있는 알고리즘은 일단 분할에 대해 작업을 하고, 그것을 합쳐서 최종적인 결과를 낼 수 있는 병합 정렬(Merge Sort)이나, 힙 정렬(Heap Sort)과 같은 것이다. 이런 알고리즘은 전체가 아닌 부분적으로 작업을 할 수 있고, 바로 이런 경우에 딱 맞는 해결 방법이 된다.
물론, 정렬해야 할 데이터가 사용 가능한 메모리보다 훨씬 큰 경우, 전체 데이터가 아닌 데이터에 대한 키만을 대상 키 정렬을 시도할 수 있지만, 키와 데이터의 물리적 위치를 가진 데이터 자체가 사용 가능한 메모리보다 더 클 경우 문제는 원점으로 돌아간다.
다음과 같은 예를 들어보자. 현재 사용 가능한 메모리는 10MB이고, 정렬 대상이 되는 파일은 8000000개의 레코드를 가지고 있고, 각각의 레코드는 100 바이트의 길이이며, 각 레코드는 10 바이트의 키 필드를 가지고 있다고 하자. 이 파일의 전체 길이는 약 800MB 정도 될 것이다. 이 경우, 전체 파일을 메모리에 올려서 정렬할 수 없으며, 키만 대상으로 정렬을 하더라도 해당 테이블의 크기 역시 사용 가능한 메모리보다 훨씬 크다.
이 문제를 해결하기 위한 첫 단계로, 먼저 메모리에 올릴 수 있는 최대 분할 크기를 구해보자. 10MB의 메모리는 대략 100000개의 레코드를 읽어들일 수 있으며, 80개의 분할이 생기게 된다. 만약, 정렬 알고리즘으로 병합 정렬을 사용한다면, 최종적으로 어느 정도의 디스크 접근 비용이 발생하는가?
정렬 단계 동안,
1. 정렬과 분할을 형성하기 위해서 모든 레코드들을 메모리 안으로 읽어야 하며,
2. 정렬된 분할들을 다시 디스크로 기록해야 한다.
그리고 병합 단계 동안,
3. 합병을 위한 정렬된 분할들을 메모리로 읽어들여야 하고,
4. 정렬된 파일을 디스크로 기록해야 한다.
먼저, 10MB의 메모리는 일반적인 의미의 전체 메모리 크기를 의미하는 것이 아니라, 순수하게 입출력에 사용할 수 있는 버퍼를 의미한다. 따라서, 800MB 크기의 데이터를 모두 읽어들이는데 모두 80번의 디스크 접근이 필요하다. 즉, 80번의 탐색 시간과 10MB씩 80번 전송하는데 소모되는 시간을 계산해보면, 1 단계에서 필요한 디스크 비용을 알 수 있다.
2 단계는 1 단계와 크게 다르지 않다. 즉, 저장될 적절한 위치를 찾는 탐색시간과 데이터를 저장하는데 걸리는 시간을 생각해보면 여기서의 디스크 접근 비용도 알 수 있다.
3 단계는 병합 단계인데, 다음과 같은 의문이 떠오를 것이다. 80개로 나뉘어진 분할을 하나의 파일로 정렬하면서 합치기 위해서, 어떻게 80개의 분할을 동시에 메모리에 올릴 수 있다는 말인가? 그 대답은, 80개의 분할을 읽어들이기 위한 IO 버퍼의 재구성에 있다. 즉, 80개의 각각의 분할 전체를 한번에 읽을 수 있도록 단일한 하나의 버퍼를 유지하는게 아니라, 10MB의 IO 버퍼를 80개로 재구성하여 각각의 분할에서 데이터를 하나씩 읽어들일 수 있도록 한다. 이 경우, 하나의 분할을 완전히 읽어들이기 위해서는 80번의 접근이 필요하다. 왜냐하면, 하나의 분할은 10MB 크기를 가지고 있기 때문에, 이것을 1 / 80 크기로 분할한 버퍼를 사용해 하나의 분할을 완전히 읽어들이기 위해서는 80번의 디스크 탐색이 필요하기 때문이다. 즉, 전체 데이터를 완전히 읽어들이기 위해서는 하나의 분할을 완전히 읽어들이는데 필요한 80번의 디스크 탐색 * 80개의 분할 = 6400번의 디스크 탐색이 필요하다.
4 단계에서는 출력 버퍼의 크기를 알 수 있다면, 전체 데이털르 전송하기 위한 디스크 비용이 어느 정도인지 쉽게 계산할 수 있다.
그렇다면, 디스크 비용을 좀 더 절약할 수 있는, 즉 성능을 향샹시키는 방법은 없을까? 사용 가능한 메모리를 늘린다면 당연히 디스크 탐색을 훨씬 줄일 수 있으며, 이것은 가장 확실한 해결 방법이다. 또, IO 채널을 증가하는 것도 디스크 접근 비용을 줄여주기 때문에, 실질적인 성능 향상을 기대할 수 있다.
그러나 이러한 방법들은 하드웨어적인 지원을 필요로 한다. 다른 방법으로, 소프트웨어적으로 다단계 병합(multiple step merge)을 통해 디스크 탐색 수를 줄일 수 있다. 위의 문제로 다시 돌아가보자. 만일, 80개의 단일 분할이 아니라, 10 분할씩 8개의 집합으로 구성된 2 패스 분할이라면 어떨까? 이러한 2 패스 분할 방법은 모든 레코드를 두 번 읽어야 하는 단점이 있다. 즉, 중간 분할을 형성하기 위해 한번, 그리고 마지막으로 정렬된 파일을 형성하기 위해 다시 한번 더 읽어야 한다. 그러나, 각 병합 단계에서 좀 더 많은 메모리를 사용할 수 있기 때문에, 디스크 접근 비용을 감소시킬 수 있다.
먼저, 최초의 분할이 80개인 것은 변함이 없다. 2 패스 병합을 선택할 경우, 한번에 80개의 분할을 모두 병합하는게 아니라, 두 단계로 나누어서 병합하는 과정을 거친다. 위의 경우 10 분할씩 8개의 집합을 만드는데, 먼저 10개의 분할을 먼저 가져온다. IO 버퍼는 이 10개를 동시에 읽어들여서 하나의 출력을 만들어야 하기 때문에, 10개의 버퍼로 재구성되어야 하며, 버퍼 하나당 크기는 1MB가 될 것이다. 따라서, 위의 경우와 마찬가지로 가져온 10개의 분할은 그 크기가 각각 10MB, 입력 버퍼는 10개로 한번에 각 분할에서 하나의 데이터를 읽어들인다. 즉, 각각의 분할을 완전히 읽어들이기 위해 필요한 10번의 디스크 탑색 * 10개의 분할 = 100번의 디스크 탑색이 필요하며, 이 분할 집합은 8개가 존재하기 때문에 필요한 첫 번째 병합 단계에서 필요한 디스크 탐색은 총 800번이 된다. 결과물로서의 분할 각각은 100MB가 된다.
두 번째 병합 단계에서는, 8개의 분할 집합을 대상으로 작업하게 되는데, 이 분할을 읽어들이기 위해 IO 버퍼는 8개로 구성되며, 각 크기는 사용 가능한 메모리인 10MB의 1 / 8 크기가 된다. 전 단계와 마찬가지로, 하나의 100MB로 구성된 분할을 완전히 읽어들이기 위해서 분할 당 80번의 디스크 탐색이 필요하며, 이런 분할이 8개 존재하기 떄문에 모두 640번의 디스크 탐색이 필요하다.
결과적으로, 이 두 단계의 디스크 탐색 횟수를 모두 더해보면 800 + 640 = 1440번의 디스크 탐색이 필요하며, 이것은 80개의 단일한 분할을 한번에 병합하는 것보다 훨씬 적은 횟수이다.
이러한 멀티 패스 병합의 핵심은, 결국 사용 가능한 버퍼의 크기를 늘려서 디스크로의 접근 횟수를 최소한으로 줄이는데 있다. 그렇다면, 병합의 횟수를 2 패스가 아니라 3 패스, 4 패스로 늘리면 더 성능을 향상시킬 여지가 있을까? 일반적으로, 패스의 수를 늘릴 수록 처리해야 하는 중간 단계 데이터가 늘어난다. 즉, 이 데이터들의 전송 시간이 디스크 탐색 시간과 회전 지연 시간보다 더 커질 수 있기 때문에 패스를 늘린다고 언제나 성능 향상 효과를 볼 수 있는 것은 아니다.
Reference
Michael J. Folk, Bill Zoellick, Greg Riccardi, File Structure, Addison Wesley