외부 정렬 문제는 컴퓨터 과학 강좌에서 잘 알려진 주제이며 교육 도구로 자주 사용됩니다. 그러나 필요한 최적화 작업은 고사하고 특정 기술 시나리오에 대한 코드에서 이 문제에 대한 솔루션을 실제로 구현한 사람을 만나는 경우는 거의 없습니다. 해커톤 중 이러한 문제에 직면하면서 이 글을 쓰게 되었습니다.
해커톤 과제는 다음과 같습니다.
IPv4 주소가 포함된 간단한 텍스트 파일이 있습니다. 한 줄은 한 줄씩 하나의 주소입니다.
145.67.23.4 8.34.5.23 89.54.3.124 89.54.3.124 3.45.71.5 ...
파일 크기는 무제한이며 수십, 수백 기가바이트를 차지할 수 있습니다.
가능한 적은 메모리와 시간을 사용하여 이 파일의 고유 주소 수를 계산해야 합니다. 이 문제를 해결하기 위한 "순진한" 알고리즘이 있습니다(한 줄씩 읽고, HashSet에 줄을 넣습니다). 구현이 이 순진한 알고리즘보다 더 복잡하고 빠르면 더 좋습니다.
파싱을 위해 80억 줄의 120GB 파일이 제출되었습니다.
프로그램 실행 속도에 대한 특별한 요구 사항은 없었습니다. 그러나 온라인에서 해당 주제에 대해 사용 가능한 정보를 신속하게 검토한 후 표준 하드웨어(예: 가정용 PC)에 허용되는 실행 시간은 약 1시간 이하라는 결론을 내렸습니다.
분명한 이유로 시스템에 사용 가능한 메모리가 최소 128GB가 아니면 파일 전체를 읽고 처리할 수 없습니다. 그런데 청크로 작업하고 병합하는 것은 불가피한가요?
외부 병합을 구현하는 것이 불편하다면 먼저 최적과는 거리가 멀지만 허용되는 대체 솔루션에 익숙해지는 것이 좋습니다.
2^32비트 비트맵을 만듭니다. uint64에는 64비트가 포함되어 있으므로 이는 uint64 배열입니다.
각 IP에 대해:
장점:
매우 빠른 고유성 감지: 비트 O(1) 설정, 확인할 필요 없이 그냥 설정하기만 하면 됩니다.
해싱, 정렬 등에 대한 오버헤드가 없습니다.
단점:
막대한 메모리 소비(오버헤드를 고려하지 않고 전체 IPv4 공간에 512MB).
파일이 크지만 전체 IPv4 공간보다 작은 경우 시간 측면에서는 여전히 유리할 수 있지만 메모리 측면에서는 항상 합리적인 것은 아닙니다.
package main
import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
"math/bits"
)
// Parse IP address "A.B.C.D" => uint32 number
func ipToUint32(ipStr string) (uint32, error) {
parts := strings.Split(ipStr, ".")
if len(parts) != 4 {
return 0, fmt.Errorf("invalid IP format")
}
var ipNum uint32
for i := 0; i < 4; i++ {
val, err := strconv.Atoi(parts[i])
if err != nil || val < 0 || val > 255 {
return 0, fmt.Errorf("invalid IP octet: %v", parts[i])
}
ipNum = (ipNum << 8) | uint32(val)
}
return ipNum, nil
}
func popcount64(x uint64) int {
return bits.OnesCount64(x)
}
func main() {
filePath := "ips.txt"
file, err := os.Open(filePath)
if err != nil {
fmt.Printf("Error opening file: %v\n", err)
return
}
defer file.Close()
// IPv4 space size: 2^32 = 4,294,967,296
// We need 2^32 bits, that is (2^32)/64 64-bit words
totalBits := uint64(1) << 32 // 2^32
arraySize := totalBits / 64 //how many uint64 do we need
bitset := make([]uint64, arraySize)
scanner := bufio.NewScanner(file)
for scanner.Scan() {
ipStr := scanner.Text()
ipNum, err := ipToUint32(ipStr)
if err != nil {
fmt.Printf("Incorrect IP: %s\n", ipStr)
continue
}
idx := ipNum / 64
bit := ipNum % 64
mask := uint64(1) << bit
// Setting the bit
bitset[idx] |= mask
}
if err := scanner.Err(); err != nil {
fmt.Printf("Error reading file: %v\n", err)
return
}
count := 0
for _, val := range bitset {
count += bits.OnesCount64(val)
}
fmt.Printf("Number of unique IP addresses: %d\n", count)
}
이 접근 방식은 간단하고 안정적이므로 대안이 없을 때 실행 가능한 옵션입니다. 그러나 프로덕션 환경에서는 특히 최적의 성능을 달성하려는 경우 보다 효율적인 솔루션을 개발하는 것이 필수적입니다.
따라서 우리의 접근 방식에는 청킹, 내부 병합 정렬, 중복 제거가 포함됩니다.
파일은 수백 메가바이트 또는 몇 기가바이트와 같이 비교적 작은 부분(청크)으로 분할됩니다. 각 청크에 대해:
청크를 읽고 IP 주소를 숫자로 구문 분석하여 메모리의 임시 배열에 저장하는 고루틴(또는 고루틴 풀)이 시작됩니다.
그런 다음 이 배열이 정렬되고(예: 표준 sort.Slice를 사용하여) 중복 항목을 제거한 후 결과가 임시 파일에 기록됩니다.
각 부분은 독립적으로 처리될 수 있으므로 CPU 코어가 여러 개이고 디스크 대역폭이 충분하다면 이러한 핸들러 여러 개를 병렬로 실행할 수 있습니다. 이를 통해 리소스를 최대한 효율적으로 사용할 수 있습니다.
모든 청크가 정렬되어 임시 파일에 기록되면 이러한 정렬된 목록을 단일 정렬 스트림으로 병합하여 중복 항목을 제거해야 합니다.
외부 정렬 과정과 유사하게 여러 개의 임시 파일을 그룹으로 나누어 병렬로 병합하고 점차적으로 파일 수를 줄여 병합을 병렬화할 수 있습니다.
이렇게 하면 정렬되고 중복이 제거된 하나의 큰 출력 스트림이 남고, 여기에서 총 고유 IP 수를 계산할 수 있습니다.
병렬화의 장점:
다중 CPU 코어 사용:
매우 큰 배열을 단일 스레드로 정렬하면 속도가 느려질 수 있지만, 멀티 코어 프로세서가 있으면 여러 청크를 병렬로 정렬하여 프로세스 속도를 몇 배로 높일 수 있습니다.
로드 밸런싱:
청크 크기를 현명하게 선택하면 각 청크를 거의 동일한 시간 내에 처리할 수 있습니다. 일부 청크가 더 크거나 작거나 더 복잡한 경우 여러 고루틴에 걸쳐 해당 처리를 동적으로 배포할 수 있습니다.
병렬화를 사용하면 한 청크를 읽는 동안 다른 청크를 정렬하거나 쓸 수 있어 유휴 시간이 줄어듭니다.
외부 정렬은 자연스럽게 파일 청크를 통한 병렬화에 적합합니다. 이 접근 방식을 사용하면 멀티 코어 프로세서를 효율적으로 사용할 수 있고 IO 병목 현상이 최소화되므로 단일 스레드 접근 방식에 비해 훨씬 더 빠른 정렬 및 중복 제거가 가능합니다. 워크로드를 효과적으로 분산함으로써 대용량 데이터세트를 처리할 때도 높은 성능을 발휘할 수 있습니다.
중요 고려 사항:
파일을 한 줄씩 읽는 동안 총 줄 수도 계산할 수 있습니다. 프로세스가 진행되는 동안 우리는 청크 분할과 병합의 두 단계로 중복 제거를 수행합니다. 결과적으로 최종 출력 파일의 행 수를 계산할 필요가 없습니다. 대신 총 고유 줄 수는 다음과 같이 계산할 수 있습니다.
finalCount := totalLines - (DeletedInChunks DeletedInMerge)
이 접근 방식은 중복 작업을 방지하고 각 중복 제거 단계에서 삭제 항목을 추적하여 계산을 더욱 효율적으로 만듭니다. 이를 통해 많은 시간을 절약할 수 있습니다.
한 가지 더:
방대한 양의 데이터에서는 작은 성능 향상도 중요하므로 직접 작성한 문자열 가속 아날로그를 사용하는 것이 좋습니다.Slice()
145.67.23.4 8.34.5.23 89.54.3.124 89.54.3.124 3.45.71.5 ...
또한 병렬 처리를 관리하기 위해 작업자 템플릿이 채택되었으며 스레드 수를 구성할 수 있습니다. 기본적으로 스레드 수는 runtime.NumCPU()로 설정되어 프로그램이 사용 가능한 모든 CPU 코어를 효율적으로 활용할 수 있습니다. 이 접근 방식은 최적의 리소스 사용을 보장하는 동시에 환경의 특정 요구 사항이나 제한 사항에 따라 스레드 수를 조정할 수 있는 유연성을 제공합니다.
중요 사항: 멀티스레딩을 사용할 때 경합 상태를 방지하고 프로그램의 정확성을 보장하기 위해 공유 데이터를 보호하는 것이 중요합니다. 이는 구현의 특정 요구 사항에 따라 뮤텍스, 채널(Go에서) 또는 기타 동시성이 안전한 기술과 같은 동기화 메커니즘을 사용하여 달성할 수 있습니다.
이러한 아이디어를 구현한 결과, M.2 SSD와 결합된 Ryzen 7700 프로세서에서 실행될 때 약 40분 만에 작업을 완료하는 코드가 탄생했습니다.
데이터의 양과 그에 따른 중요한 디스크 작업의 존재 여부를 기준으로 다음 고려 사항은 압축 사용이었습니다. 압축을 위해 Brotli 알고리즘이 선택되었습니다. 높은 압축률과 효율적인 압축 해제 덕분에 디스크 IO 오버헤드를 줄이는 동시에 중간 저장 및 처리 중에 우수한 성능을 유지하는 데 적합한 선택입니다.
다음은 Brotli를 사용한 청킹의 예입니다.
package main
import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
"math/bits"
)
// Parse IP address "A.B.C.D" => uint32 number
func ipToUint32(ipStr string) (uint32, error) {
parts := strings.Split(ipStr, ".")
if len(parts) != 4 {
return 0, fmt.Errorf("invalid IP format")
}
var ipNum uint32
for i := 0; i < 4; i++ {
val, err := strconv.Atoi(parts[i])
if err != nil || val < 0 || val > 255 {
return 0, fmt.Errorf("invalid IP octet: %v", parts[i])
}
ipNum = (ipNum << 8) | uint32(val)
}
return ipNum, nil
}
func popcount64(x uint64) int {
return bits.OnesCount64(x)
}
func main() {
filePath := "ips.txt"
file, err := os.Open(filePath)
if err != nil {
fmt.Printf("Error opening file: %v\n", err)
return
}
defer file.Close()
// IPv4 space size: 2^32 = 4,294,967,296
// We need 2^32 bits, that is (2^32)/64 64-bit words
totalBits := uint64(1) << 32 // 2^32
arraySize := totalBits / 64 //how many uint64 do we need
bitset := make([]uint64, arraySize)
scanner := bufio.NewScanner(file)
for scanner.Scan() {
ipStr := scanner.Text()
ipNum, err := ipToUint32(ipStr)
if err != nil {
fmt.Printf("Incorrect IP: %s\n", ipStr)
continue
}
idx := ipNum / 64
bit := ipNum % 64
mask := uint64(1) << bit
// Setting the bit
bitset[idx] |= mask
}
if err := scanner.Err(); err != nil {
fmt.Printf("Error reading file: %v\n", err)
return
}
count := 0
for _, val := range bitset {
count += bits.OnesCount64(val)
}
fmt.Printf("Number of unique IP addresses: %d\n", count)
}
압축의 효율성은 논쟁의 여지가 있으며 솔루션이 사용되는 조건에 따라 크게 달라집니다. 압축률이 높으면 디스크 공간 사용량이 줄어들지만 비례적으로 전체 실행 시간이 늘어납니다. 느린 HDD에서는 디스크 I/O가 병목 현상을 일으키므로 압축을 통해 속도가 크게 향상될 수 있습니다. 반대로 빠른 SSD에서는 압축으로 인해 실행 시간이 느려질 수 있습니다.
M.2 SSD가 탑재된 시스템에서 실시한 테스트에서는 압축 시 성능 향상이 나타나지 않았습니다. 그 결과 결국 포기하기로 결정했습니다. 그러나 코드가 복잡해지고 잠재적으로 가독성이 떨어질 위험이 있는 경우 구성 가능한 플래그로 제어되는 압축을 선택적 기능으로 구현할 수 있습니다.
추가적인 최적화를 추구하면서 우리는 솔루션의 바이너리 변환에 관심을 돌렸습니다. 텍스트 기반 IP 주소가 숫자 해시로 변환되면 이후의 모든 작업을 바이너리 형식으로 수행할 수 있습니다.
145.67.23.4 8.34.5.23 89.54.3.124 89.54.3.124 3.45.71.5 ...
바이너리 형식의 장점
각 숫자는 고정된 크기를 차지합니다(예: uint32 = 4바이트).
1백만 개의 IP 주소의 경우 파일 크기는 ~4MB에 불과합니다.
문자열을 구문 분석할 필요가 없으므로 읽기 및 쓰기 작업 속도가 빨라집니다.
일관적인 바이트 순서(LittleEndian 또는 BigEndian)를 사용하면 다양한 플랫폼에서 파일을 읽을 수 있습니다.
결론
데이터를 이진 형식으로 저장하는 것이 숫자를 쓰고 읽는 데 더 효율적인 방법입니다. 완전한 최적화를 위해 데이터 쓰기 및 읽기 프로세스를 모두 바이너리 형식으로 변환합니다. 쓰기에는 Binary.Write를 사용하고 읽기에는 Binary.Read를 사용하세요.
이진 형식으로 작업하는 processChunk 함수의 모습은 다음과 같습니다.
package main
import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
"math/bits"
)
// Parse IP address "A.B.C.D" => uint32 number
func ipToUint32(ipStr string) (uint32, error) {
parts := strings.Split(ipStr, ".")
if len(parts) != 4 {
return 0, fmt.Errorf("invalid IP format")
}
var ipNum uint32
for i := 0; i < 4; i++ {
val, err := strconv.Atoi(parts[i])
if err != nil || val < 0 || val > 255 {
return 0, fmt.Errorf("invalid IP octet: %v", parts[i])
}
ipNum = (ipNum << 8) | uint32(val)
}
return ipNum, nil
}
func popcount64(x uint64) int {
return bits.OnesCount64(x)
}
func main() {
filePath := "ips.txt"
file, err := os.Open(filePath)
if err != nil {
fmt.Printf("Error opening file: %v\n", err)
return
}
defer file.Close()
// IPv4 space size: 2^32 = 4,294,967,296
// We need 2^32 bits, that is (2^32)/64 64-bit words
totalBits := uint64(1) << 32 // 2^32
arraySize := totalBits / 64 //how many uint64 do we need
bitset := make([]uint64, arraySize)
scanner := bufio.NewScanner(file)
for scanner.Scan() {
ipStr := scanner.Text()
ipNum, err := ipToUint32(ipStr)
if err != nil {
fmt.Printf("Incorrect IP: %s\n", ipStr)
continue
}
idx := ipNum / 64
bit := ipNum % 64
mask := uint64(1) << bit
// Setting the bit
bitset[idx] |= mask
}
if err := scanner.Err(); err != nil {
fmt.Printf("Error reading file: %v\n", err)
return
}
count := 0
for _, val := range bitset {
count += bits.OnesCount64(val)
}
fmt.Printf("Number of unique IP addresses: %d\n", count)
}
뭐야?! 많이 느려졌습니다!!
바이너리 형식에서는 작동 속도가 느려졌습니다. 1억 줄(IP 주소)이 포함된 파일은 바이너리 형식으로 처리되는 데 4.5분, 텍스트에서는 25초가 걸립니다. 청크 크기와 작업자 수가 동일합니다. 왜요?
바이너리 형식으로 작업하면 텍스트 형식보다 속도가 느려질 수 있습니다
바이너리 형식을 사용하면 바이너리.읽기 및 바이너리.쓰기 작동 방식의 세부 사항과 구현 시 잠재적인 비효율성으로 인해 텍스트 형식보다 속도가 느려질 수 있습니다. 이런 일이 발생할 수 있는 주요 이유는 다음과 같습니다.
I/O 작업
행 읽기에 최적화된 bufio.Scanner를 사용하여 더 큰 데이터 블록으로 작업합니다.
전체 줄을 읽고 구문 분석하므로 소규모 변환 작업에 더 효율적일 수 있습니다.
binary.Read는 한 번에 4바이트를 읽으므로 소규모 I/O 작업이 더 자주 발생합니다.
바이너리에 대한 빈번한 호출. 사용자와 시스템 공간 간 전환으로 인해 오버헤드가 증가합니다.
해결책: 여러 숫자를 한 번에 읽으려면 버퍼를 사용하세요.
func fastSplit(s string) []string {
n := 1
c := DelimiterByte
for i := 0; i < len(s); i++ {
if s[i] == c {
n++
}
}
out := make([]string, n)
count := 0
begin := 0
length := len(s) - 1
for i := 0; i <= length; i++ {
if s[i] == c {
out[count] = s[begin:i]
count++
begin = i + 1
}
}
out[count] = s[begin : length+1]
return out
}
버퍼링이 성능을 향상시키는 이유는 무엇입니까?
I/O 작업 감소:
각 숫자를 디스크에 직접 쓰는 대신 데이터가 버퍼에 축적되어 더 큰 블록에 기록됩니다.
오버헤드 감소:
각 디스크 쓰기 작업은 프로세스와 운영 체제 간의 컨텍스트 전환으로 인해 오버헤드를 발생시킵니다. 버퍼링을 사용하면 이러한 통화 횟수가 줄어듭니다.
또한 바이너리 다상 병합을 위한 코드도 제시합니다:
145.67.23.4 8.34.5.23 89.54.3.124 89.54.3.124 3.45.71.5 ...
결과는 환상적입니다. 80억 줄이 있는 110Gb 파일의 경우 14분!
훌륭한 결과네요! 80억 줄이 포함된 110GB 파일을 14분 만에 처리하는 것은 정말 인상적입니다. 다음의 힘을 보여줍니다:
라인 단위나 값 단위가 아닌 메모리에서 대량의 데이터를 처리함으로써 종종 병목 현상이 발생하는 I/O 작업 수를 대폭 줄일 수 있습니다.
바이너리 읽기 및 쓰기로 전환하면 구문 분석 오버헤드가 최소화되고 중간 데이터 크기가 줄어들며 메모리 효율성이 향상됩니다.
중복 제거 및 정렬을 위해 메모리 효율적인 알고리즘을 사용하면 CPU 주기를 효과적으로 활용할 수 있습니다.
고루틴과 채널을 활용하여 작업자 간 워크로드를 병렬화하면 CPU와 디스크 사용률의 균형이 유지됩니다.
마지막으로 최종 솔루션의 전체 코드는 다음과 같습니다. 자유롭게 사용하고 필요에 맞게 조정하세요!
Gophers를 위한 외부 병합 솔루션
행운을 빌어요!
위 내용은 외부 병합 문제 - Gophers를 위한 완벽한 가이드의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
