Go에서 Slice와 Map 확장 관련 깊은 연구

Go 언어 연구에서 배열 및 Map의 확장 전략은 흔하고 고전적인 주제입니다. 이 기사에서는 배열과 Map의 확장 전략을 요약하고 설명하는 것을 목표로 합니다.

배열 확장

Go에서 동적 배열을 슬라이스라고 합니다. 슬라이스는 유연하고 동적으로 크기가 조정되는 배열 솔루션을 제공합니다. append 함수를 사용하여 슬라이스에 요소를 추가할 때 Go는 슬라이스의 현재 용량을 기반으로 용량을 확장할지 여부를 결정합니다.

Go에서 슬라이스 확장을 위한 전략은 다음과 같습니다.

1. 먼저, 새로 요청된 용량이 이전 용량의 두 배보다 크면 최종 용량은 새로 요청된 용량이 됩니다.
2. 그렇지 않고 이전 슬라이스의 길이가 1024보다 작으면 최종 용량은 이전 용량의 두 배가 됩니다.
3. 그렇지 않고 이전 슬라이스의 길이가 1024보다 크거나 같으면 최종 용량이 새로 요청된 용량에 도달하거나 초과할 때까지 이전 용량의 1/4씩 반복적으로 증가합니다.
4. 최종 용량 계산이 오버플로되면 최종 용량은 새로 요청된 용량이 됩니다.

해시 테이블 확장

Go에서 Map은 키-값 쌍을 저장하는 데 일반적으로 사용되는 데이터 구조입니다. 해당 확장 메커니즘은 Map의 성능 및 메모리 사용량을 이해하는 데 매우 중요합니다.

Go Map에는 두 가지 유형의 확장이 있습니다.

• 두 배 확장: 키-값 쌍의 수가 현재 버킷 배열 용량의 6.5배를 초과하면 버킷이 거의 가득 찼음을 의미합니다. 이 시점에서 확장이 트리거되고 버킷 수가 두 배가 됩니다. 그 목적은 해시 충돌을 줄이고 쿼리 효율성을 개선하는 것입니다.
• 동일 크기 확장: 너무 많은 오버플로 버킷이 있지만(예: 빈번한 삽입 및 삭제로 인해 데이터가 흩어짐) 총 키-값 쌍의 수가 작으면 버킷 수는 변경되지 않습니다. 대신 데이터가 재정렬되고 중복 오버플로 버킷이 병합되며 데이터 분포가 더 조밀해져 쿼리 성능이 향상됩니다.

Map의 기본 구조

Go에서 Map의 기본 구현은 해시 맵입니다. Go 소스 코드는 다음과 같습니다.

// runtime/map.go
// Go 맵의 헤더입니다.
type hmap struct {
 count     int // 현재 해시 테이블에 있는 키-값 쌍의 수
 flags     uint8
 B         uint8  // 현재 해시 테이블에 의해 유지되는 버킷 수입니다. 버킷 수는 항상 2의 배수로 확장되므로 이 필드는 지수를 저장합니다. 즉, len(buckets) == 2^B
 noverflow uint16 // 대략적인 오버플로 버킷 수
 hash0     uint32 // 해시 시드

 buckets    unsafe.Pointer // 2^B 버킷을 저장하는 배열
 oldbuckets unsafe.Pointer // 확장 중에 이전 버킷을 저장하는 데 사용되며 크기는 버킷의 절반입니다.
 nevacuate  uintptr        // 비우기 진행 카운터(이 값보다 작은 버킷은 비워졌습니다.)

 extra *mapextra // 선택적 필드
}

// mapextra는 주로 hmap의 일부 버킷이 오버플로되었지만
// 아직 확장 임계값에 도달하지 않은 경우 오버플로 버킷을 유지 관리합니다.
type mapextra struct {
 overflow    *[]*bmap
 oldoverflow *[]*bmap

 // nextOverflow는 사용 가능한 오버플로 버킷에 대한 포인터를 보유합니다.
 nextOverflow *bmap
}

몇 가지 주요 필드 설명은 다음과 같습니다.

• count: 해시 테이블의 키-값 쌍 수를 나타냅니다.
• B: 이것은 밑수가 2인 지수로, 버킷 수를 결정하는 데 사용됩니다. 예를 들어 B = 1이면 버킷 수는 2^1 = 2이고, B = 2이면 버킷 수는 2^2 = 4입니다.
• hash0: 키의 해시 값을 계산하는 데 사용되는 요소입니다.
• buckets: 버킷 배열에 대한 포인터로, 각 버킷은 키-값 쌍을 저장하는 데 사용됩니다.
• overflow: 버킷이 더 많은 요소를 담을 수 없고 키가 이 버킷으로 해시되는 경우 요소가 오버플로 버킷에 배치되고 원래 버킷의 오버플로 필드는 오버플로 버킷을 가리킵니다(체이닝 방법).

확장 메커니즘: 두 배 확장

