2019년 가을, Mail.ru Cloud iOS 팀에서 오랫동안 기다려온 이벤트가 열렸습니다. 애플리케이션 상태의 영구 저장을 위한 기본 데이터베이스는 모바일 세계에서 매우 이색적입니다. Lightning 메모리 매핑 데이터베이스 (LMDB). 컷 아래에서 네 부분으로 구성된 자세한 리뷰에 여러분의 관심을 초대합니다. 먼저 사소하지 않고 어려운 선택의 이유에 대해 이야기합시다. 그런 다음 LMDB 아키텍처의 핵심인 메모리 매핑 파일, B + 트리, 트랜잭션 및 다중 버전 관리를 구현하기 위한 copy-on-write 접근 방식의 세 가지 고려 사항으로 이동하겠습니다. 마지막으로 디저트의 경우 실용적인 부분입니다. 여기서는 하위 수준 키-값 API 위에 인덱스 테이블을 포함하여 여러 테이블이 있는 기본 스키마를 설계하고 구현하는 방법을 살펴봅니다.

내용

1. 추진동기
2. LMDB 포지셔닝
3. 세마리 고래 LMDB
   3.1. 고래 #1. 메모리 매핑된 파일
   3.2. 고래 #2. B+-트리
   3.3. 고래 #3. 기록 중 복사
4. 키-값 API 위에 데이터 스키마 설계
   4.1. 기본 추상화
   4.2. 테이블 모델링
   4.3. 테이블 간의 관계 모델링

1. 추진동기

2015년에 XNUMX년에 한 번, 우리는 응용 프로그램의 인터페이스가 얼마나 자주 지연되는지 측정했습니다. 우리는 이것을하지 않았습니다. 때때로 응용 프로그램이 사용자 작업에 응답하지 않는다는 사실에 대해 점점 더 많은 불만이 있습니다. 버튼을 누르지 않고 목록을 스크롤하지 않는 등입니다. 측정 역학 정보 말한 AvitoTech에서는 숫자 순서만 제공합니다.

측정 결과는 우리에게 냉수 샤워가 되었습니다. 동결로 인한 문제가 다른 어떤 것보다 훨씬 더 많다는 것이 밝혀졌습니다. 이 사실을 깨닫기 전에 품질의 주요 기술 지표가 충돌이 없는 경우 초점을 맞춘 후에 이동 프리즈 프리.

구축한 멈춤이 있는 대시보드 그리고 보낸 정량적 и 품질 그 원인을 분석한 결과 주요 적이 명확해졌습니다. 애플리케이션의 메인 스레드에서 실행되는 무거운 비즈니스 로직입니다. 이 불명예에 대한 자연스러운 반응은 그것을 작업 흐름에 밀어넣고 싶은 불타는 욕망이었습니다. 이 문제를 체계적으로 해결하기 위해 경량 액터를 기반으로 하는 다중 스레드 아키텍처에 의존했습니다. 나는 iOS 세계를 위해 그녀의 적응을 바쳤습니다. 두 개의 스레드 집단 트위터에서 하브레에 관한 기사. 현재 이야기의 일부로 데이터베이스 선택에 영향을 준 결정의 측면을 강조하고 싶습니다.

시스템 구성의 액터 모델은 멀티스레딩이 두 번째 본질이 된다고 가정합니다. 그 안에 있는 모델 개체는 스레드 경계를 교차하는 것을 좋아합니다. 그리고 그들은 때때로 그리고 어떤 장소에서가 아니라 거의 끊임없이 그리고 모든 곳에서 이것을합니다.

데이터베이스는 제시된 다이어그램의 초석 구성 요소 중 하나입니다. 주요 작업은 매크로 패턴을 구현하는 것입니다. 공유 데이터베이스. 엔터프라이즈 세계에서 서비스 간 데이터 동기화를 구성하는 데 사용되는 경우 액터 아키텍처의 경우 스레드 간 데이터입니다. 따라서 다중 스레드 환경에서 작업해도 최소한의 어려움도 발생하지 않는 데이터베이스가 필요했습니다. 특히 이것은 파생된 개체가 최소한 스레드로부터 안전해야 하며 이상적으로는 전혀 변경 불가능해야 함을 의미합니다. 아시다시피 후자는 성능에 유익한 영향을 미치는 잠금에 의존하지 않고 여러 스레드에서 동시에 사용할 수 있습니다.

데이터베이스 선택에 영향을 준 두 번째 중요한 요소는 클라우드 API였습니다. 동기화에 대한 git 접근 방식에서 영감을 받았습니다. 그와 마찬가지로 우리는 목표로 오프라인 퍼스트 API, 클라우드 클라이언트에 더 적합해 보입니다. 클라우드의 전체 상태를 한 번만 펌핑한 다음 대부분의 경우 롤링 변경을 통해 동기화가 발생한다고 가정했습니다. 아아, 이 가능성은 여전히 ​​이론적인 영역에만 있으며 실제로 클라이언트는 패치 작업 방법을 배우지 않았습니다. 이에 대한 여러 가지 객관적인 이유가 있으며 소개를 지연시키지 않기 위해 괄호에서 제외하겠습니다. 이제 훨씬 더 흥미로운 것은 API가 "A"라고 말하고 소비자가 "B"라고 말하지 않을 때 어떤 일이 발생하는지에 대한 학습 결과입니다.

따라서 풀 명령을 실행할 때 로컬 스냅샷에 패치를 적용하는 대신 전체 상태를 전체 서버 상태와 비교하는 git을 상상하면 동기화 방법에 대해 상당히 정확한 아이디어를 갖게 됩니다. 클라우드 클라이언트에서 발생합니다. 구현을 위해 모든 서버 및 로컬 파일에 대한 메타 정보와 함께 메모리에 두 개의 DOM 트리를 할당해야 한다고 추측하기 쉽습니다. 사용자가 클라우드에 500만 개의 파일을 저장한 다음 이를 동기화하려면 1만 개의 노드가 있는 두 개의 트리를 다시 만들고 파괴해야 하는 것으로 나타났습니다. 그러나 각 노드는 하위 개체의 그래프를 포함하는 집계입니다. 이러한 관점에서 프로파일링 결과는 예상되었습니다. 병합 알고리즘을 고려하지 않아도 엄청난 수의 작은 개체를 만들고 파괴하는 절차 자체에 상당한 비용이 든다는 것이 밝혀졌으며 기본 동기화 작업이 많은 수에 포함되어 상황이 악화됩니다. 사용자 스크립트의. 결과적으로 데이터베이스 선택에서 두 번째로 중요한 기준인 개체의 동적 할당 없이 CRUD 작업을 구현하는 기능을 수정했습니다.

다른 요구 사항은 보다 전통적이며 전체 목록은 다음과 같습니다.

1. 스레드 안전.
2. 다중 처리. 동일한 데이터베이스 인스턴스를 사용하여 스레드 간뿐만 아니라 기본 애플리케이션과 iOS 확장 간에도 상태를 동기화하려는 욕구에 따라 결정됩니다.
3. 저장된 엔터티를 변경할 수 없는 개체로 나타내는 기능입니다.
4. CRUD 작업 내에서 동적 할당이 부족합니다.
5. 기본 속성에 대한 트랜잭션 지원 ACID키워드: 원자성, 일관성, 격리 및 신뢰성.
6. 가장 인기있는 사례의 속도.

이러한 요구 사항으로 인해 SQLite는 여전히 좋은 선택이었습니다. 그런데 대안 연구의 일환으로 우연히 만난 책 "LevelDB 시작하기". 그녀의 리더십 아래 실제 클라우드 시나리오에서 다양한 데이터베이스의 작업 속도를 비교하는 벤치마크가 작성되었습니다. 결과는 가장 큰 기대치를 초과했습니다. 모든 파일의 정렬된 목록에 커서를 놓고 지정된 디렉토리에 대한 모든 파일의 정렬된 목록을 가져오는 가장 인기 있는 사례에서 LMDB는 SQLite보다 10배 빠른 것으로 나타났습니다. 선택은 분명해졌습니다.

2. LMDB 포지셔닝

LMDB는 데이터베이스의 가장 낮은 기본 계층인 스토리지를 구현하는 매우 작은(단지 10K 라인) 라이브러리입니다.

위의 다이어그램은 더 높은 수준을 구현하는 SQLite와 LMDB를 비교하는 것이 일반적으로 Core Data가 있는 SQLite보다 더 정확하지 않다는 것을 보여줍니다. BerkeleyDB, LevelDB, Sophia, RocksDB 등 동일한 경쟁자와 동일한 스토리지 엔진을 인용하는 것이 더 공정할 것입니다. LMDB가 SQLite의 스토리지 엔진 구성 요소 역할을 하는 개발도 있습니다. 2012년 첫 실험 실시 저자 LMDB 하워드 추. 조사 결과 OSS 열광자들이 그의 이니셔티브를 선택했을 정도로 매우 흥미로운 것으로 판명되었고, 루모SQL. 2020년 XNUMX월 이 프로젝트의 저자는 Den Shearer입니다. 제시 LinuxConfAu에 있습니다.

