database 컬럼 - 정렬 된 문자열 테이블(SSTable)또는 B+트리 데이터베이스 인덱스?




향상 속도 (5)

LSM-Trees는 스토리지 엔진 구조의 B-Tree보다 낫습니다. 랜덤 - 쓰기를 aof 방식으로 변환합니다. 다음은 LSM-Tree src입니다. https://github.com/shuttler/lsmtree

이 예제를 설명하기 위해 두 개의 데이터베이스를 사용합니다 : CouchDB and Cassandra .

CouchDB

CouchDB는 문서 인덱스에 대해 B + Tree를 사용합니다 (추가 전용 환경에서 작동 하도록 영리한 수정 사용). 특히 문서가 수정 (삽입 / 업데이트 / 삭제) 될 때 실행중인 데이터베이스 파일과 전체 리프에 추가됩니다. -> 문서 바로 다음에 업데이트 된 개정에 의해 영향을받는 모든 노드의 B + 트리에서 노드 경로.

이 조각 모음 식 색인 개정은 수정 사항과 함께 바로 인라인되어 전체 색인은 파일 끝에 추가 된 가장 최근의 색인 수정과 데이터 파일의 뒷부분에있는 추가 조각이 아직 관련이 있고 ' 아직 수정되지 않았습니다.

B + 트리 검색은 O (logn)입니다.

카산드라

카산드라는 레코드 키를 테이블에 저장하고 (이 질문에 대한 배열로 생각합시다) 때때로 개별 정렬 된 정렬 된 문자열 테이블 로 기록합니다.

우리는이 모든 테이블의 콜렉션을 "인덱스"(내가 이해 한 것)라고 생각할 수 있습니다.

카산드라는 이러한 정렬 된 문자열 테이블 을 수시로 압축 / 결합 하여 인덱스의 파일 표현을보다 완벽하게 작성해야합니다.

정렬 된 배열을 검색 하는 것은 O (logn)입니다.

문제

CassDB에서 부분 B + 트리 청크를 유지하는 것과 Cassandra에서 부분 정렬 된 문자열 인덱스를 유지하는 것 사이에 비슷한 수준의 복잡성이 있다고 가정하고 둘 다 O (logn) 검색 시간을 제공하면 데이터베이스 인덱스를 더 잘 표현할 수 있다고 생각합니까? ?

특별히 흥미로운 구현 세부 사항이있는 경우 특히 궁금합니다. 또는 둘 다 씻어 내고 개발자가 더 선호하는 데이터 구조를 선택하면됩니다.

생각해 줘서 고마워.


각 접근법에 대해 언급해야 할 몇 가지 사항은 다음과 같습니다.

B- 나무

  • 읽기 / 쓰기 작업은 로그 O(logn) 로 가정됩니다. 그러나 단일 데이터베이스 쓰기는 스토리지 시스템에서 다중 쓰기로 이어질 수 있습니다 . 예를 들어, 노드가 가득차면 분할되어야하며 이는 2 개의 새 노드에 2 개의 쓰기가 있고 부모 노드를 업데이트하기위한 1 개의 추가 쓰기가 있음을 의미합니다. 부모 노드가 가득차면 어떻게 증가 할 수 있는지 확인할 수 있습니다.
  • 일반적으로 B- 트리는 각 노드가 페이지 크기를 갖는 방식으로 저장됩니다. 이로 인해 쓰기 증폭 이라는 현상이 발생합니다. 단일 바이트를 업데이트해야하는 경우에도 전체 페이지가 기록됩니다.
  • 쓰기는 대개 무작위 (순차적이지 않음)이며, 따라서 자기 디스크의 경우 특히 느립니다 .

