대형 128 비트 정수를 저장하기위한 디스크 구조?

Question

필자는 약 5 억 개의 128 비트 정수를 가지고 있으며 연간 약 100M을 더합니다. 아무것도 삭제되지 않습니다. 숫자는 규모와 시간에 따라 균일하게 분포합니다.

기본적으로 DB에 번호가 이미 있는지 여부를 반환하는 추가 작업이 필요합니다. 또한이 시스템에 너무 많은 RAM을 사용하고 싶지 않으므로 모든 것을 메모리에 저장하는 것이 내가 원하는 것이 아닙니다.

지금까지 우리는 두 개의 bigint를 기본 키로 사용하여 MySQL에서 여러 개의 MyISAM 테이블을 사용 해왔다. 이것은 우리에게 만족스러운 성능을 제공하지만,이 작업에 적합한 도구가 아닌 것 같습니다. 테이블을 분할하기 전에 몇 가지 성능 문제가 있었으며 우리는 정전에 대해 손상을 입었습니다. 또한 DB는 우리에게 필요하지 않은 많은 기능을 제공합니다.

저는 리눅스에서 파이썬을 사용하고 있습니다.하지만 제안 사항은 공개되어 있습니다.

Similar question in C++.

업데이트 : Marcelo의 의견은 Bloom Filter이라고 말하면서 나에게 정말로 유망한 것으로 보입니다. 해시 작업을하고 있기 때문에 이미 완전한 정확성을 포기 했으므로 정확도/성능이 크게 향상 될 수 있습니다. 정수의 N 비트의 해시를 계산하여 선택

Answer 1

2 삽입 ^N SQLite는 데이터베이스 풀의 하나에 각각 정수 (2 ⁸ 좋은 수가 아마도). 한 테이블의 한 열을 기본 키로 만들어 기존 번호를 삽입하지 못합니다.

정수가 이미 충분히 무작위라고 가정하면, 아마도 가장 중요한 바이트를 "해시"로 선택하면됩니다.

편집 : 일부 테스트를 수행했습니다. 약 2 시간 만에 2 천 5 백만 개의 항목을 삽입했지만이 과정에서 1GB 이상을 차지했습니다. 이것은 난수를 생성하여 32 개의 하위 프로세스에 배포하며 각 하위 프로세스는 제어하에 하나의 SQLite 데이터베이스를 사용하고 100,000 회의 삽입마다 한 번 커밋합니다. 삽입은 현재 문제의 요구 사항 인 3Hz를 훨씬 넘어서 약 1350Hz로 움직이고 있지만 전체 데이터베이스는 여전히 캐시에 들어갑니다 (8GB RAM이 있음). 현재 데이터베이스 크기에 가깝지 않으면 정상 상태 성능을 알 수 없습니다. 이 시점에서 모든 삽입은 적어도 4 개의 디스크 헤드 이동 (인덱스와 테이블 읽기 및 쓰기, 아마도 B + 트리로의 자세한 드릴 다운)을 유발할 것이며, 그러면 실제로 얼마나 많은 고통이 있는지 알게 될 것입니다 .

저는 이것이 맞춤형 솔루션으로 훨씬 효율적으로 해결할 수있는 진정 흥미로운 문제라고 생각하기 시작했습니다. 그러나 데이터베이스 엔진 성능을 크게 뛰어 넘는 데는 상당한 노력이 필요할 것으로 생각됩니다.

Answer 2

해시를 해시 하시겠습니까?