HyperLogLog 데이터 구조

매일 접속한 unique 사용자들을 어떻게 알 수 있을까? (google analytics 무시)

수백만 명이 접속해 있다면 정확하진 않더라도 n 명 접속 중을 빠르게 표시할 수 있는 자료 구조가 있을까?

해쉬맵을 통해 모든 유저를 저장하면, 서버 메모리보다 커지지 않을까 등을 생각하다가

HyperLogLog 데이터 구조란 것을 알게 되었다. (다른 방법도 많을 것이다)

https://www.youtube.com/watch?v=lJYufx0bfpw&t=479s

 

HyperLogLog

추정치를 구하기 때문에 정확한 값을 원하면 옳지 않다.

이름이 왜 하이퍼로그로그 일까?

먼저, "LogLog"는 알고리즘이 고유한 요소들을 (유니크) 효율적으로 계산하기 위해 log 함수들을 사용함으로

셀 수 있는 요소들의 수에 따라 대수적으로 증가하는 메모리 사용량을 달성한 데서 유래한다고 한다.

 

쉽게 말해, 집합 안에서 다른 요소들, 유니크한 요소들을 세는 데에 로그 함수를 사용한다.

집합에 포함된 요소들의 숫자가 증가해도, 메모리 양이 그 숫자에 따라 대수적(매우 천천히) 증가한다.

HyperLogLog는 로그로그 알고리즘의 개선/확장 버전이다.

 

unique 한 사용자들이 몇 명 있는지를 알고 싶을 때 사용할 수 있는 로깅 툴도 많고 하겠지만

이걸 데이터 구조에 저장해서 빠르게 구하고 싶을 때, set 나 hashmap을 이용할 수도 있겠지만,

 

Set에서 고유한 유저 ID를 저장한다고 하면 (ex, IP 주소) 포인터를 저장하는 일이므로, 8byte * N을 저장하게 된다.

(백만 명이면 8백만 바이트 = 8MB, 그렇게 크진 않지만 각 아이템마다 고유한 유저의 클릭 총횟수를 알고 싶다면?)

(HashMap 도 비슷한 메모리)

 

HLL (HyperLogLog) 메모리 사용량?

고유 요소의 수를 추정한다고 했다. (약 2% 오류가 있음)

정밀도에 따라 다르겠지만, 2^p 개의 레지스터를 사용해 kb 단위로 저장할 수 있다.

 

이 부분은 수학이라 그냥 코드로 테스트 해볼 정도의 지식만 공부했는데, 아래 논문을 읽어보면 좋다.

"Better with fewer bits: Improving the performance of cardinality estimation of large data streams - Qingjun Xiao, You Zhou, Shigang Chen"

http://cse.seu.edu.cn/PersonalPage/csqjxiao/csqjxiao_files/papers/INFOCOM17.pdf

 

사용법 (Go)

Redis도 hyperloglog 를 지원해서 hll 명령어 등을 이용하면 쉽게 사용할 수 있다.

// Redis에서 키를 hll로
hllKey := fmt.Sprintf("hll:marker:%s:%d", time.Now().Format("20060102"), markerID)
_, err = RedisStore.Conn().PFAdd(context.Background(), hllKey, user).Result()
if err != nil {
    log.Printf("Error adding visitor to HyperLogLog: %v", err)
    return
}

이 글에선 직접 구현된 라이브러리를 통해 이용할 것이다.

Go언어 기준, axiomhq/hyperloglog 가 제일 효율적으로 구현된 듯 하다.

// Sketch is a HyperLogLog data-structure for the count-distinct problem,
// approximating the number of distinct elements in a multiset.
type Sketch struct {
	p          uint8
	b          uint8
	m          uint32
	alpha      float64
	tmpSet     set
	sparseList *compressedList
	regs       *registers
}

// newSketch returns a HyperLogLog Sketch with 2^precision registers
func newSketch(precision uint8, sparse bool) (*Sketch, error) {
	if precision < 4 || precision > 18 {
		return nil, fmt.Errorf("p has to be >= 4 and <= 18")
	}
	m := uint32(math.Pow(2, float64(precision)))
	s := &Sketch{
		m:     m,
		p:     precision,
		alpha: alpha(float64(m)),
	}
	if sparse {
		s.tmpSet = set{}
		s.sparseList = newCompressedList()
	} else {
		s.regs = newRegisters(m)
	}
	return s, nil
}

