분산 계산을 위한 알고리즘

• 수학 시간에 배운 분산

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