SSTables

  • SSTables는 일반적으로 다음 접근 방식에서 사용됩니다. Memtable이라는 메모리 내 구조가 있습니다. 가끔씩이 구조는 디스크에 SSTable로 플러시됩니다. 결과적으로 모든 쓰기가 memtable로 이동하지만 읽기가 현재 memtable에 없을 수도 있습니다.이 경우 현재 SSTables에서 검색됩니다 .
  • 결과적으로 쓰기는 O(logn) 입니다. 그러나 항상 메모리에서 수행된다는 것을 명심하십시오. 따라서 B- 디스크 디스크의 로그 연산보다 훨씬 빠른 속도로 수행해야합니다. 완전을 기하기 위해, 쓰기는 응급 복구를위한 write-ahead 로그에도 기록됩니다. 그러나 이것들은 모두 순차적 쓰기이므로 B- 트리의 임의 쓰기보다 훨씬 효율적 입니다.
  • memtable의 메모리에서 제공 될 경우 읽기 속도가 훨씬 빨라질 것으로 예상됩니다 . 그러나 오래된 디스크 기반 SSTable을 살펴볼 필요가있을 때 잠재적으로 B- 트리보다 읽기 속도가 느려질 수 있습니다. SSTable에 디스크 읽기를 수행하지 않고 값이 들어 있는지 확인하기 위해 블룸 필터 사용과 같은 몇 가지 최적화가 있습니다.
  • 앞서 언급했듯이 SSTables를 병합하는 데 사용되는 압축 이라고하는 백그라운드 프로세스가 있습니다. 이렇게하면 삭제 된 값을 제거하고 조각화를 방지 할 수 있지만 상당한 쓰기로드가 발생하여 들어오는 작업의 쓰기 처리량에 영향을 줄 수 있습니다.

그것이 분명해 짐에 따라,이 두 접근법의 비교는 훨씬 더 복잡합니다. 구체적인 비교를 제공하기위한 매우 단순한 시도에서 나는 다음과 같이 말할 수 있다고 생각한다.

  • SSTables는 B- 트리보다 쓰기 처리량이 훨씬 좋습니다. 그러나, 그들은 계속되는 다짐 때문에 덜 안정된 행동을 할 것으로 예상됩니다. 이 벤치마킹 비교 에서는 예가 표시됩니다.
  • B-tree는 일반적으로 트랜잭션 의미론이 필요한 유스 케이스에 우선합니다. 이것은 각 키가 단일 장소에서만 발견 될 수 있기 때문입니다 (SSTable과 달리 일부 SSTable에서는 폐기 된 값이있는 SSTable에 존재할 수 있음). 또한 일부 키는 값의 범위를 값의 일부로 나타낼 수 있기 때문에 가능합니다. 나무. 즉, 키 수준 및 범위 수준 잠금 메커니즘을 쉽게 수행 할 수 있습니다.

참고 문헌

[1] LevelDB와 MySQL의 성능 비교

[2] 데이터 집약적 인 응용 프로그램 설계


Tokutek 에서 사용되는 프랙탈 트리는 데이터베이스의 더 나은 색인이라고 생각합니다. B- 트리보다 실제 20 배에서 80 배 향상된 기능을 제공합니다.

프랙탈 트리 인덱스가 here 어떻게 작동하는지에 대한 훌륭한 설명이 here .


BTree 인덱스와 SSTable 인덱스를 비교할 때 쓰기 복잡성을 고려해야합니다.

  • 쓰기시 복사 BTree에 무작위로 쓰면 리프 노드와 경로의 사본을 만들기 위해 임의의 읽기가 발생합니다. 따라서 쓰기가 디스크에 순차적으로 수행되는 동안 RAM보다 큰 데이터 세트의 경우 이러한 임의의 읽기가 곧 병 목이됩니다. SSTable과 같은 인덱스의 경우, 쓰기시 이러한 읽기가 발생하지 않습니다. 순차 쓰기 만 있습니다.

  • 최악의 경우, BTree를 업데이트 할 때마다 log_b N IO가 발생할 수 있다는 것을 고려해야합니다. 즉, 모든 키에 대해 3 또는 4 개의 블록을 작성할 수 있습니다. 키 크기가 블록 크기보다 훨씬 작 으면 이것은 매우 비쌉니다. SSTable과 같은 인덱스의 경우 각 쓰기 IO에는 가능한 한 많은 새 키가 포함되므로 각 키의 IO 비용은 1 / B와 비슷합니다.

실제로 이것은 BTree보다 SSTable과 같은 속도로 (무작위 기록의 경우) 수천 배 빠릅니다.

구현 세부 사항을 고려할 때, 우리는 BTree를위한 잠금 전략이 상당히 복잡해지면서 SSTable과 같은 인덱스 (거의) 잠금을 구현하는 것이 훨씬 쉽다는 것을 알게되었습니다.

