분산 계산을 위한 알고리즘

수학 시간에 배운 분산
- 편차 제곱의 합의 평균
- 예) 1, 2, 3의 분산을 구하라
- 평균 = (1 + 2 + 3) / 3 = 2
- 편차 제곱의 합 = (1-2)^2 + (2-2)^2 + (3-2)^2 = 2
- 분산 = 2 / 3 = 0.6666666666666666
위 처럼 naive한 방식으로는 1억개 데이터의 분산을 구하려면 1억개의 데이터를 리스트로 보관해야한다.
- 1억개의 Long 타입을 메모리에 저장한다면?
- 100,000,000 * 24 / 1024 / 1024 = 2286MB 를 필요로 하게 된다.
- 이는 메모리 비효율성을 야기시키고, 연산을 동시에 4개를 처리한다면 OOM이 발생할 수 있다.

OpenJDK 기준으로 Long 타입의 메모리 크기

OpenJDK의 HotSpot JVM을 기준으로 java.lang.Long 객체는 다음과 같은 메모리 구조를 가집니다.

메모리 구성:

객체 헤더 (Object Header): 12 바이트

마크 단어 (Mark Word): 8 바이트

클래스 포인터 (Class Pointer): 4 바이트 (compressed oops 사용 시)

필드 (long 값): 8 바이트

패딩 (Padding): 4 바이트

JVM은 객체 크기를 8바이트 단위로 정렬하므로, 총합이 20 바이트인 경우 4바이트의 패딩이 추가되어 24 바이트가 됩니다.

총 메모리 크기: 24 바이트

계산 방식:

객체 헤더: 12 바이트

long 필드: 8 바이트

패딩: 4 바이트

합계: 12 + 8 + 4 = 24 바이트

추가 정보:

Compressed OOPs:

64비트 JVM에서 객체 참조를 압축하여 메모리 사용량을 줄이는 기술입니다. 이를 사용하면 클래스 포인터의 크기가 줄어들어 메모리 효율이 향상됩니다.

메모리 정렬:

JVM은 객체의 메모리 정렬을 최적화하기 위해 8바이트 단위로 패딩을 추가합니다. 이는 메모리 접근 속도를 향상시키기 위한 목적입니다.

따라서 이를 해결하기 위해 Welford's Online Algorithm 을 사용한다.

웰포드의 온라인 알고리즘이란?

웰포드의 온라인 알고리즘(Welford's Online Algorithm)은 데이터 스트림을 한 번에 한 요소씩 처리하면서 평균과 분산을 효율적으로 계산할 수 있는 방법입니다.
특히, 대용량 데이터나 실시간으로 들어오는 데이터에 대해 메모리 사용량을 최소화하면서 통계 값을 업데이트할 수 있어 유용합니다.

왜 온라인 알고리즘이 필요한가?

전통적인 통계 계산 방식에서는 모든 데이터를 한 번에 메모리에 로드한 후 평균과 분산을 계산합니다.
그러나 데이터의 양이 매우 크거나 실시간으로 데이터가 유입되는 경우, 이러한 방식은 비효율적이거나 불가능할 수 있습니다. 온라인 알고리즘은 다음과 같은 장점을 제공합니다:
- 메모리 효율성: 모든 데이터를 저장할 필요 없이, 현재까지의 통계 값만 유지하면 됩니다.
- 실시간 처리: 데이터가 들어오는 즉시 통계 값을 업데이트할 수 있습니다. 단일 패스 처리: 데이터를 한 번만 읽으면 되므로 I/O 비용을 절감할 수 있습니다.

웰포드 알고리즘의 작동 원리

웰포드의 알고리즘은 새로운 데이터 포인트가 들어올 때마다 평균과 분산을 업데이트합니다.
이를 위해 다음과 같은 변수를 유지합니다:
- n: 현재까지의 데이터 포인트 수
- mean: 현재까지의 평균
- M2: 현재까지의 두 번째 중심 누적합 (분산 계산에 사용)

장점과 단점

장점
- 효율성: 시간 복잡도가 O(1)로 매우 효율적입니다.
- 안정성: 누적 오차를 최소화하여 정확한 통계 값을 제공합니다.
- 비교적 단순한 구현: 이해하고 구현하기 쉬운 알고리즘입니다.
단점
- 단일 통계만 유지: 평균과 분산만을 계산할 수 있으며, 다른 통계 값을 원할 경우 추가적인 수정이 필요합니다.
- 정확도 제한: 매우 큰 데이터 집합에서는 부동 소수점 연산의 한계로 인해 정확도에 영향을 받을 수 있습니다.

분산 계산을 위한 알고리즘

수학 시간에 배운 분산

편차 제곱의 합의 평균
예) 1, 2, 3의 분산을 구하라
평균 = (1 + 2 + 3) / 3 = 2
편차 제곱의 합 = (1-2)^2 + (2-2)^2 + (3-2)^2 = 2
분산 = 2 / 3 = 0.6666666666666666