LMDB의 주요 용도는 애플리케이션 데이터베이스용 엔진입니다. 라이브러리는 개발자에게 그 모습을 빚지고 있습니다. OpenLDAP, 프로젝트의 기반으로 BerkeleyDB에 크게 불만을 품은 사람. 초라한 도서관에서 밀려나다 비트리, Howard Chu는 우리 시대의 가장 인기 있는 대안 중 하나를 만들 수 있었습니다. 그는 이 이야기와 LMDB의 내부 구조에 대한 그의 매우 멋진 보고서를 바쳤습니다. "번개 메모리 매핑 데이터베이스". 레오니드 유리예프(일명 일레오) Highload 2015에서 발표한 Positive Technologies의 "LMDB 엔진은 특별한 챔피언입니다.". 여기에서 그는 ReOpenLDAP를 구현하는 유사한 작업의 맥락에서 LMDB에 대해 이야기하며 LevelDB는 이미 비교 비판을 받았습니다. 구현 결과, Positive Technologies는 활발히 개발 중인 포크까지 얻었습니다. MDBX 매우 맛있는 기능, 최적화 및 버그 수정.

LMDB는 종종 있는 그대로의 스토리지로도 사용됩니다. 예를 들어, Mozilla Firefox 브라우저 선택 다양한 요구 사항을 충족하고 버전 9부터 Xcode 선호하는 인덱스를 저장하는 SQLite.

이 엔진은 모바일 개발 세계에서도 인기를 끌었습니다. 사용 흔적이 남을 수 있습니다 발견 Telegram용 iOS 클라이언트에서. LinkedIn은 한 단계 더 나아가 자체 개발한 데이터 캐싱 프레임워크인 Rocket Data의 기본 스토리지로 LMDB를 선택했습니다. 말한 2016년 기사에서.

LMDB는 Oracle의 통제하에 전환 후 BerkeleyDB가 남긴 틈새 시장에서 태양의 자리를 놓고 성공적으로 싸우고 있습니다. 이 라이브러리는 자체 종류와 비교해도 속도와 안정성으로 사랑받고 있습니다. 아시다시피 공짜 점심은 없으며 LMDB와 SQLite 중 하나를 선택할 때 직면하게 될 절충점을 강조하고 싶습니다. 위의 다이어그램은 어떻게 증가된 속도를 얻을 수 있는지 명확하게 보여줍니다. 첫째, 우리는 디스크 스토리지 위에 추가 추상화 계층에 대해 비용을 지불하지 않습니다. 물론 좋은 아키텍처에서는 그것들 없이는 여전히 할 수 없으며 필연적으로 애플리케이션 코드에 나타날 것이지만 훨씬 더 얇을 것입니다. 예를 들어 SQL 언어의 쿼리 지원과 같이 특정 응용 프로그램에 필요하지 않은 기능은 없습니다. 둘째, 디스크 스토리지에 대한 요청에 대한 애플리케이션 작업의 매핑을 최적으로 구현할 수 있습니다. 만약 SQLite 내 작품에 평균 애플리케이션의 평균 요구 사항에서 비롯된 경우 애플리케이션 개발자인 당신은 주요 로드 시나리오를 잘 알고 있습니다. 보다 생산적인 솔루션을 위해서는 초기 솔루션 개발과 후속 지원 모두에 대해 증가된 가격표를 지불해야 합니다.

3. 세마리 고래 LMDB

조감도에서 LMDB를 살펴본 후 더 깊이 들어갈 때입니다. 다음 세 섹션은 스토리지 아키텍처가 기반이 되는 주요 고래 분석에 전념할 것입니다.

1. 디스크 작업 및 내부 데이터 구조 동기화를 위한 메커니즘으로서의 메모리 매핑된 파일.
2. 저장된 데이터 구조의 조직으로서의 B+-트리.
3. ACID 트랜잭션 속성 및 다중 버전 관리를 제공하기 위한 접근 방식인 Copy-on-write.

3.1. 고래 #1. 메모리 매핑된 파일

메모리 매핑된 파일은 리포지토리 이름에도 나타나는 중요한 아키텍처 요소입니다. 저장된 정보에 대한 캐싱 및 동기화 액세스 문제는 전적으로 운영 체제에 달려 있습니다. LMDB는 자체적으로 캐시를 포함하지 않습니다. 이는 작성자의 의식적인 결정입니다. 매핑된 파일에서 직접 데이터를 읽으면 엔진 구현에서 많은 코너를 자를 수 있기 때문입니다. 아래는 그들 중 일부의 완전한 목록과는 거리가 멀다.

1. 여러 프로세스에서 작업할 때 스토리지에서 데이터의 일관성을 유지하는 것은 운영 체제의 책임이 됩니다. 다음 섹션에서 이 역학에 대해 그림과 함께 자세히 설명합니다.
2. 캐시가 없으면 동적 할당과 관련된 오버헤드가 LMDB에서 완전히 제거됩니다. 실제로 데이터를 읽는 것은 포인터를 가상 메모리의 올바른 주소로 설정하는 것일 뿐 그 이상은 아닙니다. 환상처럼 들리지만 리포지토리 소스에서 모든 calloc 호출은 리포지토리 구성 기능에 집중되어 있습니다.
3. 캐시가 없다는 것은 캐시에 액세스하기 위한 동기화와 관련된 잠금이 없다는 것을 의미하기도 합니다. 임의의 숫자가 동시에 존재할 수 있는 판독기는 데이터로 가는 도중에 단일 뮤텍스를 만나지 않습니다. 이로 인해 읽기 속도는 CPU 수 측면에서 이상적인 선형 확장성을 갖습니다. LMDB에서는 수정 작업만 동기화됩니다. 한 번에 한 명의 작가만 있을 수 있습니다.
4. 최소한의 캐싱 및 동기화 논리는 다중 스레드 환경에서 작업하는 것과 관련된 매우 복잡한 유형의 오류로부터 코드를 저장합니다. Usenix OSDI 2014 컨퍼런스에서 두 가지 흥미로운 데이터베이스 연구가 있었습니다. "모든 파일 시스템이 동일하게 생성되지 않음: 크래시 일치 애플리케이션 제작의 복잡성에 대해" и 재미와 이익을 위한 고문 데이터베이스. 그들로부터 LMDB의 전례 없는 안정성과 동일한 SQLite에서 이를 능가하는 거의 완벽한 트랜잭션 ACID 속성 구현에 대한 정보를 얻을 수 있습니다.
5. LMDB의 미니멀리즘을 통해 코드의 기계 표현을 결과 속도 특성과 함께 프로세서의 L1 캐시에 완전히 배치할 수 있습니다.

불행히도 iOS에서 메모리 매핑된 파일은 우리가 원하는 만큼 장밋빛이 아닙니다. 그들과 관련된 단점에 대해 더 의식적으로 이야기하려면 운영 체제에서 이 메커니즘을 구현하기 위한 일반 원칙을 상기할 필요가 있습니다.

메모리 매핑된 파일에 대한 일반 정보

실행 가능한 각 응용 프로그램과 함께 운영 체제는 프로세스라는 엔터티를 연결합니다. 각 프로세스에는 작업에 필요한 모든 것을 배치하는 연속된 범위의 주소가 할당됩니다. 최하위 주소에는 코드와 하드코딩된 데이터 및 리소스가 있는 섹션이 포함됩니다. 다음은 상향 성장하는 동적 주소 공간 블록으로, 우리에게 힙으로 잘 알려져 있습니다. 프로그램 작동 중에 나타나는 엔터티의 주소를 포함합니다. 상단에는 애플리케이션 스택에서 사용하는 메모리 영역이 있습니다. 그것은 커지거나 작아지는 것, 즉 그 크기 또한 동적인 성질을 가지고 있습니다. 스택과 힙이 서로 밀고 간섭하지 않도록 주소 공간의 서로 다른 끝에서 분리되며, 위와 아래의 두 동적 섹션 사이에 구멍이 있습니다. 이 중간 섹션의 주소는 운영 체제에서 다양한 엔터티의 프로세스와 연결하는 데 사용됩니다. 특히 특정 연속 주소 집합을 디스크의 파일에 매핑할 수 있습니다. 이러한 파일을 메모리 매핑 파일이라고 합니다.

프로세스에 할당된 주소 공간은 엄청납니다. 이론적으로 주소의 수는 시스템의 비트에 의해 결정되는 포인터의 크기에 의해서만 제한됩니다. 물리적 메모리가 1-in-1에 할당된 경우 첫 번째 프로세스는 전체 RAM을 잡아먹고 멀티태스킹에 대해 의문의 여지가 없습니다.

그러나 최신 운영 체제는 동시에 원하는 만큼 많은 프로세스를 실행할 수 있다는 것을 경험을 통해 알고 있습니다. 이것은 종이에만 프로세스에 많은 메모리를 할당한다는 사실 때문에 가능하지만 실제로는 지금 여기에서 요구되는 부분 만 기본 물리적 메모리에로드합니다. 따라서 프로세스와 관련된 메모리를 가상이라고 합니다.

운영 체제는 가상 및 물리적 메모리를 특정 크기의 페이지로 구성합니다. 가상 메모리의 특정 페이지가 요구되는 즉시 운영 체제는 이를 물리적 메모리에 로드하고 이들 사이의 통신을 특수 테이블에 저장합니다. 사용 가능한 슬롯이 없으면 이전에 로드된 페이지 중 하나가 디스크에 복사되고 요청된 페이지가 그 자리를 차지합니다. 곧 다시 설명할 이 절차를 스와핑이라고 합니다. 아래 그림은 설명된 프로세스를 보여줍니다. 그 위에 주소가 0인 페이지 A가 로드되어 주소가 4인 주 메모리 페이지에 배치되었습니다. 이 사실은 셀 번호 0의 ​​대응표에 반영되었습니다.

