HBase data structure: SortedMap(RowKey, List(SortedMap(Column, List(Value, TimeStamp))))
from http://www.docstoc.com/docs/2996433/Hadoop-and-HBase-vs-RDBMS
HBase, Bigtable은 소개에서도 알 수 있듯이, 분산된 다중 sorted map가 그 정체이다 (아마도 B+ Tree거나 RB-Tree가 아닐까). 항상 정렬되어있기 때문에 배분 알고리즘도 간단히 짤 수 있다. 그렇기 때문에 단일한 접근을 보장할 수 있어 관리가 편하다. 이러한 접근 방식은 데이터 덩어리를 통째로 읽어들이는 DFS에 매우 적합하고 효율적인 구조라고 할 수 있겠다. 일반적으로 DFS는 선형적으로 큰 자료를 읽기에 최적화되어있고, 랜덤엑서스에는 매우 취약한 성능을 보인다.
물론 일반 RDBMS의 레코드셋도 primary key에 대한 sorted map이다. 그리고 색인들도 sorted map이고, 그 값이 저장된 곳의 주소이다. 하지만 이들은 다중 sorted map이 아니다. 다시 말해, primary key가 아닌 색인도 바로 접근할 수 있다는 말이다. 예를 들어서 나이가 19세 미만인 미성년자들을 조회하고 싶다면(select * from people where age < 19) RDBMS에서는 색인을 타고 맨 앞자리로 가서 하나씩 하나씩 뒤로 가면서 해당 주소의 자료를 불러올 수 있다. 처음 검색에 O(log(n)) 시간이 걸리고 그 뒤로는 O(1)가 걸린다는 말이다. 랜덤 액서스에 아주 효율적인 자료 구조이다.
HBase나 Bigtable 같은 DB는 그러한 색인을 지원하는가? 그렇지 않다. 어떠한 컬럼에 접근하기 위해서는 반드시 그 레코드에 접근을 해야한다. 일반 RDBMS처럼 돌아가는 방법은 없다. 모든 블럭에 대해서 '검색'을 해야한다. 과연 여기에는 시간이 얼마나 걸릴 것인가? 데이터베이스가 64MB 블럭(b)으로 쪼개져 있다고 가정하자. 그 모두가 다른 노드(m)에 들어가 있다면 각 노드당 걸리는 시간은 O(b)이고 총 연산량은 O(n)이다. 더욱이 이 결과는 증분 탐색이 불가능해서 어딘가에다가 저장을 해놓아야 하는데, 여기에 걸리는 시간은 항상 O(n)이다. 매우 취약한 자료 구조이다.
이런 문제점을 해결하기 위해서 유사한 프로젝트인 Neptune이 노력을 하고 있다고 한다. 현재 버전에서는 다중 sorted tree 기반으로 작동을 하는 것으로 보인다. 그렇다면 부가적인 index들을 다른 테이블에 만드는 방식이 되지 않을까 생각해본다. 새로운 테이블에 컬럼의 값을 Key로 삼고 RowKey를 Value로 삼으면 충분히 구현이 가능하다. 물론 분산 환경의 성능 부분에서 어떤 차이가 있을지는 나와봐야 알 것 같다. Neptune은 보다 고급 transaction을 요구하는 JDBC 표준 접근도 허용하고자 한다. 여러모로 기대가 많이 된다.
우선은 가장 단순한 index(sorted map)에 대해서만 살펴봐도 이렇게 차이점이 많다. 다음에 살펴 볼 join에서는 아마도 더 큰 문제점들을 발견할 수 있을 것이다. index는 단일 노드에서만 작동하지만 워낙에 값싼 연산이라서 큰 문제가 되지 않으며, 실제 연산-자료간의 지역성에 해를 끼치지도 않는다. 반면 join은 보다 대량의 연산을 필요로 하여, 분산 환경에서는 구현이 가능할지, 성능은 어떨지, 그리고 지역성을 보장할지도 가늠하기 힘들다. 시간 나는대로 관련 논문들을 찾아보아야겠다.
이상 그냥 마구 생각나는대로 끄적여봤습니다. 제 말을 어디 가서 논의의 근거로 쓰기에는 부족합니다. 여러분들의 날카로운 지적 환영합니다. ^^
from http://www.docstoc.com/docs/2996433/Hadoop-and-HBase-vs-RDBMS
HBase, Bigtable은 소개에서도 알 수 있듯이, 분산된 다중 sorted map가 그 정체이다 (아마도 B+ Tree거나 RB-Tree가 아닐까). 항상 정렬되어있기 때문에 배분 알고리즘도 간단히 짤 수 있다. 그렇기 때문에 단일한 접근을 보장할 수 있어 관리가 편하다. 이러한 접근 방식은 데이터 덩어리를 통째로 읽어들이는 DFS에 매우 적합하고 효율적인 구조라고 할 수 있겠다. 일반적으로 DFS는 선형적으로 큰 자료를 읽기에 최적화되어있고, 랜덤엑서스에는 매우 취약한 성능을 보인다.
물론 일반 RDBMS의 레코드셋도 primary key에 대한 sorted map이다. 그리고 색인들도 sorted map이고, 그 값이 저장된 곳의 주소이다. 하지만 이들은 다중 sorted map이 아니다. 다시 말해, primary key가 아닌 색인도 바로 접근할 수 있다는 말이다. 예를 들어서 나이가 19세 미만인 미성년자들을 조회하고 싶다면(select * from people where age < 19) RDBMS에서는 색인을 타고 맨 앞자리로 가서 하나씩 하나씩 뒤로 가면서 해당 주소의 자료를 불러올 수 있다. 처음 검색에 O(log(n)) 시간이 걸리고 그 뒤로는 O(1)가 걸린다는 말이다. 랜덤 액서스에 아주 효율적인 자료 구조이다.
HBase나 Bigtable 같은 DB는 그러한 색인을 지원하는가? 그렇지 않다. 어떠한 컬럼에 접근하기 위해서는 반드시 그 레코드에 접근을 해야한다. 일반 RDBMS처럼 돌아가는 방법은 없다. 모든 블럭에 대해서 '검색'을 해야한다. 과연 여기에는 시간이 얼마나 걸릴 것인가? 데이터베이스가 64MB 블럭(b)으로 쪼개져 있다고 가정하자. 그 모두가 다른 노드(m)에 들어가 있다면 각 노드당 걸리는 시간은 O(b)이고 총 연산량은 O(n)이다. 더욱이 이 결과는 증분 탐색이 불가능해서 어딘가에다가 저장을 해놓아야 하는데, 여기에 걸리는 시간은 항상 O(n)이다. 매우 취약한 자료 구조이다.
이런 문제점을 해결하기 위해서 유사한 프로젝트인 Neptune이 노력을 하고 있다고 한다. 현재 버전에서는 다중 sorted tree 기반으로 작동을 하는 것으로 보인다. 그렇다면 부가적인 index들을 다른 테이블에 만드는 방식이 되지 않을까 생각해본다. 새로운 테이블에 컬럼의 값을 Key로 삼고 RowKey를 Value로 삼으면 충분히 구현이 가능하다. 물론 분산 환경의 성능 부분에서 어떤 차이가 있을지는 나와봐야 알 것 같다. Neptune은 보다 고급 transaction을 요구하는 JDBC 표준 접근도 허용하고자 한다. 여러모로 기대가 많이 된다.
우선은 가장 단순한 index(sorted map)에 대해서만 살펴봐도 이렇게 차이점이 많다. 다음에 살펴 볼 join에서는 아마도 더 큰 문제점들을 발견할 수 있을 것이다. index는 단일 노드에서만 작동하지만 워낙에 값싼 연산이라서 큰 문제가 되지 않으며, 실제 연산-자료간의 지역성에 해를 끼치지도 않는다. 반면 join은 보다 대량의 연산을 필요로 하여, 분산 환경에서는 구현이 가능할지, 성능은 어떨지, 그리고 지역성을 보장할지도 가늠하기 힘들다. 시간 나는대로 관련 논문들을 찾아보아야겠다.
이상 그냥 마구 생각나는대로 끄적여봤습니다. 제 말을 어디 가서 논의의 근거로 쓰기에는 부족합니다. 여러분들의 날카로운 지적 환영합니다. ^^
덧글