위 처럼 naive한 방식으로는 1억개 데이터의 분산을 구하려면 1억개의 데이터를 리스트로 보관해야한다.

1억개의 Long 타입을 메모리에 저장한다면?
100,000,000 * 24 / 1024 / 1024 = 2286MB 를 필요로 하게 된다.
이는 메모리 비효율성을 야기시키고, 연산을 동시에 4개를 처리한다면 OOM이 발생할 수 있다.

OpenJDK 기준으로 Long 타입의 메모리 크기

OpenJDK의 HotSpot JVM을 기준으로 java.lang.Long 객체는 다음과 같은 메모리 구조를 가집니다.

메모리 구성:
- 객체 헤더 (Object Header): 12 바이트
- 마크 단어 (Mark Word): 8 바이트
- 클래스 포인터 (Class Pointer): 4 바이트 (compressed oops 사용 시)
- 필드 (long 값): 8 바이트
- 패딩 (Padding): 4 바이트
JVM은 객체 크기를 8바이트 단위로 정렬하므로, 총합이 20 바이트인 경우 4바이트의 패딩이 추가되어 24 바이트가 됩니다.
총 메모리 크기: 24 바이트
계산 방식:
- 객체 헤더: 12 바이트
- long 필드: 8 바이트
- 패딩: 4 바이트
- 합계: 12 + 8 + 4 = 24 바이트
추가 정보:
- Compressed OOPs:
  
  64비트 JVM에서 객체 참조를 압축하여 메모리 사용량을 줄이는 기술입니다. 이를 사용하면 클래스 포인터의 크기가 줄어들어 메모리 효율이 향상됩니다.
- 메모리 정렬:
  
  JVM은 객체의 메모리 정렬을 최적화하기 위해 8바이트 단위로 패딩을 추가합니다. 이는 메모리 접근 속도를 향상시키기 위한 목적입니다.

따라서 이를 해결하기 위해 Welford's Online Algorithm 을 사용한다.

웰포드의 온라인 알고리즘이란?

웰포드의 온라인 알고리즘(Welford's Online Algorithm)은 데이터 스트림을 한 번에 한 요소씩 처리하면서 평균과 분산을 효율적으로 계산할 수 있는 방법입니다.

특히, 대용량 데이터나 실시간으로 들어오는 데이터에 대해 메모리 사용량을 최소화하면서 통계 값을 업데이트할 수 있어 유용합니다.

왜 온라인 알고리즘이 필요한가?

전통적인 통계 계산 방식에서는 모든 데이터를 한 번에 메모리에 로드한 후 평균과 분산을 계산합니다.

그러나 데이터의 양이 매우 크거나 실시간으로 데이터가 유입되는 경우, 이러한 방식은 비효율적이거나 불가능할 수 있습니다. 온라인 알고리즘은 다음과 같은 장점을 제공합니다:

메모리 효율성: 모든 데이터를 저장할 필요 없이, 현재까지의 통계 값만 유지하면 됩니다.
실시간 처리: 데이터가 들어오는 즉시 통계 값을 업데이트할 수 있습니다. 단일 패스 처리: 데이터를 한 번만 읽으면 되므로 I/O 비용을 절감할 수 있습니다.

웰포드 알고리즘의 작동 원리

웰포드의 알고리즘은 새로운 데이터 포인트가 들어올 때마다 평균과 분산을 업데이트합니다.

이를 위해 다음과 같은 변수를 유지합니다:

n: 현재까지의 데이터 포인트 수
mean: 현재까지의 평균
M2: 현재까지의 두 번째 중심 누적합 (분산 계산에 사용)

장점과 단점

장점

효율성: 시간 복잡도가 O(1)로 매우 효율적입니다.
안정성: 누적 오차를 최소화하여 정확한 통계 값을 제공합니다.
비교적 단순한 구현: 이해하고 구현하기 쉬운 알고리즘입니다.

단점

단일 통계만 유지: 평균과 분산만을 계산할 수 있으며, 다른 통계 값을 원할 경우 추가적인 수정이 필요합니다.
정확도 제한: 매우 큰 데이터 집합에서는 부동 소수점 연산의 한계로 인해 정확도에 영향을 받을 수 있습니다.