메모리 매핑된 파일의 경우 이야기는 정확히 동일합니다. 논리적으로 그들은 가상 주소 공간에 지속적으로 그리고 완전히 배치된다고 가정합니다. 그러나 페이지 단위로 요청 시에만 물리적 메모리에 들어갑니다. 이러한 페이지의 수정은 디스크의 파일과 동기화됩니다. 따라서 단순히 메모리의 바이트로 작업하여 파일 I/O를 수행할 수 있습니다. 모든 변경 사항은 운영 체제 커널에 의해 자동으로 원본 파일로 전송됩니다.
â € <
아래 이미지는 다른 프로세스에서 데이터베이스로 작업할 때 LMDB가 상태를 동기화하는 방법을 보여줍니다. 서로 다른 프로세스의 가상 메모리를 동일한 파일에 매핑함으로써 우리는 사실상 운영 체제가 주소 공간의 특정 블록을 서로 전이적으로 동기화하도록 강제합니다. 여기서 LMDB가 보입니다.
â € <

중요한 차이점은 LMDB가 기본적으로 쓰기 시스템 호출 메커니즘을 통해 데이터 파일을 수정하고 파일 자체가 읽기 전용 모드로 표시된다는 것입니다. 이 접근 방식에는 두 가지 중요한 의미가 있습니다.

첫 번째 결과는 모든 운영 체제에 공통적입니다. 그 본질은 잘못된 코드로 인한 데이터베이스의 부주의한 손상에 대한 보호 기능을 추가하는 것입니다. 아시다시피 프로세스의 실행 가능한 명령은 주소 공간의 어디에서나 데이터에 자유롭게 액세스할 수 있습니다. 동시에 우리가 방금 기억한 것처럼 파일을 읽기-쓰기 모드로 표시한다는 것은 모든 명령이 추가로 파일을 수정할 수 있음을 의미합니다. 예를 들어 실제로 존재하지 않는 인덱스에서 배열 요소를 덮어쓰려고 시도하는 등 실수로 이 작업을 수행하면 이 방법으로 이 주소에 매핑된 파일을 실수로 변경할 수 있으며 이로 인해 데이터베이스가 손상될 수 있습니다. 파일이 읽기 전용 모드로 표시되는 경우 해당 주소 공간을 변경하려고 하면 신호와 함께 프로그램 충돌이 발생합니다. SIGSEGV, 파일은 그대로 유지됩니다.

두 번째 결과는 이미 iOS에만 해당됩니다. 작성자나 다른 출처에서 명시적으로 언급하지 않았지만, 이것이 없으면 LMDB는 이 모바일 운영 체제에서 실행하기에 적합하지 않습니다. 다음 섹션은 이에 대한 고려 사항입니다.

iOS의 메모리 매핑된 파일의 특성

2018년 WWDC에서 멋진 보고가 있었습니다. iOS 메모리 심층 분석. 이는 iOS에서 물리적 메모리에 있는 모든 페이지가 더티(dirty), 압축(compressed) 및 클린(clean)의 3가지 유형 중 하나에 속함을 알려줍니다.

클린 메모리는 물리적 메모리에서 안전하게 교체할 수 있는 페이지 모음입니다. 포함된 데이터는 필요에 따라 원래 소스에서 다시 로드할 수 있습니다. 읽기 전용 메모리 매핑 파일이 이 범주에 속합니다. iOS는 파일에 매핑된 페이지가 디스크의 파일과 동기화되도록 보장되기 때문에 언제든지 메모리에서 파일에 매핑된 페이지를 언로드하는 것을 두려워하지 않습니다.
â € <
수정된 모든 페이지는 원래 위치에 상관없이 더티 메모리에 들어갑니다. 특히 이와 관련된 가상 메모리에 기록하여 수정된 메모리 매핑된 파일도 이러한 방식으로 분류됩니다. 플래그로 LMDB 열기 MDB_WRITEMAP, 변경 후 직접 확인할 수 있습니다.

응용 프로그램이 물리적 메모리를 너무 많이 차지하기 시작하면 iOS는 더티 페이지를 압축합니다. 더티 및 압축 페이지가 차지하는 메모리 모음은 소위 애플리케이션의 메모리 공간입니다. 특정 임계값에 도달하면 OOM 킬러 시스템 데몬이 프로세스 뒤에 와서 강제 종료합니다. 이것은 데스크톱 운영 체제와 비교하여 iOS의 특징입니다. 반면 물리적 메모리에서 디스크로 페이지를 교환하여 메모리 사용량을 줄이는 기능은 iOS에서 제공되지 않으며 그 이유를 추측할 수 있을 뿐입니다. 페이지를 디스크로 집중적으로 이동하는 절차가 모바일 장치에 너무 많은 에너지를 소비하거나 iOS가 SSD 드라이브에 셀을 다시 쓰는 리소스를 절약하거나 설계자가 시스템의 전체 성능에 만족하지 않았을 수 있습니다. 끊임없이 교환했습니다. 사실은 남아 있습니다.

앞서 언급한 좋은 소식은 LMDB가 기본적으로 mmap 메커니즘을 사용하여 파일을 업데이트하지 않는다는 것입니다. 따라서 렌더링된 데이터는 iOS에서 클린 메모리로 분류되며 메모리 공간에 기여하지 않습니다. 이는 VM Tracker라는 Xcode 도구를 사용하여 확인할 수 있습니다. 아래 스크린샷은 작동 중 iOS Cloud 애플리케이션의 가상 메모리 상태를 보여줍니다. 처음에는 2개의 LMDB 인스턴스가 초기화되었습니다. 첫 번째는 파일을 1GiB의 가상 메모리에 매핑할 수 있었고 두 번째는 512MiB였습니다. 두 스토리지 모두 일정량의 상주 메모리를 차지하지만 어느 쪽도 더티 크기에 기여하지 않습니다.

이제 나쁜 소식을 전할 시간입니다. 64비트 데스크톱 운영 체제의 스왑 메커니즘 덕분에 각 프로세스는 잠재적인 스왑을 허용하는 하드 디스크의 여유 공간만큼 가상 주소 공간을 차지할 수 있습니다. iOS에서 스왑을 압축으로 대체하면 이론적 최대값이 크게 줄어듭니다. 이제 모든 활성 프로세스는 기본(읽기 RAM) 메모리에 맞아야 하며 맞지 않는 모든 프로세스는 강제 종료됩니다. 위와 같이 기재되어 있습니다 보고,에서 공식 문서. 결과적으로 iOS는 mmap을 통해 할당할 수 있는 메모리 양을 심각하게 제한합니다. 여기 여기에 이 시스템 호출을 사용하여 다른 장치에 할당할 수 있는 메모리 양에 대한 경험적 한계를 볼 수 있습니다. 가장 현대적인 스마트 폰 모델에서 iOS는 2GB, 상위 버전의 iPad에서는 4GB로 관대 해졌습니다. 물론 실제로는 모든 것이 매우 슬픈 지원되는 가장 어린 장치 모델에 집중해야합니다. 설상가상으로 VM Tracker에서 애플리케이션의 메모리 상태를 보면 LMDB가 메모리 매핑된 메모리를 요구하는 유일한 제품이 아님을 알 수 있습니다. 좋은 청크는 시스템 할당자, 리소스 파일, 이미지 프레임워크 및 기타 작은 약탈자에 의해 잠식됩니다.

클라우드에서의 실험 결과에 따라 LMDB에서 할당한 메모리의 타협 값은 384비트 장치의 경우 32MB, 768비트 장치의 경우 64MB입니다. 이 볼륨이 모두 사용된 후 모든 수정 작업은 코드로 완료되기 시작합니다. MDB_MAP_FULL. 우리는 이러한 오류를 모니터링에서 관찰하지만 현 단계에서 무시할 수 있을 만큼 작습니다.

저장소에서 과도한 메모리를 사용하는 명확하지 않은 이유는 수명이 긴 트랜잭션일 수 있습니다. 이 두 현상이 어떻게 관련되어 있는지 이해하려면 나머지 두 LMDB 고래를 고려하는 것이 도움이 될 것입니다.

3.2. 고래 #2. B+-트리

키-값 저장소 위에 있는 테이블을 에뮬레이트하려면 API에 다음 작업이 있어야 합니다.

1. 새 요소를 삽입합니다.
2. 주어진 키로 요소를 검색합니다.
3. 요소 삭제.
4. 정렬 순서에 따라 키 간격을 반복합니다.

네 가지 작업을 모두 쉽게 구현할 수 있는 가장 간단한 데이터 구조는 이진 검색 트리입니다. 각 노드는 자식 키의 전체 하위 집합을 두 개의 하위 트리로 나누는 키입니다. 왼쪽에는 부모보다 작은 것이 있고 오른쪽에는 큰 것이 있습니다. 정렬된 키 집합을 얻는 것은 고전적인 트리 순회 중 하나를 통해 이루어집니다.