type compressedList struct {
	count uint32
	last  uint32
	b     []uint8
}

구현된 코드를 보면, Sketch struct가 있고, sparse (메모리 사용 최적화), 임시 set,

해싱 (이 구현에선 metro 해쉬를 쓰는데 이유는 잘 모르겠다) 등을 보면 된다.

 

해볼 것은, 내 서버 웹사이트에 있는 아이템마다 고유한 유저가 얼마나 접근했는지 (매일) 알고 싶었다.

단순히, 한 유저가 n번 클릭해서 조회수를 높이는 것이 아닌 X-Forwarded-For과 같은 값에서 얻은 IP를 통해

고유한 유저의 방문 수를 구해보자.

 

우선 각 아이템마다 Sketch를 저장해야 하므로 concurrent-safe 한 맵을 하나 만든다. (xxh3 + csmap)

var SketchedLocations = csmap.Create(
	csmap.WithShardCount[int, *hyperloglog.Sketch](64),
	csmap.WithCustomHasher[int, *hyperloglog.Sketch](func(key int) uint64 {
		// Convert int to a byte slice
		bs := make([]byte, 8)
		binary.LittleEndian.PutUint64(bs, uint64(key))
		return xxh3.Hash(bs)
	}),
)

 

LoadOrStore가 csmap에 없기 때문에 Load 하고, 없을 때 sketch를 만들고 uniqueUser를 계속 insert 하면 된다.

go SaveUniqueVisitor(id, unique)

...

func SaveUniqueVisitor(markerID int, uniqueUser string) {
	sketch, exist := SketchedLocations.Load(markerID)

	if !exist {
		SketchedLocations.Store(markerID, hyperloglog.New16())
	}
	sketch.Insert([]byte(uniqueUser))

}

 

벤치마크

HLL을 무조건 사용해서 좋은 것은 아니다.

정확한 값이 필요는 없고, 메모리 효율적으로 관리하고 그럴 때 좋다.

 

메모리 관점에서 2가지 모드를 사용할 수 있는데, Sparse가 있는 모드랑 없는 모드다.

 

1. 희소 표현 (sparse representation)

HLL은 내부 레지스터 (or 카운터)의 compact 한 메모리 효율적인 표현으로 시작함.

모든 레지스터리에 대해 메모리를 미리 할당하는 게 아니고 0이 아닌 항목만 동적으로 기록한다.

HLL이 처리할 수 있는 최대 카디널리티에 비해 unique 수가 적을 때 좋다.

 

2. non 희소 표현

데이터 축적의 초기 단계나 비교적 작은 데이터 세트를 다룰 때 유용하다고 한다.

처음부터 모든 레지스터리에 메모리를 직접 할당하는데, 희소 표현 관련 관리 오버헤드를 줄일 수도 있다.

 

실제로 아래 벤치마크에서는 sparse를 끄고 해야 메모리를 일반 hashmap 보다 적게 먹는다.

(아래 벤치마크는 1000개의 아이템에 각 백만명의 유저가 있다고 했을 때)

import (
    "strconv"
	"testing"

	"github.com/axiomhq/hyperloglog"
)

const (
	K = 1000    // Number of unique keys to simulate
	N = 1000000 // Number of unique users to simulate
)

// Benchmark using a map with HyperLogLog
func BenchmarkMapWithHLL(b *testing.B) {
	userMap := make(map[string]*hyperloglog.Sketch)
	b.ResetTimer() // Reset the timer after setup
	for i := 0; i < b.N; i++ {
		for j := 0; j < N; j++ {
			userID := "user" + strconv.Itoa(j)
			itemID := "item" + strconv.Itoa(j%K) // Simulate K different items
			if userMap[itemID] == nil {
				userMap[itemID] = hyperloglog.New16NoSparse() // p=16 gives a good balance of accuracy and memory usage
			}
			userMap[itemID].Insert([]byte(userID))
		}
	}
}

// Benchmark using a map with sets
func BenchmarkMapWithSet(b *testing.B) {
	userMap := make(map[string]map[string]bool)
	b.ResetTimer() // Reset the timer after setup
	for i := 0; i < b.N; i++ {
		for j := 0; j < N; j++ {
			userID := "user" + strconv.Itoa(j)
			itemID := "item" + strconv.Itoa(j%K) // Simulate K different items
			if userMap[itemID] == nil {
				userMap[itemID] = make(map[string]bool)
			}
			userMap[itemID][userID] = true
		}
	}
}