jaso extends j2ee

Bigtable이 단순히 데이터를 저장하는 데이터베이스의 역할만 수행하는 경우라면 MySQL 클러스터 기능과 같은 기존의 데이터베이스 기능을 적절하게 활용하면 된다.
Bigtable과 같은 데이터 저장소의 가치를 이해하기 위해서는 데이터 모델에 대한 이해와 적절하게 분산되어 있는 분산의 구조, 컬럼 기반 저장 방식 등에 대해 제대로 이해하고 있어야 한다.

Bigtable이 sparse matrix 저장소에 적합한 구조라는 것은 이미 알려진 사실이다. sparse matrix는 10억*10억 matrix에 대부분의 값은 0이고 하나의 row에 수십 ~ 수천 정도만 값이 있는 matrix를 말한다. 하나의 웹 페이지내에 있는 anchor나 term 들이 이런 경우이다. 전체 웹 페이지는 수십억 내지 수백억이고 이들이 포함하고 있는 anchor 값을 이용하여 matrix를 만들면 다음과 같은 sparse matrix가 된다.


기존 관계형 데이터베이스에서는 row-column이 만나는 cell에 값을 하나만 저장할 수 있다. 따라서 이런 sparse matrix를 저장하기 위해서는 다음과 같은 테이블 구성이 되어야 한다.


이런 경우 데이터가 많은 경우 분산된 데이터베이스 인스턴스에서 관리되어야 하고 T_URL과 T_ANCHOR에 대한 외래키 관계도 구성하기 어렵다.
Bigtable을 이용할 경우에는 다음과 같이 저장할 수 있다.


하나의 cell에 n개의 데이터를 저장할 수 있기 때문에 특정 웹 페이지에 잇는 anchor 정보를 하나의 컬럼에 모두 저장할 수 있다.
다음은 Map&Reduce와 함께 matrix 계산에 Bigtable이 어떻게 활용되는지 살펴본다.
matrix 곱하기의 경우 O(n*n)의 복잡도를 가지기 때문에 n이 증가할 수록 속도는 급격하게 증가하게 된다.  matrix 계산에서 병렬처리는 많은 연구가 이루어 졌고 다양한 방법이 있지만 여기서 사용한 방법은 다음과 같다.

위에서 보는 것 처럼 C11 계산과 C12계산은 병렬로 계산이 가능하다. 자세한 내용은 다음 사이트에 잘 나와 있다.
http://carbon.cudenver.edu/csprojects/CSC5809S01/Simd/parmult.html

이런 계산식에서 문제는 Matrix-B의 데이터가 많은 경우라면 문제가 되지만 Matrix-B가 sparse한 경우라면 O(n*m)이 아니라 O(n * avg(count(b에서 0이 아닌 값의 갯수)) 의 복잡도가 된다. 그리고 이것을 분산병렬 처리할 경우 병렬처리 만큼 속도가 향상된다.

Bigtable과 같은 저장소와 Map&Reduce를 이용하여 위의 matrix 연산을 처리하는 방법은 다음과 같다.
1. 두개의 matrix를 테이블에 저장한다.

2. Map Task를 구성하기 위해 Tablet 단위로 job을 split한다.
3. InputFormat에서는 자신이 처리할 Tablet의 scanner를 오픈하여 값을 하나씩 읽으면서 map()으로 전달한다.
4. map() 에서는 전달받은 값의 row, column 정보를 이용하여 Matrix-B의 값을 조회한 다음 계산 결과를 출력한다.
5. reduce() 에서는 계산 결과를 받아 sum한 다음 결과 테이블에 저장한다.

위의 코드는 Hadoop Map&Reduce를 기준으로 하였으며 정식 코드가 아니라 pseudo 코드 수준이다.
위의 코드에서 보는 것처럼 코드는 아주 간단하다. 여기서 성능에 영향을 미치는 부분은 4번 map 처리에서 scannerB에서 데이터를 가져오는 부분이 된다. Matrix-B에서 row 전체를 가져오는 것이기 때문에 row의 데이터가 많은 경우 속도가 급격하게 저하된다. matrix는 sparse 하다라고 가정했기 때문에 수십 ~ 수백 정도의 데이터만 저장되어 있어 수 ms 내에 데이터 조회가 가능하다. Bigtable의 경우 sequential read의 경우 초당 수천개 데이터를 처리할 수 있다. HBase의 경우 현재는 수백 내지 천개 정도 처리하는 수준이다.
Matrix-B에서 하나의 row를 조회하는데 평군 5ms 정도 소요된다고 했을 때 전체 처리 시간은 다음과 같다.
100개의 서버와 한 서버에 6개의 map task를 동시에 수행할 경우 map task 수행되는데 소요되는 시간은 2.3 시간 정도이다. Map&Reduce 작업 처리 과정과 Bigtable의 데이터 조회시간은 데이터가 증가할수록 급격하게 증가하지 않고 선형적으로 증가하고, 장비 대수가 늘어날 수록 처리 속도는 선형적으로 감소하기 때문에 더 많은 장비를 투입하면 더 짮은 시간에도 처리가 가능할 것이다.
물론 이 수치는 이론적인 수치이며 HBase를 이용하여 테스트를 수행해 봐야 정확한 처리시간을 알 수 있을 것이다.
페이지랭크 계산을 할 경우에도 이런 방법을 적용할 수 있다. 다음과 같은 페이지 관계가 있다.
 Bigtable에는 다음과 같이 저장할 수 있다.


여기서 계산은 다음과 같이 처리한다.
1. InputFormat는 rowkey와 rank 데이터를 scan하여 map() 으로 전달한다.
2. map()에서는 rowkey에 해당하는 outlink 값을 조회하여 계산 값을 reduce로 보낸다.
3. reduce에서는 row, column을 키로 하여 sum한 다음 rank 필드에 다시 저장한다.
4. 1 ~3번 과정을 수렴할때까지(50번 정도) 반복한다.

* HBase와 Bigtable, Map&Reduce 등의 자료를 참고로 하여 작성된 내용이기 때문에 틀린 부분이 있을 수 있습니다. 틀린 부분이나 다른 의견은 댓글 달아 주시면 많은 도움이 될 것 같습니다.

크리에이티브 커먼즈 라이센스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.

Posted by 김형준