이진 트리에는 디스크 데이터 구조로 효과적이지 못하게 하는 두 가지 근본적인 단점이 있습니다. 첫째, 균형의 정도를 예측할 수 없습니다. 서로 다른 가지의 높이가 크게 다를 수 있는 트리를 얻을 상당한 위험이 있으며, 이는 예상보다 검색의 알고리즘 복잡성을 크게 악화시킵니다. 둘째, 노드 사이의 풍부한 교차 링크는 메모리에서 이진 트리의 위치를 ​​박탈합니다.가까운 노드(둘 사이의 링크 측면에서)는 가상 메모리의 완전히 다른 페이지에 위치할 수 있습니다. 결과적으로 트리에서 여러 인접 노드를 단순 순회하는 경우에도 비슷한 수의 페이지를 방문해야 할 수 있습니다. 프로세서 캐시에서 지속적으로 페이지를 회전시키는 것이 저렴하지 않기 때문에 메모리 내 데이터 구조로서 이진 트리의 효율성에 대해 이야기할 때도 문제가 됩니다. 디스크에서 노드 관련 페이지를 자주 올리면 상황이 정말 나빠집니다. 통탄 할.

이진 트리의 진화인 B-트리는 이전 단락에서 식별된 문제를 해결합니다. 첫째, 그들은 자기 균형을 이루고 있습니다. 둘째, 각 노드는 하위 키 집합을 2가 아니라 M 순서의 하위 집합으로 분할하고 M의 수는 수백 또는 수천 정도로 상당히 클 수 있습니다.

그것에 의하여:

1. 각 노드에는 이미 정렬된 키가 많고 트리가 매우 낮습니다.
2. 트리는 값이 가까운 키가 하나 또는 인접한 노드에서 자연스럽게 서로 옆에 위치하기 때문에 메모리에서 지역성 속성을 얻습니다.
3. 검색 작업 중 트리를 내려갈 때 통과 노드 수를 줄입니다.
4. 각 노드에는 이미 많은 수의 정렬된 키가 포함되어 있으므로 범위 쿼리에 대한 대상 노드 읽기 수를 줄입니다.

LMDB는 B+ 트리라고 하는 B-트리의 변형을 사용하여 데이터를 저장합니다. 위의 다이어그램은 여기에 포함된 세 가지 유형의 노드를 보여줍니다.

1. 맨 위에는 루트가 있습니다. 그것은 저장소 내의 데이터베이스 개념 이상을 구체화하지 않습니다. 단일 LMDB 인스턴스 내에서 매핑된 가상 주소 공간을 공유하는 여러 데이터베이스를 생성할 수 있습니다. 그들 각각은 자신의 뿌리에서 시작합니다.
2. 가장 낮은 수준에는 잎(잎)이 있습니다. 데이터베이스에 저장된 키-값 쌍을 포함하는 것은 바로 그들입니다. 그건 그렇고, 이것이 B+-트리의 특징입니다. 일반 B-트리가 모든 수준의 노드에 값 부분을 저장하는 경우 B+-변형은 가장 낮은 노드에만 있습니다. 이 사실을 수정한 다음에는 LMDB에서 사용되는 트리의 하위 유형을 단순히 B-트리라고 부를 것입니다.
3. 루트와 리프 사이에는 탐색(분기) 노드가 있는 0개 이상의 기술 수준이 있습니다. 그들의 임무는 리프 사이에 정렬된 키 세트를 나누는 것입니다.

물리적으로 노드는 미리 결정된 길이의 메모리 블록입니다. 크기는 위에서 언급한 운영 체제의 메모리 페이지 크기의 배수입니다. 노드 구조는 아래와 같습니다. 헤더에는 메타 정보가 포함되어 있으며, 예를 들어 체크섬이 가장 확실한 정보입니다. 다음은 데이터가 있는 셀이 있는 오프셋에 대한 정보입니다. 데이터의 역할은 탐색 노드에 대해 이야기하는 경우 키이거나 잎의 경우 전체 키-값 쌍일 수 있습니다. 작업에서 페이지 구조에 대해 자세히 읽을 수 있습니다. "고성능 키-값 저장소 평가".

페이지 노드의 내부 콘텐츠를 처리했으므로 다음 형식으로 단순화된 방식으로 LMDB B-트리를 추가로 나타냅니다.

노드가 있는 페이지는 디스크에 순차적으로 배열됩니다. 번호가 높은 페이지는 파일의 끝 부분에 위치합니다. 소위 메타 페이지(meta page)는 모든 트리의 루트를 찾는 데 사용할 수 있는 오프셋에 대한 정보를 포함합니다. 파일이 열리면 LMDB는 유효한 메타 페이지를 찾기 위해 파일을 페이지 단위로 끝에서 처음까지 스캔하고 이를 통해 기존 데이터베이스를 찾습니다.

이제 데이터 구성의 논리적 및 물리적 구조에 대한 아이디어를 가지고 LMDB의 세 번째 고래를 고려할 수 있습니다. 모든 스토리지 수정이 트랜잭션 방식으로 서로 격리되어 발생하여 데이터베이스 전체에 다중 버전 속성을 부여하는 데 도움이 됩니다.

3.3. 고래 #3. 기록 중 복사

일부 B-트리 작업에는 해당 노드에 대한 전체 일련의 변경 작업이 포함됩니다. 한 가지 예는 이미 최대 용량에 도달한 노드에 새 키를 추가하는 것입니다. 이 경우 먼저 노드를 둘로 분할하고 두 번째로 분리된 새 자식 노드에 대한 링크를 부모에 추가해야 합니다. 이 절차는 잠재적으로 매우 위험합니다. 어떤 이유로(충돌, 정전 등) 시리즈의 변경 사항 중 일부만 발생하면 트리가 일관성 없는 상태로 유지됩니다.

데이터베이스를 내결함성으로 만드는 한 가지 기존 솔루션은 추가 디스크 기반 데이터 구조인 트랜잭션 로그(WAL(Write-Ahead Log)라고도 함)를 B-트리 옆에 추가하는 것입니다. B-트리 자체를 수정하기 전에 의도한 작업이 기록되는 파일입니다. 따라서 자가 진단 중에 데이터 손상이 감지되면 데이터베이스는 로그를 참조하여 스스로 정리합니다.

LMDB는 내결함성 메커니즘으로 copy-on-write라고 하는 다른 방법을 선택했습니다. 그 본질은 기존 페이지의 데이터를 업데이트하는 대신 먼저 전체를 복사하고 사본에서 이미 모든 수정을 수행한다는 것입니다.

또한 업데이트된 데이터를 사용할 수 있으려면 관련하여 상위 노드에서 최신이 된 노드로의 링크를 변경해야 합니다. 이를 위한 수정도 필요하므로 미리 복사해둔다. 프로세스는 루트까지 재귀적으로 계속됩니다. 메타 페이지의 데이터는 마지막으로 변경됩니다.

업데이트 절차 중에 프로세스가 갑자기 충돌하면 새 메타 페이지가 생성되지 않거나 끝날 때까지 디스크에 기록되지 않고 체크섬이 올바르지 않습니다. 이 두 경우 중 하나에서 새 페이지에 연결할 수 없으며 이전 페이지는 영향을 받지 않습니다. 이렇게 하면 LMDB가 데이터 일관성을 유지하기 위해 미리 로그를 작성할 필요가 없습니다. 사실상 위에서 설명한 디스크의 데이터 저장 구조는 동시에 그 기능을 수행합니다. 명시적인 트랜잭션 로그가 없는 것은 빠른 데이터 읽기 속도를 제공하는 LMDB의 특징 중 하나입니다.

추가 전용 B-트리라고 하는 결과 구조는 자연스럽게 트랜잭션 격리 및 다중 버전 관리를 제공합니다. LMDB에서 열려 있는 각 트랜잭션에는 연결된 최신 트리 루트가 있습니다. 트랜잭션이 완료되지 않는 한 트랜잭션과 관련된 트리의 페이지는 변경되거나 새로운 버전의 데이터로 재사용되지 않으므로 해당 시점에 관련되었던 데이터 세트로 정확히 원하는 만큼 작업할 수 있습니다. 이 시점에서 저장소가 계속해서 활발하게 업데이트되더라도 트랜잭션이 열린 시간입니다. 이것이 멀티버저닝의 핵심이며, LMDB를 우리 사랑하는 사람에게 이상적인 데이터 소스로 만듭니다. UICollectionView. 트랜잭션을 열면 애플리케이션의 메모리 공간을 늘릴 필요가 없으며 현재 데이터를 메모리 내 구조로 급히 펌핑하여 아무것도 남기지 않을까 두려워합니다. 이 기능은 완전한 격리를 자랑할 수 없는 동일한 SQLite와 LMDB를 구별합니다. 후자에서 두 개의 트랜잭션을 열고 그 중 하나에서 특정 레코드를 삭제하면 두 번째 나머지 트랜잭션에서 동일한 레코드를 더 이상 얻을 수 없습니다.

동전의 이면에는 잠재적으로 훨씬 더 많은 가상 메모리 소비가 있습니다. 슬라이드는 서로 다른 버전의 데이터베이스를 보고 있는 3개의 열린 읽기 트랜잭션과 동시에 수정된 경우 데이터베이스 구조가 어떤 모습인지 보여줍니다. LMDB는 실제 트랜잭션과 연결된 루트에서 도달 가능한 노드를 재사용할 수 없기 때문에 스토리지는 메모리에 또 다른 네 번째 루트를 할당하고 그 아래에 수정된 페이지를 다시 한 번 복제할 수밖에 없습니다.