트리거 조건:

Map의 로드가 특정 임계값을 초과하면 두 배 확장이 트리거됩니다. 로드는 요소 수(count)를 버킷 수(2^B)로 나눈 값으로 계산됩니다. 이 비율이 6.5보다 크거나 같으면 로드가 초과된 것으로 간주됩니다.

예를 들어 B = 2이면 2^2 = 4 버킷이 있습니다. 요소 수 count가 26이면(26 / 4 = 6.5) 두 배 확장이 트리거됩니다.

소스 코드의 관련 로직은 다음과 같습니다.

// h가 맵 구조체에 대한 포인터라고 가정합니다.
if !h.flags&hashWriting && h.count > int(float64(1<<h.B)*loadFactor) {
    // 두 배 확장 로직을 트리거합니다.
}

확장 프로세스:

두 배 확장 중에 B 값이 1씩 증가하여 버킷 수가 두 배가 됩니다. 예를 들어 원래 B = 2이고 버킷이 4개인 경우 확장 후 B = 3이고 버킷이 2^3 = 8개입니다.

데이터를 마이그레이션할 때 원래 버킷의 요소가 새 버킷으로 재분배됩니다. 특히, 키의 해시 값을 기반으로 새 버킷 위치가 다시 계산됩니다.

키의 해시 값이 hash라고 가정합니다. 원래 버킷 수는 2^B1이었고 확장 후에는 2^B2가 됩니다. 그러면 데이터는 원래 버킷(hash % 2^B1)에서 새 버킷(hash % 2^B2)으로 마이그레이션됩니다.

예:

• 해시 값이 10이고 B = 2(4개 버킷)이면 10 % 4 = 2이므로 데이터는 인덱스 2의 버킷에 저장됩니다.
• B = 3(8개 버킷)으로 확장한 후 10 % 8 = 2이면 데이터는 여전히 인덱스 2의 버킷에 있습니다. 그러나 이제 버킷 분포가 더 희소해져 해시 충돌 확률이 줄어듭니다.

확장 메커니즘: 동일 크기 확장

트리거 조건:

많은 키가 삭제되어 오버플로 버킷이 너무 많으면 동일 크기 확장이 트리거될 수 있습니다. 여기서 오버플로 버킷은 버킷이 8개의 요소로 가득 차고 새 요소가 오버플로 버킷에 저장되는 상황을 의미합니다. 오버플로 버킷은 총 버킷 수에 포함되지 않습니다.

오버플로 버킷 수가 2^B보다 크거나 같으면 동일 크기 확장이 트리거될 수 있습니다. 그러나 해시 충돌로 인해 오버플로 버킷이 과도하고 로드가 초과되면 두 배 확장이 먼저 트리거됩니다.

소스 코드의 관련 로직은 다음과 같습니다.

// h가 맵 구조체에 대한 포인터라고 가정합니다. noverflow는 오버플로 버킷 수입니다.
if noverflow >= uint16(1)<<(h.B) {
    if h.B < 15 {
        // 동일 크기 또는 두 배 확장 로직을 트리거할 수 있습니다.
    }
}

확장 프로세스:

동일 크기 확장은 주로 버킷을 구성하여 빈 공간을 제거합니다. 새 버킷 배열이 생성되고 이전 버킷 배열을 순회하여 비어 있지 않은 키-값 쌍을 새 배열에 다시 삽입하고 원래 오버플로 버킷을 해제합니다.

해시 요소, B 값 및 해시 알고리즘은 변경되지 않으므로 새 버킷의 키-값 쌍 위치는 이전과 동일한 방식으로 계산됩니다. 빈 저장 공간만 제거되어 키-값 쌍이 더 조밀해지고 후속 작업의 효율성이 향상됩니다.

---

Go 프로젝트 호스팅을 위한 최고의 선택, Leapcell입니다.

Leapcell은 웹 호스팅, 비동기 작업 및 Redis를 위한 차세대 서버리스 플랫폼입니다.

다국어 지원

• Node.js, Python, Go 또는 Rust로 개발합니다.

무료로 무제한 프로젝트 배포

• 사용량에 대해서만 지불 - 요청 없음, 요금 없음.

탁월한 비용 효율성

• 유휴 요금 없이 사용한 만큼 지불합니다.
• 예: $25는 평균 응답 시간 60ms에서 694만 건의 요청을 지원합니다.

간소화된 개발자 경험

• 간편한 설정을 위한 직관적인 UI.
• 완전 자동화된 CI/CD 파이프라인 및 GitOps 통합.
• 실행 가능한 통찰력을 위한 실시간 지표 및 로깅.

간편한 확장성 및 고성능

• 쉬운 동시성 처리를 위한 자동 확장.
• 운영 오버헤드가 없으므로 구축에만 집중할 수 있습니다.

설명서에서 자세히 알아보세요!

X에서 저희를 팔로우하세요: @LeapcellHQ