티스토리 뷰
1. 이전이야기
2회 열린세미나에서 발표했을때, UC에 대한 이야기를 한적이 있다. (Unique Count 집계하기)
해당글을 안본사람을 위해 잠깐 설명하자면, 중복이 제거된 카운팅(=UC)을 구할때, Set 자료구조를 이용해서 카운팅한다고 했다. (=물론 그때 핵심내용은 서버에 분산 저장 가능한게 핵심이었지만...)
이때, 매우 많은 아이템의 경우 HashSet은 아이템 갯수가 많아지면 커버가 안되고 BitSet을 쓰면 최대값이 큰 경우 문제가 된다고 했다. 그래서 두 장단점을 흡수하기위해 Map과 BitSet을 섞어서 구현한 SmartBitSet을 구현해서 처리했다고 했다. 아이디어는 비슷하지만 좀더 효율적으로 개선된 HyperSet이라는 Set구현체를 만들어 공개해 봤다.
기본 아이디어와 소스는 github에 정리해서 올려두었기 때문에, 거기에 다루지 않은 몇가지를 더 상세히 글을 써볼까 한다.
<소스코드>
https://github.com/jungkoo/hyperset
2. 자료구조별 메모리 사용률
우선 아래 코드로 실행한 결과부터 보자. 테스트는 1~Int최대값의 랜덤값 1억번 loop도는 샘플이다.
결론부터 말하면, 성능은 bitset이 가장 좋다. 하지만 메모리 사용률은 HyperSet이 가장 적다.
>> 2.1 BitSet의 메모리 사용 이야기
사실, 이론적으로 bitset이 메모리 사용률도 가장 적어야 할것 같다. (= 정확히 말하면 충분히 데이터가 촘촘하다면)
하지만 그렇지 않은 이유는, BitSet에서는 어떤값이 올지 알수 없기 때문에 가변적으로 bit배열을 확장할 수 밖에 없는 방식이기 때문이다.
예를 들어, 초반에는 100bit를 허용하는 공간을 만들었는데, 101이 들어오면 공간이 부족하기 때문에 더 큰 공간을 만들어야한다. 이때, 101bit 짜리 공간이 아닌 더 충분하고 적당히 큰 공간을 만들게 된다. 그 값은 구현에 따라 다르지만 쉽게 설명하기위해 2배 bit배열로 확장한다고 치면 200bit짜리 공간을 만들어 내야한다.
이때, 추가적인 값이 더 없이 101번 비트까지만 쓰는데 200bit짜리 배열을 유지해야 하는 상황이 온다.
대신, 이미 한번에 연속된 공간을 만들어 두기 때문에, 잦은 메모리 할당과 해제가 필요없어서 성능이 좋다.
동일 조건인데도 24초밖에 안걸렸다 (=HyperSet구현체에서는 1분 30초 정도가 걸렸다)
문제는 n번째 비트를 셋하는 구조다보니, 제일 큰 값 기준의 bit배열공간이 필요하다는것이다. (max값이 메모리 사용률을 결정)
* BitSet (성공)
>> 2.2 HashSet 이야기
동일 조건에서 돌렸는데 1200만건쯤에서 힙오류가 났다. 메모리 사용률은 데이터가 늘어나면서 꾸준히 늘어가는 모습을 몰수 있다. 메모리가 허용되었다고 쳐도 속도는 가장 늦다.
그 이유는 한건이 입력될때마다 공간을 메모리 할당해야 하기 때문에 성능도 떨어지고, 데이터 갯수에 영향을 받아 뒤로 넘어갈수록 메모리 사용률이 커지면서 GC도 빈번해져 성능저하가 심해진다.
HashSet 의 장점은 빈도수와 크기에 영향받지 않는다는점. 그리고 자료구조(String, Integer...)의 제약이 적은 범용성이다. 이 테스트 케이스에서는 안좋은 결과지만, 데이터 빈도수는 넓고 데이터가 적은 경우에는 일정한 성능이 보장된다.
* HashSet (1200만건쯤에서 heapsize오류발생)
>> 2.3 HyperSet 이야기
메모리 사용률이나 GC상황을 보면 두 자료구조의 중간정도의 위치에 있다고 볼수 있을것 같다.
성능은 BitSet보다 느리지만 HashSet 보다는 좋다. 메모리 사용률은 HashSet보다 유용하다.
GitHub에 간단히 설명하긴 했지만, 크기가 M 비트 크기의 배열을 블럭으로 관리하고, 그 블럭은 인덱스 번호를 써서 안쓰는 공간의 낭비를 줄인 BitSet으로 생각하면 편하다.
물론 더 나아가 가득찬 블럭의 비트배열은 null로 관리한다거나 하는 메모리 사용을 줄이기위한 아이디어들이 더 들어가 있다. 하지만 기본 개념은 동일하다.
* HyperSet(default) (성공)
3. HyperSet의 특징
>> HyperSet의 블럭사이즈
이번에 구현한 HyperSet의 경우 블럭의 크기(bit갯수)를 초기에 지정할 수 있다. 현재 기본값은 65536을 사용중이다.
블럭의 크기가 작아지면, 성능은 떨어진다. 왜냐면 해당 블럭에 속하는 값이 아니라면 메모리 할당을 해야하기 때문이다. 그리고 블럭크기만 변경했을때, 1분 30초 걸리던 작업이 3분으로 더 늦어지는걸 볼 수 있다.
늦어지는 이유는 블럭크기가 작아질수록 메모리 할당 빈도가 늘어나기 때문이다.
Set<Integer> set = new HyperSet(2048);
그럼 무조건 블럭크기를 키우는것이 좋다고 생각할수 있겠지만, 사실은 그렇지않다.
숫자의 분포가 이가 많이 빠진 구조라면 메모리를 더 효율적으로 사용한다.
즉, 블럭하나에 여러개의 값이 존재하지 않는 형태의 데이터라면 블럭사이즈를 줄이는게 도움이 될수 있다.
그래프를 보면 블럭크기 2048로 줄였을때, 초기 메모리 사용률은 100~200메가 이내로 더 적게 사용한 걸 알수 있다.
* HyperSet (블럭크기 2048)
* HyperSet (블럭크기 기본: 65536)
4. 뒷 이야기
4.1 데이터 쏠림 이야기
HyperSet은 "특정 숫자범위에 데이터가 쏠려있을때" 가장 효율적인 구조로 구현되어있다.
그 이유는 일반적으로 데이터는 쏠림 현상이 크다는것이다. 특히 sequence한 값을 KEY로 사용하는 데이터는 숫자가 클수록 가장 최신 데이터를 의미한다. 이는 과거 데이터일수록 노출될 확률이 낮다는걸 의미한다.
예를 들어, 태어난 순서대로 사람에게 고유한 숫자를 차례대로 발급해서 몇번재 태어난 사람인지 알수 있다고 하자.
이 사람들이 백화점을 이용한다고 치면 20~30대 나이대 사람들이 몰릴테고, 유치원에는 어린 유아의 사람들만 몰려있을것이다. 좀더 극단적으로 말하면 100년뒤에 1번대 사람들은 이미 죽고 없을 수도 있다.
또 자주쓰는 검색어에 숫자를 붙여 관리한다고 치자. 이러면 인기좋은 키워드는 상위권 숫자에 오게되고, 희귀 신조어 희귀 단어들은 뒤쪽에 흩어져 있을것이다.
즉, 이런 데이터 쏠림은 당연히 나타나는 현상이고 이를 고려한 구조라면 실분석에 유용할것으로 생각된다.
4.2 왜 메모리를 적게 쓰는 Set이 필요했나?
요즘은 PC도 싸져서, 여러대의 PC로 분산하거나 대용량 메모리를 달아서 구하는것도 가능하다.
하지만, 왜 메모리를 적게 쓰는 Set을 만들어야 했나 하는 이야기를 할까 한다.
하 둡 2.0에서는 어떤지 모르겠지만, 하둡 하위버전(0.1x버전대)에서는 맵갯수를 TaskTracker가 정해줬다(=사용자는 리듀서갯수만 지정가능). 그러다보니 맵작업이 여러개가 동시에 실행될수도 있고, 동시에 돌아갈때 모든 작업에서 메모리를 많이 쓰게되면 하둡서버가 먹통이 되는 문제도 존재했다. 그래서 메모리를 많이 쓰면 하둡작업만으로 UC처리하는건 한계가 있었다.
그래서 메모리서버를 도입해서 처리했는데, 혹시 맵/리듀스 안에서도 이런 작업을 할 수 있을정도로 더 효율적인것이 있으면 할 수 있을까? 하는 단순한 호기심에서 시작된것도 있다.
4.3 기냥 HashMap+BitSet을 쓰는걸로 충분하지 않았나?
물 론, 성능문제로 인한 문제를 이 조합으로 해결했었다. 하지만 위에 언급했던것처럼 BitSet은 내부적으로 메모리공간이 부족할 경우 더크게 재할당 되는 문제가 있는데, 이게 안쓰는 공간이 존재하는 문제가 존재한다. 블럭단위로 관리해서 어느정도는 비효율성이 줄어들긴 했지만, 동적으로 배열크기를 크게 늘리는 구조이기 때문에 이런 문제도 최소화 하고 싶었다.
그리고 특히, 블럭이 가득찼을때는 bit배열을 유지할 필요가 없기 때문에 이걸 직접 컨트롤하려면 기냥 직접 구현하는게 낫겠다 싶었다.
4.3 Integer만 되는데 String의 데이터는 어떻게 UC를 구할것이냐?
이 문제를 고민 많이 하였다. HashSet은 문자열도 처리가 가능하다. 하지만 BitSet이나 HyperSet은 숫자형 데이터에서만 가능한 문제가 있다. 지금까지는 숫자형 키가 존재해서 그 숫자를 이용하면 되었다.
하지만, 이런 숫자형키가 없이 문자열만으로 처리한다면, 집계전에 숫자키를 발급하는 작업이 필요할텐데 엄청큰 데이터에서 그런 작업을 한다면 집계하는것보다 더 오래걸릴것 같다. (물론 로깅할때마다 처리한다면 부담은 없겠지만)
아마 이건 http://helloworld.naver.com/helloworld/textyle/711301 이글에서 해결책을 찾을수 있을것 같다.
근사치를 구하는 방법인데, 아직 이 공식이나 그런건 이해를 못하겠다;
그래서 생각하는건, 여러개의 해쉬함수와 HyperSet조합을 이용해 블룸필터로 활용해서, 없는지 유무는 메모리에서 판별하고, 그 하위에서는 sqllite같은 파일DB를 써서 정확한 값을 이용하는건 어떨까 싶기도 하다.
근데 정확한 숫자카운팅을 위해 이런 자원낭비가 필요있는가 싶기도 하지만..
4.4 더 개선한 여지는 있는가?
지금은 HyperSet은 여러개의 블럭(내부는 Set구현체)로 관리된다.
현 재는 고정크기의 FIxedSet과 단일값의 AloneSet을 내부적으로 쓰고 있는데, 블럭으로 쪼개졌기 때문에 블럭의 조합크기만으로 표현이 가능하기 때문에, 블럭을 풀링해서 사용하여 인스턴스화된 블럭을 재활용하는것도 방법일것 같다.
하지만, 일단 안정화에 더 우선순위를 두고 싶긴하다.
관심있는 사람은 이슈등록이나 코드에 기여를 해주면 좋을듯하다.