여기서 메모리 매핑 파일에 대한 섹션을 다시 불러오는 것은 불필요한 일이 아닙니다. 가상 메모리의 추가 소비는 응용 프로그램의 메모리 공간에 기여하지 않기 때문에 우리를 크게 괴롭히지 않아야 합니다. 그러나 동시에 iOS는 할당에 매우 인색하며 서버 또는 데스크톱에서 1테라바이트 LMDB 영역을 마스터의 어깨에서 제공할 수 없으며 이 기능에 대해 전혀 생각하지 않습니다. 가능하면 트랜잭션 수명을 가능한 한 짧게 유지해야 합니다.

4. 키-값 API 위에 데이터 스키마 설계

LMDB에서 제공하는 기본 추상화(환경 및 데이터베이스, 키 및 값, 트랜잭션 및 커서)를 살펴봄으로써 API 구문 분석을 시작하겠습니다.

코드 목록에 대한 참고 사항

LMDB 공개 API의 모든 함수는 작업 결과를 오류 코드 형태로 반환하지만 이후의 모든 목록에서는 간결함을 위해 확인을 생략했습니다.실제로 우리는 자체 코드를 사용하여 저장소와 상호 작용했습니다. 포크 C++ 래퍼 lmdbxx, 여기서 오류는 C++ 예외로 구체화됩니다.

LMDB를 iOS 또는 macOS 프로젝트에 연결하는 가장 빠른 방법으로 CocoaPod를 제공합니다. POSLMDB.

4.1. 기본 추상화

환경

구조 MDB_env is는 LMDB 내부 상태의 저장소입니다. 접두사 함수 제품군 mdb_env 일부 속성을 구성할 수 있습니다. 가장 간단한 경우 엔진 초기화는 다음과 같습니다.

mdb_env_create(env);​
mdb_env_set_map_size(*env, 1024 * 1024 * 512)​
mdb_env_open(*env, path.UTF8String, MDB_NOTLS, 0664);

Mail.ru Cloud 애플리케이션에서 두 개의 매개변수에 대해서만 기본값을 변경했습니다.

첫 번째는 스토리지 파일이 매핑되는 가상 주소 공간의 크기입니다. 불행하게도 동일한 장치에서도 특정 값은 실행마다 크게 다를 수 있습니다. iOS의 이 기능을 고려하여 최대 스토리지 용량을 동적으로 선택합니다. 특정 값에서 시작하여 함수가 될 때까지 연속적으로 반감합니다. mdb_env_open 이외의 결과를 반환하지 않습니다 ENOMEM. 이론적으로는 반대 방법이 있습니다. 먼저 엔진에 최소한의 메모리를 할당한 다음 오류가 수신되면 MDB_MAP_FULL, 늘리십시오. 그러나 훨씬 더 가시적입니다. 그 이유는 함수를 사용하여 메모리를 다시 매핑하는 절차가 mdb_env_set_map_size 이전에 엔진에서 받은 모든 엔터티(커서, 트랜잭션, 키 및 값)를 무효화합니다. 코드에서 이러한 사건의 전환을 설명하면 상당한 복잡성이 발생합니다. 그럼에도 불구하고 가상 메모리가 매우 소중하다면 이것이 훨씬 앞서가는 포크를 살펴봐야 할 이유가 될 수 있습니다. MDBX, 여기서 선언된 기능 중에는 "자동 데이터베이스 크기 조정"이 있습니다.

기본값이 우리에게 적합하지 않은 두 번째 매개 변수는 스레드 안전을 보장하는 메커니즘을 규제합니다. 불행히도 적어도 iOS 10에서는 스레드 로컬 스토리지 지원에 문제가 있습니다. 이러한 이유로 위의 예에서 리포지토리는 플래그와 함께 열립니다. MDB_NOTLS. 또한, 그것은 또한 요구 포크 C++ 래퍼 lmdbxx이 속성을 사용하여 변수를 잘라냅니다.

데이터 베이스

데이터베이스는 위에서 언급한 B-트리의 별도 인스턴스입니다. 처음에는 약간 이상하게 보일 수 있는 트랜잭션 내부에서 열림이 발생합니다.

MDB_txn *txn;​
MDB_dbi dbi;​
mdb_txn_begin(env, NULL, MDB_RDONLY, &txn);​
mdb_dbi_open(txn, NULL, MDB_CREATE, &dbi);​
mdb_txn_abort(txn);

실제로 LMDB의 트랜잭션은 특정 데이터베이스가 아니라 스토리지 엔터티입니다. 이 개념을 사용하면 다른 데이터베이스에 있는 엔터티에 대해 원자적 작업을 수행할 수 있습니다. 이론적으로 이것은 서로 다른 데이터베이스의 형태로 테이블을 모델링할 수 있는 가능성을 열어주지만 한 번에 아래에서 자세히 설명하는 것과 같이 반대 방향으로 이동했습니다.

키와 값

구조 MDB_val 키와 값의 개념을 모델링합니다. 저장소는 의미 체계에 대해 전혀 모릅니다. 그녀에게 다른 것은 주어진 크기의 바이트 배열일 뿐입니다. 최대 키 크기는 512바이트입니다.

typedef struct MDB_val {​
    size_t mv_size;​
    void *mv_data;​
} MDB_val;​​

저장소는 비교기를 사용하여 키를 오름차순으로 정렬합니다. 자신의 것으로 바꾸지 않으면 사전식 순서로 바이트별로 정렬하는 기본 항목이 사용됩니다.

거래

거래 장치는 에 자세히 설명되어 있습니다. 이전 장, 그래서 여기에서 짧은 줄로 주요 속성을 반복합니다.

1. 모든 기본 속성 지원 ACID키워드: 원자성, 일관성, 격리 및 신뢰성. macOS 및 iOS의 내구성 측면에서 MDBX에서 수정된 버그가 있다는 점에 유의하지 않을 수 없습니다. 당신은 그들의에서 더 읽을 수 있습니다 README.
2. 다중 스레딩에 대한 접근 방식은 "단일 작성자/다중 판독기" 방식으로 설명됩니다. 작가는 서로를 차단하지만 독자를 차단하지는 않습니다. 독자는 작가나 서로를 차단하지 않습니다.
3. 중첩 트랜잭션 지원.
4. 다중 버전 지원.

LMDB의 멀티버저닝은 매우 훌륭해서 실제로 시연하고 싶습니다. 아래 코드는 각 트랜잭션이 모든 후속 변경 사항으로부터 완전히 격리된 상태에서 열 때 관련된 데이터베이스 버전과 정확히 작동함을 보여줍니다. 리포지토리를 초기화하고 테스트 레코드를 추가하는 것은 관심이 없으므로 이러한 의식은 스포일러 아래에 있습니다.

테스트 항목 추가

MDB_env *env;
MDB_dbi dbi;
MDB_txn *txn;

mdb_env_create(&env);
mdb_env_open(env, "./testdb", MDB_NOTLS, 0664);

mdb_txn_begin(env, NULL, 0, &txn);
mdb_dbi_open(txn, NULL, 0, &dbi);
mdb_txn_abort(txn);

char k = 'k';
MDB_val key;
key.mv_size = sizeof(k);
key.mv_data = (void *)&k;

int v = 997;
MDB_val value;
value.mv_size = sizeof(v);
value.mv_data = (void *)&v;

mdb_txn_begin(env, NULL, 0, &txn);
mdb_put(txn, dbi, &key, &value, MDB_NOOVERWRITE);
mdb_txn_commit(txn);

MDB_txn *txn1, *txn2, *txn3;
MDB_val val;

// Открываем 2 транзакции, каждая из которых смотрит
// на версию базы данных с одной записью.
mdb_txn_begin(env, NULL, 0, &txn1); // read-write
mdb_txn_begin(env, NULL, MDB_RDONLY, &txn2); // read-only

// В рамках первой транзакции удаляем из базы данных существующую в ней запись.
mdb_del(txn1, dbi, &key, NULL);
// Фиксируем удаление.
mdb_txn_commit(txn1);

// Открываем третью транзакцию, которая смотрит на
// актуальную версию базы данных, где записи уже нет.
mdb_txn_begin(env, NULL, MDB_RDONLY, &txn3);
// Убеждаемся, что запись по искомому ключу уже не существует.
assert(mdb_get(txn3, dbi, &key, &val) == MDB_NOTFOUND);
// Завершаем транзакцию.
mdb_txn_abort(txn3);

// Убеждаемся, что в рамках второй транзакции, открытой на момент
// существования записи в базе данных, её всё ещё можно найти по ключу.
assert(mdb_get(txn2, dbi, &key, &val) == MDB_SUCCESS);
// Проверяем, что по ключу получен не абы какой мусор, а валидные данные.
assert(*(int *)val.mv_data == 997);
// Завершаем транзакцию, работающей хоть и с устаревшей, но консистентной базой данных.
mdb_txn_abort(txn2);

선택적으로 SQLite로 동일한 트릭을 시도하고 어떤 일이 발생하는지 확인하는 것이 좋습니다.