또한 읽기 비용을 다시 고려해야합니다. 당신은 랜덤 포인트 읽기를위한 O (log_b N) 랜덤 I / O가 BTree보다 낫지 만, SSTable과 같은 인덱스는 실제로 O (#sstables. log_b N)입니다. 알맞은 병합 스키마가 없다면 #sstables는 N에 비례합니다. 예를 들어 Bloom Filters를 사용하여 여러 가지 트릭을 만들 수 있지만 작은 임의의 범위 쿼리에는 도움이되지 않습니다. 이것이 우리가 카산드라와 함께 발견 한 것입니다 :

http://www.acunu.com/blogs/richard-low/cassandra-under-heavy-write-load-part-ii/

이것이 성 (GPL) 스토리지 엔진이 약간 다른 방식으로 병합하고 쓰기 성능이 약간의 트레이드 오프 (O (log ^ 2 N) / B)). 실제로 우리는 Cassandra의 쓰기에 대한 SSTable 색인보다 빠르다는 것을 알게되었습니다.

이것에 대해 더 알고 싶다면, 어떻게 작동하는지에 대한 이야기를했습니다 :


당신은 거의 이해하고 있습니다. 그러나 몇 분의 세부 사항을 놓치고 있습니다.

구조화 된 방식으로 사물을 설명하면, 카산드라 쓰기 작업 라이프 사이클은 다음 단계로 나뉩니다.

  • 커밋 로그 쓰기
  • memtable write
  • sstable write

Cassandra 쓰기는 커밋 로그 (내구성을 위해)에 기록 된 다음 memtable이라는 메모리 내 테이블 구조에 기록됩니다. 쓰기가 커밋 로그 및 메모리에 기록되면 쓰기가 성공한 것으로 간주되므로 쓰기시 매우 적은 디스크 I / O가 있습니다. memtable이 공간을 다 써 버렸을 때 (즉, 키의 수가 특정 제한을 초과하면 (기본값 128) 또는 지속 시간 (클러스터 클럭)에 도달하면 sstable, immutable 공간에 저장됩니다 (이 메커니즘은 Flushing ). SSTable에서 쓰기가 완료되면 데이터 폴더에서 S:\Apache Cassandra\apache-cassandra-1.2.3\storage\data 있습니다. 각 SSTable은 주로 2 개의 파일로 구성됩니다 - 색인 파일과 데이터 파일

  • 색인 파일 포함 - 블룸 필터 및 키 - 오프셋 쌍

    • 블룸 필터 : 블룸 필터는 요소가 집합의 구성원인지 여부를 테스트하는 데 사용되는 공간 효율적인 확률 데이터 구조입니다. 거짓 긍정은 가능하지만, 잘못된 음수는 아닙니다. 카산드라는 블룸 필터를 사용하여 키 조회를 수행 할 때 IO를 저장합니다. 각 SSTable에는 Cassandra가 디스크 검색을 수행하기 전에 확인하는 블룸 필터가 있으며 거의 ​​존재하지 않는 키에 대한 쿼리를 만듭니다
    • (키, 오프셋) 쌍 (데이터 파일을 가리킴)
  • 데이터 파일에는 실제 열 데이터가 들어 있습니다.

그리고 commitlog 파일과 관련해서는 Cassandra가 본질적으로 관리하는 암호화 된 파일입니다.이 파일은 제대로 볼 수 없습니다.

최신 정보:

Memtable은 내용이 키 / 열로 저장된 메모리 내 캐시입니다 (데이터는 키순으로 정렬 됨). 각 column-family에는 별도의 Memtable이 있으며 키에서 열 데이터를 검색합니다. 이제 여러분이 사실을 이해하기위한 명확한 마음의 상태에 있기를 바랍니다. 왜 우리가 디스크에서 찾을 수 없습니까?

Memtable 임계 값이 표백되지 않아서 플러시가 발생하지 않으므로 memtable이 가득 채워지지 않습니다. MemtableThresholds에 대한 자세한 내용은이 다이얼을 만지지 않는 것이 좋습니다.

SSTableStructure :

  • 내 데이터 폴더
    • 키 스페이스
      • CF
        • CompressionInfo.db
        • Data.db
        • Filter.db
        • Index.db
        • Statistics.db
        • 스냅 샷 // 스냅 샷이 찍히는 경우

더 자세한 정보는 sstable 참조하십시오 sstable







database indexing nosql couchdb cassandra