다중 버전 관리는 iOS 개발자의 삶에 매우 좋은 이점을 제공합니다. 이 속성을 사용하면 사용자 경험 고려 사항에 따라 화면 양식에 대한 데이터 소스 업데이트 속도를 쉽고 자연스럽게 조정할 수 있습니다. 예를 들어, 시스템 미디어 갤러리에서 콘텐츠를 자동으로 로드하는 것과 같은 Mail.ru 클라우드 애플리케이션의 기능을 살펴보겠습니다. 연결 상태가 양호하면 클라이언트는 초당 여러 장의 사진을 서버에 추가할 수 있습니다. 다운로드할 때마다 업데이트하는 경우 UICollectionView 사용자의 클라우드에 있는 미디어 콘텐츠를 사용하면 이 프로세스 중에 약 60fps와 부드러운 스크롤을 잊을 수 있습니다. 빈번한 화면 업데이트를 방지하려면 기본적으로 데이터 변경 속도를 어떻게든 제한해야 합니다. UICollectionViewDataSource.

데이터베이스가 다중 버전 관리를 지원하지 않고 현재 상태로만 작업할 수 있도록 허용하는 경우 시간이 안정적인 데이터 스냅샷을 생성하려면 일부 메모리 내 데이터 구조나 임시 테이블에 복사해야 합니다. 이러한 접근 방식 중 하나는 매우 비쌉니다. 인메모리 스토리지의 경우 생성된 객체를 저장함으로써 발생하는 메모리 비용과 중복 ORM 변환과 관련된 시간 비용을 모두 얻습니다. 임시 테이블의 경우 이것은 훨씬 더 비싼 즐거움이며 사소한 경우에만 의미가 있습니다.

멀티버저닝 LMDB는 안정적인 데이터 소스를 유지하는 문제를 매우 우아한 방식으로 해결합니다. 트랜잭션과 짜잔을 여는 것만으로도 충분합니다. 완료할 때까지 데이터 세트는 고정되어 있습니다. 업데이트 속도의 논리는 이제 상당한 리소스의 오버헤드 없이 프레젠테이션 계층의 손에 전적으로 있습니다.

커서

커서는 B-트리를 순회하여 키-값 쌍에 대한 순서대로 반복하는 메커니즘을 제공합니다. 그것들이 없다면 데이터베이스의 테이블을 효과적으로 모델링하는 것이 불가능할 것입니다.

4.2. 테이블 모델링

키 순서 지정 속성을 사용하면 기본 추상화 위에 테이블과 같은 최상위 추상화를 구성할 수 있습니다. 사용자의 모든 파일 및 폴더에 대한 정보가 캐시되는 클라우드 클라이언트의 기본 테이블을 예로 들어 이 프로세스를 살펴보겠습니다.

테이블 스키마

폴더 트리가 있는 테이블의 구조를 선명하게 해야 하는 일반적인 시나리오 중 하나는 지정된 디렉터리 내에 있는 모든 요소를 ​​선택하는 것입니다. 이러한 종류의 효율적인 쿼리를 위한 좋은 데이터 구성 모델은 다음과 같습니다. 인접 목록. 키-값 저장소 위에 구현하려면 파일 및 폴더의 키를 상위 디렉터리에 속하는 것을 기준으로 그룹화하는 방식으로 정렬해야 합니다. 또한 Windows 사용자에게 친숙한 형식으로 디렉토리의 내용을 표시하려면(폴더가 먼저, 파일이 알파벳순으로 정렬됨) 키에 해당하는 추가 필드를 포함해야 합니다.

아래 그림은 작업에 따라 키를 바이트 배열로 표현하는 방법을 보여줍니다. 먼저 상위 디렉터리 식별자(빨간색)가 있는 바이트가 배치되고 그 다음 유형(녹색)이 있는 바이트가 배치되고 이미 이름(파란색)이 있는 테일에 배치됩니다.기본 LMDB 비교기에 의해 사전식 순서로 정렬되므로 필요한 방법. 동일한 빨간색 접두사가 있는 키를 순차적으로 순회하면 추가 사후 처리 없이 사용자 인터페이스(오른쪽)에 표시되어야 하는 순서대로 키와 연결된 값을 제공합니다.

키와 값 직렬화

전 세계적으로 개체를 직렬화하는 방법에는 여러 가지가 있습니다. 우리는 속도 외에 다른 요구 사항이 없었기 때문에 우리는 가장 빠른 것을 선택했습니다 - C 언어 구조의 인스턴스가 차지하는 메모리 덤프. 따라서 디렉토리 요소의 키는 다음 구조로 모델링할 수 있습니다. NodeKey.

typedef struct NodeKey {​
    EntityId parentId;​
    uint8_t type;​
    uint8_t nameBuffer[256];​
} NodeKey;

저장하려면 NodeKey 객체에 스토리지 필요 MDB_val 구조의 시작 주소에 있는 데이터에 대한 포인터를 배치하고 함수를 사용하여 크기를 계산합니다. sizeof.

MDB_val serialize(NodeKey * const key) {
    return MDB_val {
        .mv_size = sizeof(NodeKey),
        .mv_data = (void *)key
    };
}

데이터베이스 선택 기준에 대한 첫 번째 장에서 중요한 선택 요소로 CRUD 작업의 일부로 동적 할당을 최소화하는 것을 언급했습니다. 기능 코드 serialize LMDB의 경우 데이터베이스에 새 레코드가 삽입될 때 완전히 피할 수 있는 방법을 보여줍니다. 서버에서 들어오는 바이트 배열은 먼저 스택 구조로 변환된 다음 저장소에 간단하게 덤프됩니다. LMDB 내부에 동적 할당도 없다는 점을 감안할 때 iOS 표준에 따라 환상적인 상황을 얻을 수 있습니다. 스택 메모리만 사용하여 네트워크에서 디스크까지 데이터 작업을 수행합니다!

이진 비교기로 키 주문

키 순서 관계는 비교기라는 특수 기능에 의해 제공됩니다. 엔진은 포함된 바이트의 의미 체계에 대해 아무것도 모르기 때문에 기본 비교기는 바이트 단위 비교에 의존하여 사전식 순서로 키를 배열할 수밖에 없습니다. 그것을 사용하여 구조를 배열하는 것은 조각 도끼로 면도하는 것과 비슷합니다. 그러나 간단한 경우에는 이 방법을 사용할 수 있습니다. 대안은 아래에 설명되어 있지만 여기서는 길을 따라 흩어져 있는 두 개의 갈퀴에 주목하겠습니다.

가장 먼저 염두에 두어야 할 것은 기본 데이터 유형의 메모리 표현입니다. 따라서 모든 Apple 기기에서 정수 변수는 다음 형식으로 저장됩니다. 리틀 엔디안. 즉, 최하위 바이트가 왼쪽에 있고 바이트 단위 비교를 사용하여 정수를 정렬할 수 없습니다. 예를 들어 0에서 511까지의 숫자 집합으로 이 작업을 시도하면 다음과 같은 결과가 나타납니다.

// value (hex dump)
000 (0000)
256 (0001)
001 (0100)
257 (0101)
...
254 (fe00)
510 (fe01)
255 (ff00)
511 (ff01)

이 문제를 해결하려면 바이트 비교기에 적합한 형식으로 정수를 키에 저장해야 합니다. 가족의 기능은 필요한 변형을 수행하는 데 도움이 될 것입니다. hton* (특히 htons 예에서 XNUMX바이트 숫자의 경우).

프로그래밍에서 문자열을 나타내는 형식은 아시다시피 전체 역사. 문자열의 의미와 메모리에서 문자열을 나타내는 데 사용되는 인코딩이 문자당 XNUMX바이트 이상일 수 있음을 시사하는 경우 기본 비교기를 사용한다는 생각을 즉시 포기하는 것이 좋습니다.

두 번째로 유념해야 할 것은 정렬 원리 구조체 필드 컴파일러. 이로 인해 가비지 값을 가진 바이트가 필드 사이의 메모리에 형성될 수 있으며, 이는 물론 바이트 정렬을 중단합니다. 가비지를 제거하려면 정렬 규칙을 염두에 두고 엄격하게 정의된 순서로 필드를 선언하거나 구조 선언에서 특성을 사용해야 합니다. packed.

외부 비교기에 의한 키 순서

키 비교 논리는 이진 비교기에 비해 너무 복잡할 수 있습니다. 많은 이유 중 하나는 구조물 내부에 기술 분야가 존재하기 때문입니다. 디렉토리 요소에 대해 이미 친숙한 키의 예에서 발생을 설명하겠습니다.

typedef struct NodeKey {​
    EntityId parentId;​
    uint8_t type;​
    uint8_t nameBuffer[256];​
} NodeKey;

모든 단순성을 위해 대부분의 경우 너무 많은 메모리를 소비합니다. 제목 버퍼는 256바이트이지만 평균적으로 파일 및 폴더 이름이 20-30자를 초과하는 경우는 거의 없습니다.

레코드 크기를 최적화하기 위한 표준 기술 중 하나는 실제 크기에 맞게 "잘라내는" 것입니다. 그 본질은 모든 가변 길이 필드의 내용이 구조의 끝에 있는 버퍼에 저장되고 해당 길이는 별도의 변수에 저장된다는 것입니다. NodeKey 아래와 같이 변환됩니다.

typedef struct NodeKey {​
    EntityId parentId;​
    uint8_t type;​
    uint8_t nameLength;​
    uint8_t nameBuffer[256];​
} NodeKey;

또한 직렬화 시에는 데이터 크기를 지정하지 않습니다. sizeof 전체 구조이며 모든 필드의 크기는 고정 길이에 실제로 사용되는 버퍼 부분의 크기를 더한 값입니다.

MDB_val serialize(NodeKey * const key) {
    return MDB_val {
        .mv_size = offsetof(NodeKey, nameBuffer) + key->nameLength,
        .mv_data = (void *)key
    };
}

리팩토링 결과 키가 차지하는 공간을 크게 절약할 수 있었습니다. 그러나 기술 분야로 인해 nameLength, 기본 이진 비교기는 더 이상 키 비교에 적합하지 않습니다. 우리가 그것을 우리 자신의 것으로 바꾸지 않는다면, 이름 자체보다 이름의 길이가 정렬에서 더 우선순위가 되는 요소가 될 것입니다.

LMDB를 사용하면 각 데이터베이스가 고유한 키 비교 기능을 가질 수 있습니다. 이것은 기능을 사용하여 수행됩니다 mdb_set_compare 개봉 전에 엄격히. 분명한 이유로 데이터베이스는 수명 기간 내내 변경할 수 없습니다. 입력에서 비교기는 이진 형식의 두 키를 수신하고 출력에서 ​​비교 결과를 반환합니다: 보다 작음(-1), 보다 큼(1) 또는 같음(0). 의사 코드 NodeKey 그렇게 보인다.

int compare(MDB_val * const a, MDB_val * const b) {​
    NodeKey * const aKey = (NodeKey * const)a->mv_data;​
    NodeKey * const bKey = (NodeKey * const)b->mv_data;​
    return // ...
}​

데이터베이스의 모든 키가 동일한 유형인 한 무조건 바이트 표현을 키의 응용 프로그램 구조 유형으로 캐스팅하는 것이 합법적입니다. 여기에는 한 가지 뉘앙스가 있지만 "기록 읽기" 하위 섹션에서 조금 더 자세히 설명합니다.

값 직렬화

저장된 레코드의 키를 사용하여 LMDB는 매우 집중적으로 작동합니다. 애플리케이션 작업의 프레임워크 내에서 서로 비교되며 전체 솔루션의 성능은 비교기의 속도에 따라 달라집니다. 이상적인 세계에서는 기본 이진 비교기가 키를 비교하기에 충분해야 하지만 실제로 자신의 것을 사용해야 하는 경우에는 키를 역직렬화하는 절차가 가능한 한 빨라야 합니다.

데이터베이스는 레코드의 값 부분(값)에 특별히 관심이 없습니다. 바이트 표현에서 객체로의 변환은 예를 들어 화면에 표시하기 위해 응용 프로그램 코드에서 이미 필요한 경우에만 발생합니다. 이것은 비교적 드물게 발생하기 때문에 이 절차의 속도에 대한 요구 사항은 그다지 중요하지 않으며 구현 시 편의성에 훨씬 더 중점을 둘 수 있습니다 예를 들어 아직 다운로드되지 않은 파일에 대한 메타데이터를 직렬화하려면 다음을 사용합니다. NSKeyedArchiver.

NSData *data = serialize(object);​
MDB_val value = {​
    .mv_size = data.length,​
    .mv_data = (void *)data.bytes​
};

그러나 성능이 중요할 때가 있습니다. 예를 들어 사용자 클라우드의 파일 구조에 대한 메타 정보를 저장할 때 동일한 개체 메모리 덤프를 사용합니다. 직렬화된 표현을 생성하는 작업의 하이라이트는 디렉토리의 요소가 클래스 계층 구조로 모델링된다는 사실입니다.

C 언어로 구현하기 위해 상속인의 특정 필드는 별도의 구조로 가져오고 기본 필드와의 연결은 공용체 유형의 필드를 통해 지정됩니다. 공용체의 실제 내용은 유형 기술 속성을 통해 지정됩니다.

typedef struct NodeValue {​
    EntityId localId;​
    EntityType type;​
    union {​
        FileInfo file;​
        DirectoryInfo directory;​
    } info;​
    uint8_t nameLength;​
    uint8_t nameBuffer[256];​
} NodeValue;​

항목 추가 및 업데이트

직렬화된 키와 값을 저장소에 추가할 수 있습니다. 이를 위해 함수가 사용됩니다. mdb_put.

// key и value имеют тип MDB_val​
mdb_put(..., &key, &value, MDB_NOOVERWRITE);

구성 단계에서 리포지토리가 동일한 키를 가진 여러 레코드를 저장하도록 허용하거나 금지할 수 있습니다. 키 복제가 금지된 경우 레코드를 삽입할 때 이미 존재하는 레코드의 업데이트 허용 여부를 결정할 수 있습니다. 코드 오류의 결과로만 해어짐이 발생할 수 있는 경우 플래그를 지정하여 방지할 수 있습니다. NOOVERWRITE.

기록 읽기

LMDB에서 레코드를 읽는 기능은 mdb_get. 키-값 쌍이 이전에 덤프된 구조로 표시되는 경우 이 절차는 다음과 같습니다.

NodeValue * const readNode(..., NodeKey * const key) {​
    MDB_val rawKey = serialize(key);​
    MDB_val rawValue;​
    mdb_get(..., &rawKey, &rawValue);​
    return (NodeValue * const)rawValue.mv_data;​
}

제시된 목록은 구조 덤프를 통한 직렬화가 어떻게 데이터를 쓸 때뿐만 아니라 읽을 때 동적 할당을 제거할 수 있는지 보여줍니다. 함수에서 파생 mdb_get 포인터는 데이터베이스가 객체의 바이트 표현을 저장하는 가상 메모리 주소를 정확하게 찾습니다. 실제로 우리는 거의 무료로 매우 높은 데이터 읽기 속도를 제공하는 일종의 ORM을 얻습니다. 접근 방식의 모든 아름다움에도 불구하고 이와 관련된 몇 가지 기능을 기억할 필요가 있습니다.

1. 읽기 전용 트랜잭션의 경우 값 구조에 대한 포인터는 트랜잭션이 닫힐 때까지만 유효한 상태로 유지됩니다. 앞에서 언급한 것처럼 개체가 상주하는 B-트리의 페이지는 기록 중 복사 원칙 덕분에 적어도 하나의 트랜잭션이 해당 페이지를 참조하는 한 변경되지 않은 상태로 유지됩니다. 동시에 페이지와 관련된 마지막 트랜잭션이 완료되는 즉시 페이지를 새 데이터에 재사용할 수 있습니다. 개체가 개체를 생성한 트랜잭션에서 유지되어야 하는 경우에도 개체를 복사해야 합니다.
2. 읽기 쓰기 트랜잭션의 경우 결과 구조 값에 대한 포인터는 첫 번째 수정 절차(데이터 쓰기 또는 삭제)까지만 유효합니다.
3. 구조인데도 NodeValue 본격적인 것은 아니지만 잘립니다 ( "외부 비교기에 의한 키 정렬"하위 섹션 참조). 포인터를 통해 해당 필드에 쉽게 액세스 할 수 있습니다. 가장 중요한 것은 그것을 역참조하지 않는 것입니다!
4. 어떤 경우에도 받은 포인터를 통해 구조를 수정할 수 없습니다. 모든 변경은 메소드를 통해서만 이루어져야 합니다. mdb_put. 그러나이 구조가있는 메모리 영역이 읽기 전용 모드로 매핑되기 때문에이 작업을 수행하려는 모든 욕구가 작동하지 않습니다.
5. 예를 들어 함수를 사용하여 최대 저장소 크기를 늘리기 위해 파일을 프로세스의 주소 공간에 다시 매핑합니다. mdb_env_set_map_size 일반적으로 모든 트랜잭션 및 관련 엔터티와 특히 읽기 개체에 대한 포인터를 완전히 무효화합니다.

마지막으로, 한 가지 더 많은 기능이 너무 교활해서 그 본질의 공개가 한 가지 더 많은 점에 맞지 않습니다. B-트리에 관한 장에서 메모리의 페이지 구성에 대한 다이어그램을 제공했습니다. 따라서 직렬화된 데이터가 있는 버퍼의 시작 주소는 절대적으로 임의적일 수 있습니다. 이로 인해 구조에서 얻은 포인터 MDB_val 구조에 대한 포인터로 캐스트하는 것은 일반적으로 정렬되지 않습니다. 동시에 일부 칩의 아키텍처(iOS의 경우 armv7)는 모든 데이터의 주소가 기계어 크기의 배수, 즉 시스템의 비트 수를 요구합니다. (armv7의 경우 32비트임). 즉, 다음과 같은 작업 *(int *foo)0x800002 그들에 대한 탈출과 동일시되며 평결로 처형됩니다. EXC_ARM_DA_ALIGN. 그런 안타까운 운명을 피하는 방법은 두 가지다.

첫 번째는 사전에 알려진 정렬 구조에 데이터를 복사하는 것입니다. 예를 들어 사용자 지정 비교기에서는 다음과 같이 반영됩니다.

int compare(MDB_val * const a, MDB_val * const b) {
    NodeKey aKey, bKey;
    memcpy(&aKey, a->mv_data, a->mv_size);
    memcpy(&bKey, b->mv_data, b->mv_size);
    return // ...
}

다른 방법은 키와 값이 있는 구조가 특성을 사용하여 정렬되지 않을 수 있음을 사전에 컴파일러에 알리는 것입니다. aligned(1). ARM에서는 동일한 효과가 다음과 같을 수 있습니다. 성취하다 그리고 packages 속성을 사용합니다. 구조가 차지하는 공간의 최적화에도 기여한다는 점을 고려하면 이 방법이 바람직해 보이지만 приводит 데이터 액세스 작업 비용을 증가시킵니다.

typedef struct __attribute__((packed)) NodeKey {
    uint8_t parentId;
    uint8_t type;
    uint8_t nameLength;
    uint8_t nameBuffer[256];
} NodeKey;

범위 쿼리

레코드 그룹을 반복하기 위해 LMDB는 커서 추상화를 제공합니다. 우리에게 이미 친숙한 사용자 클라우드 메타데이터가 있는 테이블의 예를 사용하여 작업하는 방법을 살펴보겠습니다.

디렉토리에 있는 파일 목록을 표시하는 과정의 일부로 하위 파일 및 폴더와 관련된 모든 키를 찾아야 합니다. 이전 하위 섹션에서는 키를 정렬했습니다. NodeKey 상위 디렉토리 ID로 먼저 정렬됩니다. 따라서 기술적으로 폴더의 내용을 가져오는 작업은 주어진 접두사가 있는 키 그룹의 위쪽 경계에 커서를 놓고 아래쪽 경계까지 반복하는 것으로 축소됩니다.

순차 검색으로 "이마에서"상한을 찾을 수 있습니다. 이를 위해 커서는 데이터베이스의 전체 키 목록 시작 부분에 배치된 다음 상위 디렉토리 식별자가 있는 키가 그 아래에 나타날 때까지 증가합니다. 이 접근 방식에는 두 가지 명백한 단점이 있습니다.

1. 검색의 선형 복잡성은 아시다시피 일반적으로 트리, 특히 B-트리에서 로그 시간으로 수행할 수 있습니다.
2. 헛되이 원하는 페이지 앞의 모든 페이지가 파일에서 메인 메모리로 올라가는데 이는 매우 비쌉니다.

다행스럽게도 LMDB API는 처음에 커서를 배치하는 효율적인 방법을 제공합니다. 이렇게 하려면 간격의 상한에 있는 키보다 확실히 작거나 같은 키를 형성해야 합니다. . 예를 들어, 위 그림의 목록과 관련하여 필드가 있는 키를 만들 수 있습니다. parentId 2와 같고 나머지는 모두 XNUMX으로 채워집니다. 이러한 부분적으로 채워진 키는 함수의 입력에 공급됩니다. mdb_cursor_get 작동 표시 MDB_SET_RANGE.

NodeKey upperBoundSearchKey = {​
    .parentId = 2,​
    .type = 0,​
    .nameLength = 0​
};​
MDB_val value, key = serialize(upperBoundSearchKey);​
MDB_cursor *cursor;​
mdb_cursor_open(..., &cursor);​
mdb_cursor_get(cursor, &key, &value, MDB_SET_RANGE);

키 그룹의 상한이 발견되면 다른 키와 만나거나 키가 될 때까지 반복합니다. parentId또는 키가 전혀 소모되지 않습니다.

do {​
    rc = mdb_cursor_get(cursor, &key, &value, MDB_NEXT);​
    // processing...​
} while (MDB_NOTFOUND != rc && // check end of table​
         IsTargetKey(key));    // check end of keys group​​

좋은 점은 mdb_cursor_get을 사용하는 반복의 일부로 키뿐만 아니라 값도 얻습니다. 선택 조건을 충족하기 위해 무엇보다도 레코드의 값 부분에서 필드를 확인해야 하는 경우 추가 제스처 없이도 필드에 쉽게 액세스할 수 있습니다.

4.3. 테이블 간의 관계 모델링

지금까지 단일 테이블 데이터베이스 설계 및 작업의 모든 측면을 고려했습니다. 테이블은 동일한 유형의 키-값 쌍으로 구성된 정렬된 레코드 집합이라고 말할 수 있습니다. 키를 사각형으로 표시하고 관련 값을 상자로 표시하면 데이터베이스의 시각적 다이어그램이 표시됩니다.

â € <

그러나 실생활에서 그렇게 적은 양의 피를 흘리는 것은 거의 불가능합니다. 종종 데이터베이스에서 첫 번째로 여러 테이블이 있어야 하고 두 번째로 기본 키와 다른 순서로 테이블에서 선택을 수행해야 합니다. 이 마지막 섹션은 생성 및 상호 연결 문제를 다룹니다.

인덱스 테이블

클라우드 앱에는 "갤러리" 섹션이 있습니다. 전체 클라우드의 미디어 콘텐츠를 날짜별로 정렬하여 표시합니다. 이러한 선택을 최적으로 구현하려면 기본 테이블 옆에 새로운 유형의 키를 사용하여 다른 테이블을 만들어야 합니다. 여기에는 파일이 생성된 날짜가 포함된 필드가 포함되며 이 필드는 기본 정렬 기준으로 사용됩니다. 새 키는 기본 테이블의 키와 동일한 데이터를 참조하므로 인덱스 키라고 합니다. 아래 그림에서 주황색으로 강조 표시되어 있습니다.

동일한 데이터베이스 내에서 다른 테이블의 키를 서로 분리하기 위해 추가 기술 필드 tableId가 모든 테이블에 추가되었습니다. 정렬의 최우선 순위로 지정함으로써 먼저 테이블별로 키를 그룹화하고 이미 자체 규칙에 따라 테이블 내부에 그룹화합니다.

인덱스 키는 기본 키와 동일한 데이터를 참조합니다. 기본 키의 값 부분 복사본을 연결하여 이 속성을 직접 구현하는 것은 한 번에 여러 관점에서 차선책입니다.

1. 점유된 공간의 관점에서 메타데이터는 상당히 풍부할 수 있습니다.
2. 성능 관점에서 보면 노드 메타데이터를 업데이트할 때 두 개의 키를 덮어써야 합니다.
3. 결국 코드 지원의 관점에서 볼 때 키 중 하나의 데이터를 업데이트하는 것을 잊어버리면 스토리지에서 데이터 불일치라는 미묘한 버그가 발생합니다.

다음으로 이러한 단점을 제거하는 방법을 고려할 것입니다.

테이블 간의 관계 구성

이 패턴은 인덱스 테이블을 기본 테이블과 연결하는 데 적합합니다. "값으로서의 키". 이름에서 알 수 있듯이 인덱스 레코드의 값 부분은 기본 키 값의 복사본입니다. 이 접근 방식은 기본 레코드의 값 부분 복사본을 저장하는 것과 관련하여 위에 나열된 모든 단점을 제거합니다. 유일한 요금은 인덱스 키로 값을 가져오려면 데이터베이스에 대해 하나가 아닌 2개의 쿼리를 만들어야 한다는 것입니다. 도식적으로 결과 데이터베이스 스키마는 다음과 같습니다.

테이블 간의 관계를 구성하는 또 다른 패턴은 다음과 같습니다. "중복 키". 그 본질은 정렬이 아닌 관련 키를 재생성하는 데 필요한 추가 속성을 키에 추가하는 것입니다.그러나 Mail.ru 클라우드 응용 프로그램에서 사용하는 실제 예가 있습니다. 특정 iOS 프레임워크의 맥락에서 가상이지만 더 이해하기 쉬운 예를 들겠습니다.

클라우드 모바일 클라이언트에는 사용자가 다른 사람과 공유한 모든 파일 및 폴더를 표시하는 페이지가 있습니다. 그러한 파일이 상대적으로 적고 관련 공개에 대한 구체적인 정보(액세스가 부여된 사람, 권한 등)가 많기 때문에 기본 테이블의 항목입니다. 그러나 이러한 파일을 오프라인으로 표시하려면 여전히 어딘가에 저장해야 합니다. 자연스러운 해결책은 별도의 테이블을 만드는 것입니다. 아래 다이어그램에서 해당 키는 "P" 접두사가 붙고 "propname" 자리 표시자는 보다 구체적인 값인 "public info"로 대체될 수 있습니다.

새 테이블이 생성된 모든 고유 메타데이터는 레코드의 값 부분으로 이동됩니다. 동시에 기본 테이블에 이미 저장된 파일 및 폴더에 대한 데이터를 복제하고 싶지 않습니다. 대신 중복 데이터가 "노드 ID" 및 "타임스탬프" 필드 형식으로 "P" 키에 추가됩니다. 덕분에 기본 키를 얻을 수 있는 인덱스 키를 구성할 수 있으며, 이를 통해 최종적으로 노드의 메타데이터를 얻을 수 있습니다.

결론

LMDB 구축 결과를 긍정적으로 평가한다. 그 후 애플리케이션 정지 횟수가 30% 감소했습니다.

수행한 작업 결과 iOS 팀 외부에서 응답을 찾았습니다. 현재 Android 애플리케이션의 기본 "파일" 섹션 중 하나도 LMDB를 사용하도록 전환되었으며 다른 부분도 진행 중입니다. 키-값 저장소가 구현된 C 언어는 초기에 C++ 언어로 교차 플랫폼을 중심으로 애플리케이션 바인딩을 만드는 데 좋은 도움이 되었습니다. 결과 C ++ 라이브러리를 Objective-C 및 Kotlin의 플랫폼 코드와 원활하게 연결하기 위해 코드 생성기가 사용되었습니다. 진니 하지만 그건 또 다른 이야기입니다.

출처 : habr.com