Vào mùa thu năm 2019, một sự kiện được chờ đợi từ lâu đã diễn ra trong nhóm Mail.ru Cloud iOS. Cơ sở dữ liệu chính để lưu trữ liên tục trạng thái ứng dụng đã trở nên khá kỳ lạ đối với thế giới di động Cơ sở dữ liệu ánh xạ bộ nhớ Lightning (LMĐB). Dưới phần cắt giảm, sự chú ý của bạn được mời đến phần đánh giá chi tiết của nó trong bốn phần. Đầu tiên, hãy nói về những lý do cho một sự lựa chọn không tầm thường và khó khăn như vậy. Sau đó, hãy chuyển sang xem xét ba con cá voi ở trung tâm của kiến ​​trúc LMDB: tệp ánh xạ bộ nhớ, cây B +, phương pháp sao chép khi ghi để triển khai giao dịch và đa phiên bản. Cuối cùng, cho món tráng miệng - phần thực hành. Trong đó, chúng ta sẽ xem xét cách thiết kế và triển khai một lược đồ cơ sở với một số bảng, bao gồm một bảng chỉ mục, bên trên API khóa-giá trị cấp thấp.​

nội dung

1. Động lực thực hiện
2. Định vị LMDB
3. Ba chú cá voi LMDB
   3.1. Cá voi #1. Tệp ánh xạ bộ nhớ
   3.2. Cá voi #2. B+-cây
   3.3. Cá voi #3. sao chép trên ghi
4. Thiết kế lược đồ dữ liệu trên API khóa-giá trị
   4.1. trừu tượng cơ bản
   4.2. Lập mô hình bảng
   4.3. Mô hình hóa mối quan hệ giữa các bảng

1. Động cơ thực hiện

Mỗi năm một lần, vào năm 2015, chúng tôi quan tâm đến việc đo lường tần suất giao diện ứng dụng của chúng tôi bị trễ. Chúng tôi không chỉ làm điều này. Chúng tôi ngày càng có nhiều phàn nàn về việc đôi khi ứng dụng ngừng phản hồi các thao tác của người dùng: các nút không được nhấn, danh sách không cuộn, v.v. Giới thiệu về cơ chế đo lường kể lại trên AvitoTech, vì vậy ở đây tôi chỉ đưa ra thứ tự các số.

Các kết quả đo lường đã trở thành một cơn mưa lạnh đối với chúng tôi. Hóa ra các vấn đề do đóng băng gây ra nhiều hơn bất kỳ vấn đề nào khác. Nếu trước khi nhận ra thực tế này, chỉ số kỹ thuật chính về chất lượng không bị lỗi, thì sau khi tập trung chuyển trên đóng băng miễn phí.

đã xây dựng bảng điều khiển với đóng băng và đã trải qua định lượng и chất lượng phân tích nguyên nhân của chúng, kẻ thù chính đã trở nên rõ ràng - logic nghiệp vụ nặng nề thực thi trong luồng chính của ứng dụng. Một phản ứng tự nhiên đối với sự ô nhục này là mong muốn cháy bỏng được đẩy nó vào dòng công việc. Để có giải pháp có hệ thống cho vấn đề này, chúng tôi đã sử dụng kiến ​​trúc đa luồng dựa trên các tác nhân nhẹ. Tôi dành riêng những bản chuyển thể của cô ấy cho thế giới iOS hai chủ đề trong twitter tập thể và Bài viết trên Habre. Là một phần của câu chuyện hiện tại, tôi muốn nhấn mạnh những khía cạnh của quyết định đã ảnh hưởng đến việc lựa chọn cơ sở dữ liệu.​

Mô hình diễn viên của tổ chức hệ thống giả định rằng đa luồng trở thành bản chất thứ hai của nó. Các đối tượng mô hình trong đó muốn vượt qua ranh giới luồng. Và họ làm điều này không phải đôi khi và ở một số nơi, mà hầu như liên tục và ở mọi nơi.

​Cơ sở dữ liệu là một trong những thành phần nền tảng trong sơ đồ được trình bày. Nhiệm vụ chính của nó là triển khai một mẫu macro Cơ sở dữ liệu dùng chung. Nếu trong thế giới doanh nghiệp, nó được sử dụng để tổ chức đồng bộ hóa dữ liệu giữa các dịch vụ, thì trong trường hợp kiến ​​trúc diễn viên, dữ liệu giữa các luồng. Vì vậy, chúng tôi cần một cơ sở dữ liệu như vậy, làm việc với nó trong môi trường đa luồng không gây ra những khó khăn dù chỉ là nhỏ nhất. Cụ thể, điều này có nghĩa là các đối tượng bắt nguồn từ nó ít nhất phải an toàn cho luồng và lý tưởng nhất là không thể thay đổi được. Như bạn đã biết, cái sau có thể được sử dụng đồng thời từ một số luồng mà không cần dùng đến bất kỳ loại khóa nào, điều này có tác dụng có lợi cho hiệu suất.

Yếu tố quan trọng thứ hai ảnh hưởng đến việc lựa chọn cơ sở dữ liệu là API đám mây của chúng tôi. Nó được lấy cảm hứng từ cách tiếp cận git để đồng bộ hóa. Giống như anh ấy, chúng tôi nhắm đến API ngoại tuyến đầu tiên, có vẻ phù hợp hơn cho máy khách trên đám mây. Người ta cho rằng họ sẽ chỉ bơm toàn bộ trạng thái của đám mây một lần và sau đó đồng bộ hóa trong phần lớn các trường hợp sẽ xảy ra thông qua các thay đổi luân phiên. Than ôi, khả năng này vẫn chỉ nằm trong vùng lý thuyết và trên thực tế, khách hàng chưa học cách làm việc với các bản vá. Có một số lý do khách quan cho việc này, để không làm chậm phần giới thiệu, chúng tôi sẽ bỏ qua phần mở rộng. Bây giờ thú vị hơn nhiều là kết quả hướng dẫn của bài học về điều gì sẽ xảy ra khi API nói "A" và người tiêu dùng của nó không nói "B".

Vì vậy, nếu bạn tưởng tượng git, khi thực hiện lệnh kéo, thay vì áp dụng các bản vá cho ảnh chụp nhanh cục bộ, sẽ so sánh trạng thái đầy đủ của nó với trạng thái đầy đủ của máy chủ, thì bạn sẽ có một ý tưởng khá chính xác về cách đồng bộ hóa xảy ra trong máy khách đám mây. Có thể dễ dàng đoán rằng để triển khai, cần phân bổ hai cây DOM trong bộ nhớ với siêu thông tin về tất cả các tệp máy chủ và tệp cục bộ. Nó chỉ ra rằng nếu người dùng lưu trữ 500 nghìn tệp trên đám mây, thì để đồng bộ hóa nó, cần phải tạo lại và phá hủy hai cây với 1 triệu nút. Nhưng mỗi nút là một tập hợp chứa một đồ thị của các đối tượng con. Trong ánh sáng này, kết quả hồ sơ đã được mong đợi. Hóa ra là ngay cả khi không tính đến thuật toán hợp nhất, chính quy trình tạo và sau đó hủy một số lượng lớn các đối tượng nhỏ cũng tiêu tốn một khoản tiền khá lớn. của tập lệnh người dùng. Do đó, chúng tôi khắc phục tiêu chí quan trọng thứ hai trong việc chọn cơ sở dữ liệu - khả năng thực hiện các thao tác CRUD mà không cần phân bổ động các đối tượng.

Các yêu cầu khác mang tính truyền thống hơn và danh sách đầy đủ của chúng như sau.

1. Chủ đề an toàn.
2. đa xử lý. Được quyết định bởi mong muốn sử dụng cùng một phiên bản cơ sở dữ liệu để đồng bộ hóa trạng thái không chỉ giữa các luồng mà còn giữa ứng dụng chính và tiện ích mở rộng iOS.
3. Khả năng biểu diễn các thực thể được lưu trữ dưới dạng các đối tượng không thể thay đổi.​
4. Thiếu phân bổ động trong các hoạt động CRUD.
5. Hỗ trợ giao dịch cho các thuộc tính cơ bản ACIDTừ khóa: tính nguyên tử, nhất quán, cô lập và độ tin cậy.
6. Tốc độ trên các trường hợp phổ biến nhất.

Với tập hợp các yêu cầu này, SQLite đã và vẫn là một lựa chọn tốt. Tuy nhiên, trong quá trình nghiên cứu các lựa chọn thay thế, tôi tình cờ đọc được một cuốn sách "Bắt đầu với LevelDB". Dưới sự lãnh đạo của cô ấy, một điểm chuẩn đã được viết để so sánh tốc độ làm việc với các cơ sở dữ liệu khác nhau trong các tình huống đám mây thực. Kết quả vượt quá mong đợi hoang dã nhất. Trong các trường hợp phổ biến nhất - nhận con trỏ trên danh sách được sắp xếp của tất cả các tệp và danh sách được sắp xếp của tất cả các tệp cho một thư mục nhất định - LMDB hóa ra nhanh hơn SQLite 10 lần. Sự lựa chọn trở nên rõ ràng.

2. Định vị LMDB

LMDB là một thư viện, rất nhỏ (chỉ 10 nghìn dòng) triển khai lớp cơ sở dữ liệu cơ bản thấp nhất - lưu trữ.

Sơ đồ trên cho thấy rằng việc so sánh LMDB với SQLite, thực hiện các cấp độ cao hơn, thường không đúng hơn SQLite với Dữ liệu lõi. Sẽ công bằng hơn nếu trích dẫn các công cụ lưu trữ giống nhau như các đối thủ cạnh tranh ngang nhau - BerkeleyDB, LevelDB, Sophia, RocksDB, v.v. Thậm chí có những phát triển trong đó LMDB hoạt động như một thành phần công cụ lưu trữ cho SQLite. Thí nghiệm đầu tiên như vậy vào năm 2012 bỏ ra tác giả LMDB Howard Chu. Những phát hiện hóa ra lại hấp dẫn đến mức sáng kiến ​​của anh ấy đã được những người đam mê PMNM đón nhận và thấy nó được tiếp tục khi đối mặt với LumoSQL. Vào tháng 2020 năm XNUMX, tác giả của dự án này là Den Shearer trình bày nó trên LinuxConfAu.

Công dụng chính của LMDB là làm công cụ cho cơ sở dữ liệu ứng dụng. Thư viện có được sự xuất hiện của nó đối với các nhà phát triển OpenLDAP, những người rất không hài lòng với BerkeleyDB làm nền tảng cho dự án của họ. Đẩy ra khỏi thư viện khiêm tốn cây btree, Howard Chu đã có thể tạo ra một trong những lựa chọn thay thế phổ biến nhất trong thời đại chúng ta. Anh ấy đã dành bản báo cáo rất hay của mình cho câu chuyện này, cũng như cho cấu trúc bên trong của LMDB. "Cơ sở dữ liệu ánh xạ bộ nhớ Lightning". Leonid Yuriev (hay còn gọi là yeo) từ Positive Technologies trong bài nói chuyện của anh ấy tại Highload 2015 "Công cụ LMDB là một nhà vô địch đặc biệt". Trong đó, anh ấy nói về LMDB trong bối cảnh nhiệm vụ tương tự là triển khai ReOpenLDAP và LevelDB đã trải qua những lời chỉ trích so sánh. Kết quả của việc triển khai, Công nghệ tích cực thậm chí còn có một ngã ba đang phát triển tích cực MDBX với các tính năng rất ngon, tối ưu hóa và Sửa lỗi.

LMDB cũng thường được sử dụng làm bộ lưu trữ. Ví dụ, trình duyệt Mozilla Firefox đã chọn nó cho một số nhu cầu, và bắt đầu từ phiên bản 9, Xcode ưa thích SQLite của nó để lưu trữ các chỉ mục.

Công cụ này cũng được chú ý trong thế giới phát triển di động. Dấu vết của việc sử dụng nó có thể được tìm trong ứng dụng khách iOS cho Telegram. LinkedIn đã tiến thêm một bước và chọn LMDB làm bộ lưu trữ mặc định cho khung bộ nhớ đệm dữ liệu cây nhà lá vườn của mình, Rocket Data. kể lại trong một bài báo năm 2016.

LMDB đang tranh giành thành công một vị trí trong thị trường ngách do BerkeleyDB để lại sau quá trình chuyển đổi dưới sự kiểm soát của Oracle. Thư viện được yêu thích vì tốc độ và độ tin cậy của nó, ngay cả khi so với các loại thư viện cùng loại. Như bạn đã biết, không có bữa trưa miễn phí và tôi muốn nhấn mạnh sự đánh đổi mà bạn sẽ phải đối mặt khi lựa chọn giữa LMDB và SQLite. Sơ đồ trên minh họa rõ ràng làm thế nào để đạt được tốc độ tăng lên. Đầu tiên, chúng tôi không trả tiền cho các lớp trừu tượng bổ sung trên bộ lưu trữ đĩa. Tất nhiên, trong một kiến ​​​​trúc tốt, bạn vẫn không thể thiếu chúng và chắc chắn chúng sẽ xuất hiện trong mã ứng dụng, nhưng chúng sẽ mỏng hơn nhiều. Chúng sẽ không có các tính năng không được yêu cầu bởi một ứng dụng cụ thể, chẳng hạn như hỗ trợ cho các truy vấn bằng ngôn ngữ SQL. Thứ hai, có thể triển khai tối ưu việc ánh xạ các hoạt động của ứng dụng tới các yêu cầu lưu trữ trên đĩa. Nếu SQLite trong công việc của tôi xuất phát từ nhu cầu trung bình của một ứng dụng trung bình, thì bạn, với tư cách là nhà phát triển ứng dụng, nhận thức rõ về các tình huống tải chính. Để có giải pháp hiệu quả hơn, bạn sẽ phải trả mức giá cao hơn cho cả việc phát triển giải pháp ban đầu và hỗ trợ tiếp theo.

3. Ba con cá voi LMDB

Sau khi xem xét LMDB từ góc nhìn toàn cảnh, đã đến lúc tìm hiểu sâu hơn. Ba phần tiếp theo sẽ được dành cho việc phân tích các cá voi chính mà kiến ​​trúc lưu trữ dựa trên:

1. Các tệp ánh xạ bộ nhớ như một cơ chế để làm việc với đĩa và đồng bộ hóa các cấu trúc dữ liệu bên trong.
2. B+-tree là một tổ chức của cấu trúc dữ liệu được lưu trữ.
3. Copy-on-write như một cách tiếp cận để cung cấp các thuộc tính giao dịch ACID và đa phiên bản.

3.1. Cá voi #1. Tệp ánh xạ bộ nhớ

Các tệp ánh xạ bộ nhớ là một thành phần kiến ​​trúc quan trọng đến nỗi chúng thậm chí còn xuất hiện trong tên của kho lưu trữ. Các vấn đề về bộ nhớ đệm và đồng bộ hóa quyền truy cập vào thông tin được lưu trữ hoàn toàn do hệ điều hành quyết định. LMDB không chứa bất kỳ bộ đệm nào trong chính nó. Đây là một quyết định có ý thức của tác giả, vì việc đọc dữ liệu trực tiếp từ các tệp được ánh xạ cho phép bạn cắt giảm rất nhiều góc trong quá trình triển khai công cụ. Dưới đây là một xa danh sách đầy đủ của một số trong số họ.

1. Việc duy trì tính nhất quán của dữ liệu trong bộ lưu trữ khi làm việc với nó từ một số quy trình trở thành trách nhiệm của hệ điều hành. Trong phần tiếp theo, cơ chế này được thảo luận chi tiết và có hình ảnh.
2. Việc không có bộ đệm sẽ loại bỏ hoàn toàn LMDB khỏi chi phí hoạt động liên quan đến phân bổ động. Đọc dữ liệu trong thực tế là đặt con trỏ tới đúng địa chỉ trong bộ nhớ ảo và không có gì khác. Nghe có vẻ viển vông, nhưng trong nguồn kho lưu trữ, tất cả các lệnh gọi calloc đều tập trung ở chức năng cấu hình kho lưu trữ.
3. Việc không có bộ đệm cũng có nghĩa là không có khóa liên quan đến đồng bộ hóa để truy cập chúng. Người đọc, trong đó có thể tồn tại một số tùy ý cùng một lúc, không gặp phải một đột biến nào trên đường đến dữ liệu. Do đó, tốc độ đọc có khả năng mở rộng tuyến tính lý tưởng về số lượng CPU. Trong LMDB, chỉ các hoạt động sửa đổi mới được đồng bộ hóa. Chỉ có thể có một nhà văn tại một thời điểm.
4. Tối thiểu bộ nhớ đệm và logic đồng bộ hóa giúp lưu mã khỏi một loại lỗi cực kỳ phức tạp liên quan đến hoạt động trong môi trường đa luồng. Có hai nghiên cứu cơ sở dữ liệu thú vị tại hội nghị Usenix OSDI 2014: "Tất cả các hệ thống tệp không được tạo ra như nhau: Về mức độ phức tạp của việc chế tạo các ứng dụng nhất quán với sự cố" и Tra tấn cơ sở dữ liệu để giải trí và kiếm lợi nhuận. Từ chúng, bạn có thể nhận thông tin về cả độ tin cậy chưa từng có của LMDB và việc triển khai gần như hoàn hảo các thuộc tính ACID của các giao dịch, vượt qua nó trong cùng một SQLite.
5. Tính tối giản của LMDB cho phép máy đại diện cho mã của nó được đặt hoàn toàn trong bộ đệm L1 của bộ xử lý với các đặc tính tốc độ thu được.

Thật không may, trong iOS, các tệp ánh xạ bộ nhớ không có màu hồng như chúng ta mong muốn. Để nói về những bất lợi liên quan đến chúng một cách có ý thức hơn, cần phải nhớ lại các nguyên tắc chung để thực hiện cơ chế này trong các hệ điều hành.

Thông tin chung về các tệp ánh xạ bộ nhớ

Với mỗi ứng dụng thực thi, hệ điều hành liên kết với một thực thể được gọi là quy trình. Mỗi quá trình được phân bổ một dải địa chỉ liền kề, trong đó nó đặt mọi thứ nó cần để hoạt động. Các địa chỉ thấp nhất chứa các phần có mã và dữ liệu và tài nguyên được mã hóa cứng. Tiếp đến là khối không gian địa chỉ động ngày càng phát triển, chúng tôi thường gọi là heap. Nó chứa địa chỉ của các thực thể xuất hiện trong quá trình hoạt động của chương trình. Trên cùng là vùng bộ nhớ được sử dụng bởi ngăn xếp ứng dụng. Nó lớn lên hoặc thu nhỏ lại, nói cách khác, kích thước của nó cũng có tính chất động. Để ngăn xếp và heap không đẩy và can thiệp lẫn nhau, chúng được phân tách ở các đầu khác nhau của không gian địa chỉ.Có một lỗ hổng giữa hai phần động ở trên cùng và dưới cùng. Các địa chỉ trong phần giữa này được hệ điều hành sử dụng để liên kết với một quá trình gồm nhiều thực thể khác nhau. Đặc biệt, nó có thể ánh xạ một bộ địa chỉ liên tục nhất định vào một tệp trên đĩa. Tệp như vậy được gọi là tệp ánh xạ bộ nhớ.​

Không gian địa chỉ được phân bổ cho một quá trình là rất lớn. Về mặt lý thuyết, số lượng địa chỉ chỉ bị giới hạn bởi kích thước của con trỏ, được xác định bởi độ bit của hệ thống. Nếu bộ nhớ vật lý được gán cho nó 1 trong 1, thì quy trình đầu tiên sẽ ngấu nghiến toàn bộ RAM và sẽ không có vấn đề gì về bất kỳ tác vụ đa nhiệm nào.​

​Tuy nhiên, chúng tôi biết từ kinh nghiệm rằng các hệ điều hành hiện đại có thể chạy nhiều quy trình như bạn muốn cùng một lúc. Điều này có thể là do chúng chỉ phân bổ nhiều bộ nhớ cho các quy trình trên giấy, nhưng trên thực tế, chúng chỉ tải vào bộ nhớ vật lý chính phần được yêu cầu ở đây và bây giờ. Do đó, bộ nhớ liên quan đến quy trình được gọi là ảo.

Hệ điều hành tổ chức bộ nhớ ảo và vật lý thành các trang có kích thước nhất định. Ngay khi một trang bộ nhớ ảo nào đó được yêu cầu, hệ điều hành sẽ tải nó vào bộ nhớ vật lý và đặt sự tương ứng giữa chúng trong một bảng đặc biệt. Nếu không có chỗ trống, thì một trong những trang đã tải trước đó sẽ được sao chép vào đĩa và trang được yêu cầu sẽ thế chỗ. Quy trình này, mà chúng ta sẽ quay lại ngay sau đây, được gọi là hoán đổi. Hình dưới đây minh họa quá trình được mô tả. Trên đó, trang A có địa chỉ 0 đã được tải và đặt trên trang bộ nhớ chính có địa chỉ 4. Thực tế này được phản ánh trong bảng tương ứng ở ô số 0.​

Với các tệp ánh xạ bộ nhớ, câu chuyện hoàn toàn giống nhau. Về mặt logic, chúng được cho là liên tục và hoàn toàn được đặt trong không gian địa chỉ ảo. Tuy nhiên, chúng vào bộ nhớ vật lý theo từng trang và chỉ khi có yêu cầu. Việc sửa đổi các trang đó được đồng bộ hóa với tệp trên đĩa. Như vậy, bạn có thể thực hiện thao tác vào/ra tệp, thao tác đơn giản với byte trong bộ nhớ - mọi thay đổi sẽ được nhân hệ điều hành tự động chuyển sang tệp gốc.​
â € <
Hình ảnh bên dưới minh họa cách LMDB đồng bộ hóa trạng thái của nó khi làm việc với cơ sở dữ liệu từ các quy trình khác nhau. Bằng cách ánh xạ bộ nhớ ảo của các quy trình khác nhau vào cùng một tệp, trên thực tế, chúng tôi bắt buộc hệ điều hành phải đồng bộ hóa tạm thời các khối không gian địa chỉ nhất định của chúng với nhau, đó là nơi LMDB tìm kiếm.​
â € <

Một sắc thái quan trọng là LMDB sửa đổi tệp dữ liệu theo mặc định thông qua cơ chế gọi hệ thống ghi và bản thân tệp sẽ hiển thị ở chế độ chỉ đọc. Cách tiếp cận này có hai ý nghĩa quan trọng.

Hậu quả đầu tiên là chung cho tất cả các hệ điều hành. Bản chất của nó là bổ sung khả năng bảo vệ chống lại thiệt hại do sơ ý đối với cơ sở dữ liệu do mã không chính xác. Như bạn đã biết, các hướng dẫn thực thi của một quy trình được tự do truy cập dữ liệu từ bất kỳ đâu trong không gian địa chỉ của nó. Đồng thời, như chúng ta vừa nhớ, hiển thị một tệp ở chế độ đọc-ghi có nghĩa là bất kỳ hướng dẫn nào cũng có thể sửa đổi nó. Nếu cô ấy làm điều này do nhầm lẫn, chẳng hạn như cố gắng thực sự ghi đè lên một phần tử mảng tại một chỉ mục không tồn tại, thì theo cách này, cô ấy có thể vô tình thay đổi tệp được ánh xạ tới địa chỉ này, điều này sẽ dẫn đến hỏng cơ sở dữ liệu. Nếu tệp được hiển thị ở chế độ chỉ đọc, thì nỗ lực thay đổi không gian địa chỉ tương ứng với nó sẽ dẫn đến sự cố chương trình với tín hiệu SIGSEGV, và tệp sẽ vẫn còn nguyên vẹn.

Hệ quả thứ hai đã dành riêng cho iOS. Cả tác giả và bất kỳ nguồn nào khác đều không đề cập rõ ràng đến nó, nhưng nếu không có nó, LMDB sẽ không phù hợp để chạy trên hệ điều hành di động này. Phần tiếp theo được dành cho việc xem xét nó.

Chi tiết cụ thể về tệp ánh xạ bộ nhớ trong iOS

Năm 2018, đã có một báo cáo tuyệt vời tại WWDC Tìm hiểu sâu về bộ nhớ iOS. Nó cho biết rằng trong iOS, tất cả các trang nằm trong bộ nhớ vật lý thuộc một trong 3 loại: bẩn, nén và sạch.

Bộ nhớ sạch là tập hợp các trang có thể được tráo đổi một cách an toàn khỏi bộ nhớ vật lý. Dữ liệu mà chúng chứa có thể được tải lại từ các nguồn gốc của chúng nếu cần. Các tệp ánh xạ bộ nhớ chỉ đọc thuộc loại này. iOS không ngại dỡ các trang được ánh xạ tới một tệp khỏi bộ nhớ bất kỳ lúc nào, vì chúng được đảm bảo sẽ được đồng bộ hóa với tệp trên đĩa.
â € <
Tất cả các trang đã sửa đổi đều đi vào bộ nhớ bẩn, bất kể vị trí ban đầu của chúng. Cụ thể, các tệp ánh xạ bộ nhớ được sửa đổi bằng cách ghi vào bộ nhớ ảo được liên kết với chúng cũng sẽ được phân loại theo cách này. Mở LMDB bằng cờ MDB_WRITEMAP, sau khi thực hiện các thay đổi đối với nó, bạn có thể tự mình xem.​

​Ngay khi một ứng dụng bắt đầu chiếm quá nhiều bộ nhớ vật lý, iOS sẽ nén các trang bẩn của ứng dụng đó. Tập hợp bộ nhớ bị chiếm bởi các trang bẩn và nén được gọi là dấu chân bộ nhớ của ứng dụng. Khi nó đạt đến một giá trị ngưỡng nhất định, trình nền hệ thống sát thủ OOM sẽ xuất hiện sau quá trình và buộc chấm dứt nó. Đây là điểm đặc thù của iOS so với các hệ điều hành máy tính để bàn. Ngược lại, việc giảm dung lượng bộ nhớ bằng cách hoán đổi các trang từ bộ nhớ vật lý sang đĩa không được cung cấp trong iOS. Có lẽ quy trình di chuyển mạnh các trang vào đĩa và ngược lại quá tốn năng lượng đối với thiết bị di động hoặc iOS tiết kiệm tài nguyên ghi lại các ô trên ổ SSD hoặc có thể các nhà thiết kế không hài lòng với hiệu suất tổng thể của hệ thống, nơi mọi thứ đều hoán đổi liên tục. Hãy là như nó có thể, thực tế vẫn còn.

Tin vui, đã được đề cập trước đó, là LMDB không sử dụng cơ chế mmap để cập nhật tệp theo mặc định. Theo đó, dữ liệu được hiển thị được iOS phân loại là bộ nhớ sạch và không đóng góp vào dung lượng bộ nhớ. Điều này có thể được xác minh bằng công cụ Xcode có tên VM Tracker. Ảnh chụp màn hình bên dưới hiển thị trạng thái bộ nhớ ảo của ứng dụng iOS Cloud trong quá trình hoạt động. Khi bắt đầu, 2 phiên bản LMDB đã được khởi tạo trong đó. Cái đầu tiên được phép ánh xạ tệp của nó tới 1GiB bộ nhớ ảo, cái thứ hai - 512MiB. Mặc dù thực tế là cả hai kho lưu trữ đều chiếm một lượng bộ nhớ lưu trú nhất định, nhưng cả hai kho lưu trữ đều không góp phần vào kích thước bẩn.

Bây giờ là lúc cho những tin xấu. Nhờ cơ chế trao đổi trong hệ điều hành máy tính để bàn 64 bit, mỗi quy trình có thể chiếm nhiều không gian địa chỉ ảo vì không gian trống trên đĩa cứng cho phép trao đổi tiềm năng của nó. Thay thế trao đổi bằng nén trong iOS làm giảm đáng kể mức tối đa theo lý thuyết. Giờ đây, tất cả các quy trình đang hoạt động phải vừa với bộ nhớ chính (RAM đã đọc) và tất cả những quy trình không phù hợp đều có thể bị buộc chấm dứt. Nó được đề cập như ở trên báo cáovà trong tài liệu chính thức. Do đó, iOS giới hạn nghiêm ngặt dung lượng bộ nhớ khả dụng để phân bổ qua mmap. Đây đây bạn có thể xem các giới hạn thực nghiệm về dung lượng bộ nhớ có thể được phân bổ trên các thiết bị khác nhau bằng lệnh gọi hệ thống này. Trên các mẫu điện thoại thông minh hiện đại nhất, iOS đã trở nên hào phóng với 2 gigabyte và trên các phiên bản hàng đầu của iPad - 4. Trên thực tế, tất nhiên, bạn phải tập trung vào các mẫu thiết bị được hỗ trợ trẻ nhất, nơi mọi thứ đều rất buồn. Tệ hơn nữa, khi nhìn vào trạng thái bộ nhớ của ứng dụng trong VM Tracker, bạn sẽ thấy rằng LMDB không phải là ứng dụng duy nhất yêu cầu bộ nhớ ánh xạ bộ nhớ. Các phần tốt bị ăn mất bởi bộ cấp phát hệ thống, tệp tài nguyên, khung hình ảnh và những kẻ săn mồi nhỏ hơn khác.

Dựa trên kết quả thử nghiệm trong Đám mây, chúng tôi đã đạt được các giá trị thỏa hiệp sau của bộ nhớ do LMDB phân bổ: 384 megabyte cho thiết bị 32 bit và 768 cho thiết bị 64 bit. Sau khi khối lượng này được sử dụng hết, mọi hoạt động sửa đổi bắt đầu hoàn thành với mã MDB_MAP_FULL. Chúng tôi quan sát thấy những lỗi như vậy trong quá trình giám sát của mình, nhưng chúng đủ nhỏ để có thể bỏ qua ở giai đoạn này.

Một lý do không rõ ràng cho việc tiêu thụ bộ nhớ quá mức do lưu trữ có thể là các giao dịch tồn tại lâu dài. Để hiểu làm thế nào hai hiện tượng này có liên quan, nó sẽ giúp chúng tôi xem xét hai con cá voi LMDB còn lại.

3.2. Cá voi #2. B+-cây

Để mô phỏng các bảng ở đầu kho lưu trữ khóa-giá trị, các hoạt động sau phải có trong API của nó:

1. Chèn một phần tử mới.
2. Tìm kiếm một phần tử với một khóa nhất định.
3. Xóa một phần tử.
4. Lặp lại các khoảng thời gian chính theo thứ tự sắp xếp của chúng.

Cấu trúc dữ liệu đơn giản nhất có thể dễ dàng thực hiện cả bốn thao tác là cây tìm kiếm nhị phân. Mỗi nút của nó là một khóa chia toàn bộ tập con khóa con thành hai cây con. Bên trái là những cái nhỏ hơn cha mẹ và bên phải - những cái lớn hơn. Có được một bộ khóa được sắp xếp theo thứ tự đạt được thông qua một trong các phép duyệt cây cổ điển.​

Cây nhị phân có hai nhược điểm cơ bản khiến chúng không hiệu quả như một cấu trúc dữ liệu đĩa. Đầu tiên, mức độ cân bằng của họ là không thể đoán trước. Có một rủi ro đáng kể khi lấy các cây trong đó chiều cao của các nhánh khác nhau có thể khác nhau rất nhiều, điều này làm trầm trọng thêm độ phức tạp của thuật toán tìm kiếm so với dự kiến. Thứ hai, sự phong phú của các liên kết chéo giữa các nút làm mất đi vị trí của cây nhị phân trong bộ nhớ Các nút đóng (về liên kết giữa chúng) có thể được định vị trên các trang hoàn toàn khác nhau trong bộ nhớ ảo. Kết quả là, ngay cả việc duyệt đơn giản một số nút lân cận trong cây cũng có thể yêu cầu truy cập một số lượng trang có thể so sánh được. Đây là một vấn đề ngay cả khi chúng ta nói về tính hiệu quả của cây nhị phân với tư cách là cấu trúc dữ liệu trong bộ nhớ, vì các trang xoay vòng liên tục trong bộ đệm của bộ xử lý không hề rẻ. Khi nói đến việc thường xuyên tăng các trang liên quan đến nút từ đĩa, mọi thứ trở nên thực sự tồi tệ. thương tâm.

Cây B, là một sự phát triển của cây nhị phân, giải quyết các vấn đề được xác định trong đoạn trước. Đầu tiên, họ tự cân bằng. Thứ hai, mỗi nút của chúng chia tập hợp các khóa con không phải thành 2 mà thành M tập con có thứ tự và số M có thể khá lớn, vào khoảng vài trăm hoặc thậm chí hàng nghìn.

Bằng cách ấy:

1. Mỗi nút có một số lượng lớn các khóa đã được sắp xếp và cây rất thấp.
2. Cây có được thuộc tính của vị trí trong bộ nhớ, vì các khóa gần giá trị được đặt tự nhiên cạnh nhau trên một hoặc các nút lân cận.
3. Giảm số nút chuyển tuyến khi đi xuống cây trong quá trình tìm kiếm.
4. Giảm số lượng nút đích được đọc cho các truy vấn phạm vi, vì mỗi nút trong số chúng đã chứa một số lượng lớn các khóa được sắp xếp.

LMDB sử dụng một biến thể của cây B được gọi là cây B+ để lưu trữ dữ liệu. Sơ đồ trên cho thấy ba loại nút mà nó chứa:

1. Trên cùng là gốc. Nó cụ thể hóa không gì khác hơn là khái niệm về một cơ sở dữ liệu trong một kho lưu trữ. Trong một phiên bản LMDB duy nhất, bạn có thể tạo nhiều cơ sở dữ liệu chia sẻ không gian địa chỉ ảo được ánh xạ. Mỗi người trong số họ bắt đầu từ gốc của chính nó.
2. Ở mức thấp nhất là những chiếc lá (leaf). Chính chúng và chỉ chúng chứa các cặp khóa-giá trị được lưu trữ trong cơ sở dữ liệu. Nhân tiện, đây là điểm đặc biệt của B+-trees. Nếu một cây B bình thường lưu trữ các phần giá trị tại các nút của tất cả các cấp, thì biến thể B+ chỉ ở mức thấp nhất. Sau khi khắc phục thực tế này, trong phần tiếp theo, chúng tôi sẽ gọi kiểu con của cây được sử dụng trong LMDB đơn giản là cây B.
3. Giữa gốc và lá có từ 0 cấp kỹ thuật trở lên với các nút (nhánh) điều hướng. Nhiệm vụ của họ là chia bộ khóa đã sắp xếp giữa các lá.

Về mặt vật lý, các nút là các khối bộ nhớ có độ dài xác định trước. Kích thước của chúng là bội số của kích thước của các trang bộ nhớ trong hệ điều hành mà chúng ta đã nói ở trên. Cấu trúc nút được hiển thị bên dưới. Tiêu đề chứa thông tin meta, ví dụ, thông tin rõ ràng nhất là tổng kiểm tra. Tiếp theo là thông tin về độ lệch, dọc theo đó các ô có dữ liệu được đặt. Vai trò của dữ liệu có thể là các khóa nếu chúng ta đang nói về các nút điều hướng hoặc toàn bộ các cặp khóa-giá trị trong trường hợp các lá. Bạn có thể đọc thêm về cấu trúc của các trang trong tác phẩm "Đánh giá các cửa hàng khóa-giá trị hiệu suất cao".

Sau khi xử lý nội dung bên trong của các nút trang, chúng tôi sẽ trình bày thêm cây B LMDB theo cách đơn giản hóa dưới dạng sau.

Các trang có nút được sắp xếp tuần tự trên đĩa. Các trang có số cao hơn nằm ở cuối tệp. Cái gọi là trang meta (trang meta) chứa thông tin về độ lệch, có thể được sử dụng để tìm gốc của tất cả các cây. Khi một tệp được mở, LMDB sẽ quét từng trang của tệp từ đầu đến cuối để tìm kiếm trang meta hợp lệ và tìm cơ sở dữ liệu hiện có thông qua trang đó.​

Bây giờ, khi đã có ý tưởng về cấu trúc logic và vật lý của tổ chức dữ liệu, chúng ta có thể tiến hành xem xét con cá voi thứ ba của LMDB. Với sự trợ giúp của nó, tất cả các sửa đổi lưu trữ xảy ra theo giao dịch và tách biệt với nhau, mang lại cho toàn bộ cơ sở dữ liệu cũng là thuộc tính đa phiên bản.

3.3. Cá voi #3. sao chép trên ghi

Một số hoạt động của cây B liên quan đến việc thực hiện một loạt các thay đổi đối với các nút của nó. Một ví dụ là thêm một khóa mới vào một nút đã đạt đến dung lượng tối đa. Trong trường hợp này, trước tiên, cần phải chia nút thành hai và thứ hai, thêm một liên kết đến nút con mới được tách ra trong nút cha của nó. Thủ tục này có khả năng rất nguy hiểm. Nếu vì một lý do nào đó (sự cố, mất điện, v.v.) chỉ xảy ra một phần thay đổi so với chuỗi, thì cây sẽ ở trạng thái không nhất quán.

Một giải pháp truyền thống để làm cho cơ sở dữ liệu có khả năng chịu lỗi là thêm một cấu trúc dữ liệu dựa trên đĩa bổ sung, nhật ký giao dịch, còn được gọi là nhật ký ghi trước (WAL), bên cạnh cây B. Nó là một tệp, ở phần cuối của nó, hoàn toàn trước khi sửa đổi chính cây B, thao tác dự định được viết. Do đó, nếu dữ liệu bị hỏng được phát hiện trong quá trình tự chẩn đoán, cơ sở dữ liệu sẽ tham khảo nhật ký để tự dọn sạch.

LMDB đã chọn một phương pháp khác làm cơ chế chịu lỗi, được gọi là sao chép khi ghi. Bản chất của nó là thay vì cập nhật dữ liệu trên một trang hiện có, trước tiên, nó sẽ sao chép toàn bộ trang đó và thực hiện tất cả các sửa đổi đã có trong bản sao.​

Hơn nữa, để có sẵn dữ liệu cập nhật, cần phải thay đổi liên kết đến nút đã được cập nhật trong nút cha liên quan đến nó. Vì nó cũng cần được sửa đổi cho việc này, nên nó cũng được sao chép trước. Quá trình tiếp tục đệ quy cho đến tận gốc. Dữ liệu trên trang meta là dữ liệu thay đổi cuối cùng.​

Nếu quá trình đột ngột gặp sự cố trong quá trình cập nhật, thì một trang meta mới sẽ không được tạo hoặc nó sẽ không được ghi vào đĩa cho đến khi kết thúc và tổng kiểm tra của nó sẽ không chính xác. Trong một trong hai trường hợp này, các trang mới sẽ không thể truy cập được và các trang cũ sẽ không bị ảnh hưởng. Điều này giúp LMDB không cần phải ghi nhật ký trước để duy trì tính nhất quán của dữ liệu. Trên thực tế, cấu trúc lưu trữ dữ liệu trên đĩa, được mô tả ở trên, đồng thời đảm nhận chức năng của nó. Việc không có nhật ký giao dịch rõ ràng là một trong những tính năng của LMDB, cung cấp tốc độ đọc dữ liệu cao.​

Cấu trúc kết quả, được gọi là cây B chỉ nối thêm, tự nhiên cung cấp sự cô lập và đa phiên bản giao dịch. Trong LMDB, mỗi giao dịch mở có một gốc cây cập nhật được liên kết với nó. Miễn là giao dịch chưa được hoàn thành, các trang của cây được liên kết với nó sẽ không bao giờ được thay đổi hoặc sử dụng lại cho các phiên bản dữ liệu mới. Do đó, bạn có thể làm việc bao lâu tùy thích với tập dữ liệu có liên quan tại thời điểm giao dịch được mở, ngay cả khi bộ lưu trữ tiếp tục được cập nhật tích cực vào thời điểm này. Đây là bản chất của đa phiên bản, làm cho LMDB trở thành nguồn dữ liệu lý tưởng cho những người thân yêu của chúng ta UICollectionView. Sau khi mở một giao dịch, bạn không cần phải tăng dung lượng bộ nhớ của ứng dụng, vội vàng bơm dữ liệu hiện tại vào một cấu trúc trong bộ nhớ nào đó, sợ không còn gì. Tính năng này phân biệt LMDB với cùng một SQLite, không thể tự hào về sự cô lập hoàn toàn như vậy. Đã mở hai giao dịch trong giao dịch thứ hai và xóa một bản ghi nhất định trong một trong số chúng, không thể lấy cùng một bản ghi trong giao dịch thứ hai còn lại.

​Mặt trái của xu hướng này là khả năng tiêu thụ bộ nhớ ảo cao hơn đáng kể. Trang trình bày cho thấy cấu trúc cơ sở dữ liệu sẽ như thế nào nếu nó được sửa đổi cùng lúc với 3 giao dịch đọc mở xem xét các phiên bản khác nhau của cơ sở dữ liệu. Vì LMDB không thể sử dụng lại các nút có thể truy cập được từ các gốc được liên kết với các giao dịch thực tế, bộ lưu trữ không có lựa chọn nào khác ngoài việc phân bổ một gốc thứ tư khác trong bộ nhớ và một lần nữa sao chép các trang đã sửa đổi bên dưới nó.

Ở đây sẽ không thừa khi nhớ lại phần về các tệp ánh xạ bộ nhớ. Có vẻ như việc tiêu thụ thêm bộ nhớ ảo sẽ không làm phiền chúng tôi nhiều vì nó không góp phần vào dung lượng bộ nhớ của ứng dụng. Tuy nhiên, đồng thời, người ta lưu ý rằng iOS rất keo kiệt trong việc phân bổ nó và chúng tôi không thể cung cấp vùng LMDB 1 terabyte trên máy chủ hoặc máy tính để bàn từ vai chủ và hoàn toàn không nghĩ đến tính năng này. Khi có thể, bạn nên cố gắng giữ thời gian tồn tại của các giao dịch càng ngắn càng tốt.

4. Thiết kế lược đồ dữ liệu trên API khóa-giá trị

Hãy bắt đầu phân tích cú pháp API bằng cách xem xét các tóm tắt cơ bản do LMDB cung cấp: môi trường và cơ sở dữ liệu, khóa và giá trị, giao dịch và con trỏ.

Một lưu ý về danh sách mã

Tất cả các chức năng trong API công khai LMDB trả về kết quả công việc của chúng dưới dạng mã lỗi, nhưng trong tất cả các danh sách tiếp theo, kiểm tra của nó được bỏ qua vì mục đích ngắn gọn. cái nĩa trình bao bọc C++ lmdbxx, trong đó lỗi cụ thể hóa thành ngoại lệ C++.

Là cách nhanh nhất để kết nối LMDB với dự án iOS hoặc macOS, tôi cung cấp CocoaPod của mình POSLMDB.

4.1. trừu tượng cơ bản

Môi trường

Cấu trúc MDB_env là kho lưu trữ trạng thái bên trong của LMDB. Họ các chức năng tiền tố mdb_env cho phép bạn cấu hình một số thuộc tính của nó. Trong trường hợp đơn giản nhất, quá trình khởi tạo động cơ trông như thế này.

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

Trong ứng dụng Mail.ru Cloud, chúng tôi chỉ thay đổi các giá trị mặc định cho hai tham số.

Cái đầu tiên là kích thước của không gian địa chỉ ảo mà tệp lưu trữ được ánh xạ tới. Thật không may, ngay cả trên cùng một thiết bị, giá trị cụ thể có thể thay đổi đáng kể từ lần chạy này sang lần chạy khác. Để tính đến tính năng này của iOS, chúng tôi tự động chọn dung lượng lưu trữ tối đa. Bắt đầu từ một giá trị nhất định, nó liên tiếp giảm một nửa cho đến khi hàm mdb_env_open sẽ không trả về kết quả nào khác ngoài ENOMEM. Về lý thuyết, có một cách ngược lại - đầu tiên phân bổ bộ nhớ tối thiểu cho động cơ, sau đó, khi nhận được lỗi MDB_MAP_FULL, tăng nó. Tuy nhiên, nó gai góc hơn nhiều. Lý do là quy trình ánh xạ lại bộ nhớ bằng hàm mdb_env_set_map_size làm mất hiệu lực tất cả các thực thể (con trỏ, giao dịch, khóa và giá trị) đã nhận được từ công cụ trước đó. Tính toán cho một loạt các sự kiện như vậy trong mã sẽ dẫn đến sự phức tạp đáng kể của nó. Tuy nhiên, nếu bộ nhớ ảo rất thân thiết với bạn, thì đây có thể là lý do để xem xét bản fork đã đi trước rất xa. MDBX, trong số các tính năng đã khai báo có “điều chỉnh kích thước cơ sở dữ liệu tự động nhanh chóng”.

Tham số thứ hai, giá trị mặc định không phù hợp với chúng tôi, quy định cơ chế đảm bảo an toàn cho luồng. Thật không may, ít nhất là trong iOS 10, có vấn đề với hỗ trợ bộ nhớ cục bộ của luồng. Vì lý do này, trong ví dụ trên, kho lưu trữ được mở bằng cờ MDB_NOTLS. Ngoài ra, nó còn yêu cầu cái nĩa trình bao bọc C++ lmdbxxđể cắt các biến có và trong thuộc tính này.

Cơ sở dữ liệu

Cơ sở dữ liệu là một thể hiện riêng biệt của B-tree mà chúng ta đã nói ở trên. Việc mở nó xảy ra bên trong một giao dịch, điều này thoạt nghe có vẻ hơi lạ.

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);

Thật vậy, một giao dịch trong LMDB là một thực thể lưu trữ, không phải một cơ sở dữ liệu cụ thể. Khái niệm này cho phép bạn thực hiện các thao tác nguyên tử trên các thực thể nằm trong các cơ sở dữ liệu khác nhau. Về lý thuyết, điều này mở ra khả năng lập mô hình bảng dưới dạng các cơ sở dữ liệu khác nhau, nhưng có lúc tôi đã đi theo hướng khác, được mô tả chi tiết bên dưới.

Khóa và giá trị

Cấu trúc MDB_val mô hình hóa khái niệm về cả khóa và giá trị. Kho lưu trữ không biết gì về ngữ nghĩa của chúng. Đối với cô ấy, một cái gì đó khác biệt chỉ là một mảng byte có kích thước nhất định. Kích thước khóa tối đa là 512 byte.

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

Cửa hàng sử dụng bộ so sánh để sắp xếp các khóa theo thứ tự tăng dần. Nếu bạn không thay thế nó bằng cái của riêng bạn, thì cái mặc định sẽ được sử dụng, sắp xếp chúng theo từng byte theo thứ tự từ điển.​

Giao dịch

Thiết bị giao dịch được mô tả chi tiết trong chương trước, vì vậy ở đây tôi sẽ nhắc lại các thuộc tính chính của chúng trong một dòng ngắn gọn:

1. Hỗ trợ cho tất cả các thuộc tính cơ bản ACIDTừ khóa: tính nguyên tử, nhất quán, cô lập và độ tin cậy. Tôi không thể không lưu ý rằng về độ bền trên macOS và iOS, có một lỗi đã được sửa trong MDBX. Bạn có thể đọc thêm trong README.
2. Cách tiếp cận đa luồng được mô tả bằng lược đồ "một người viết/nhiều người đọc". Các nhà văn chặn nhau, nhưng họ không chặn người đọc. Người đọc không chặn người viết hoặc chặn lẫn nhau.
3. Hỗ trợ cho các giao dịch lồng nhau.
4. Hỗ trợ đa phiên bản.

Đa phiên bản trong LMDB tốt đến mức tôi muốn chứng minh điều đó bằng hành động. Đoạn mã dưới đây cho thấy rằng mỗi giao dịch hoạt động với chính xác phiên bản cơ sở dữ liệu có liên quan tại thời điểm mở, hoàn toàn tách biệt với tất cả các thay đổi tiếp theo. Việc khởi tạo kho lưu trữ và thêm bản ghi kiểm tra vào đó không được quan tâm, vì vậy những nghi thức này được để lại dưới phần tiết lộ.

Thêm một mục kiểm tra

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);

Theo tùy chọn, tôi khuyên bạn nên thử thủ thuật tương tự với SQLite và xem điều gì sẽ xảy ra.

Đa phiên bản mang lại những lợi ích rất tốt cho cuộc sống của một nhà phát triển iOS. Sử dụng thuộc tính này, bạn có thể dễ dàng và tự nhiên điều chỉnh tốc độ cập nhật nguồn dữ liệu cho các biểu mẫu màn hình dựa trên những cân nhắc về trải nghiệm người dùng. Ví dụ: hãy coi một tính năng như vậy của ứng dụng Mail.ru Cloud là tự động tải nội dung từ thư viện phương tiện của hệ thống. Với kết nối tốt, máy khách có thể thêm vài ảnh mỗi giây vào máy chủ. Nếu bạn cập nhật sau mỗi lần tải xuống UICollectionView với nội dung đa phương tiện trong đám mây của người dùng, bạn có thể bỏ qua khoảng 60 khung hình/giây và cuộn mượt mà trong quá trình này. Để ngăn cập nhật màn hình thường xuyên, bạn cần hạn chế bằng cách nào đó tốc độ thay đổi dữ liệu trong cơ sở UICollectionViewDataSource.

Nếu cơ sở dữ liệu không hỗ trợ đa phiên bản và chỉ cho phép bạn làm việc với trạng thái hiện tại, thì để tạo ảnh chụp nhanh dữ liệu ổn định theo thời gian, bạn cần sao chép nó vào một số cấu trúc dữ liệu trong bộ nhớ hoặc vào một bảng tạm thời. Một trong những cách tiếp cận này đều rất tốn kém. Trong trường hợp lưu trữ trong bộ nhớ, chúng tôi nhận được cả chi phí bộ nhớ do lưu trữ các đối tượng được xây dựng và chi phí thời gian liên quan đến các phép biến đổi ORM dự phòng. Đối với bảng tạm thời, đây là một thú vui thậm chí còn tốn kém hơn, chỉ có ý nghĩa trong những trường hợp không tầm thường.

LMDB đa phiên bản giải quyết vấn đề duy trì nguồn dữ liệu ổn định theo cách rất tinh tế. Chỉ cần mở một giao dịch và thì đấy - cho đến khi chúng tôi hoàn thành nó, bộ dữ liệu được đảm bảo là cố định. Logic của tốc độ cập nhật của nó giờ đây hoàn toàn nằm trong tay lớp trình bày, không có chi phí tài nguyên quan trọng.

con trỏ

Con trỏ cung cấp cơ chế lặp lại có trật tự trên các cặp khóa-giá trị bằng cách duyệt qua cây B. Không có chúng, sẽ không thể lập mô hình hiệu quả các bảng trong cơ sở dữ liệu, mà bây giờ chúng ta chuyển sang.

4.2. Lập mô hình bảng

Thuộc tính sắp xếp khóa cho phép bạn xây dựng một trừu tượng cấp cao nhất, chẳng hạn như một bảng trên đầu các trừu tượng cơ bản. Hãy xem xét quá trình này trên ví dụ về bảng chính của máy khách đám mây, trong đó thông tin về tất cả các tệp và thư mục của người dùng được lưu vào bộ đệm.

Lược đồ bảng

Một trong những tình huống phổ biến mà cấu trúc của bảng có cây thư mục nên được làm sắc nét hơn là chọn tất cả các phần tử nằm bên trong một thư mục nhất định. Một mô hình tổ chức dữ liệu tốt cho các truy vấn loại này hiệu quả là Danh sách gần kề. Để triển khai nó trên bộ lưu trữ khóa-giá trị, cần phải sắp xếp các khóa của tệp và thư mục theo cách chúng được nhóm dựa trên thuộc về thư mục mẹ. Ngoài ra, để hiển thị nội dung của thư mục ở dạng quen thuộc với người dùng Windows (trước tiên là thư mục, sau đó là tệp, cả hai đều được sắp xếp theo thứ tự abc), cần phải bao gồm các trường bổ sung tương ứng trong khóa.

​Hình ảnh dưới đây cho thấy cách thức, dựa trên nhiệm vụ, biểu diễn các khóa dưới dạng một mảng byte có thể trông như thế nào. Đầu tiên, các byte có mã định danh thư mục mẹ (màu đỏ) được đặt, sau đó là loại (màu xanh lá cây) và đã có tên ở đuôi (màu xanh lam). cách cần thiết. Các khóa duyệt liên tục có cùng tiền tố màu đỏ cung cấp cho chúng tôi các giá trị được liên kết với chúng theo thứ tự chúng sẽ được hiển thị trong giao diện người dùng (phải) mà không yêu cầu bất kỳ xử lý hậu kỳ bổ sung nào.

Nối tiếp khóa và giá trị

Có nhiều phương pháp để tuần tự hóa các đối tượng trên khắp thế giới. Vì chúng tôi không có yêu cầu nào khác ngoài tốc độ, nên chúng tôi đã chọn yêu cầu nhanh nhất có thể cho mình - một kết xuất bộ nhớ bị chiếm giữ bởi một thể hiện của cấu trúc ngôn ngữ C. Vì vậy, khóa của phần tử thư mục có thể được mô hình hóa theo cấu trúc sau NodeKey.

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

Để tiết kiệm NodeKey trong nhu cầu lưu trữ trong đối tượng MDB_val định vị con trỏ tới dữ liệu tại địa chỉ bắt đầu cấu trúc và tính toán kích thước của chúng bằng hàm sizeof.

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

Trong chương đầu tiên về tiêu chí lựa chọn cơ sở dữ liệu, tôi đã đề cập đến việc giảm thiểu phân bổ động như một phần của hoạt động CRUD như một yếu tố lựa chọn quan trọng. Mã chức năng serialize cho thấy làm thế nào, trong trường hợp của LMDB, chúng có thể tránh được hoàn toàn khi các bản ghi mới được chèn vào cơ sở dữ liệu. Mảng byte đến từ máy chủ trước tiên được chuyển đổi thành cấu trúc ngăn xếp, sau đó chúng được đưa vào bộ lưu trữ một cách tầm thường. Vì cũng không có phân bổ động bên trong LMDB, bạn có thể gặp một tình huống tuyệt vời theo tiêu chuẩn của iOS - chỉ sử dụng bộ nhớ ngăn xếp để làm việc với dữ liệu từ mạng đến đĩa!

Đặt hàng các khóa với bộ so sánh nhị phân

Quan hệ thứ tự khóa được đưa ra bởi một chức năng đặc biệt gọi là bộ so sánh. Vì công cụ không biết gì về ngữ nghĩa của các byte mà chúng chứa, bộ so sánh mặc định không có lựa chọn nào khác ngoài việc sắp xếp các khóa theo thứ tự từ điển, sử dụng so sánh từng byte của chúng. Sử dụng nó để sắp xếp các cấu trúc giống như cạo bằng rìu điêu khắc. Tuy nhiên, trong những trường hợp đơn giản, tôi thấy phương pháp này có thể chấp nhận được. Phương án thay thế được mô tả bên dưới, nhưng ở đây tôi sẽ lưu ý một vài chiếc cào nằm rải rác trên đường đi.

Điều đầu tiên cần lưu ý là biểu diễn bộ nhớ của các kiểu dữ liệu nguyên thủy. Vì vậy, trên tất cả các thiết bị của Apple, các biến số nguyên được lưu trữ ở định dạng Endian nhỏ. Điều này có nghĩa là byte ít quan trọng nhất sẽ ở bên trái và bạn sẽ không thể sắp xếp các số nguyên bằng cách so sánh từng byte của chúng. Ví dụ thử làm với dãy số từ 0 đến 511 sẽ được kết quả như sau.

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

Để giải quyết vấn đề này, các số nguyên phải được lưu trữ trong khóa ở định dạng phù hợp với bộ so sánh byte. Các chức năng từ gia đình sẽ giúp thực hiện các chuyển đổi cần thiết. hton* (đặc biệt htons đối với các số byte kép từ ví dụ).

Như bạn đã biết, định dạng biểu diễn các chuỗi trong lập trình là toàn bộ lịch sử. Nếu ngữ nghĩa của các chuỗi, cũng như mã hóa được sử dụng để biểu thị chúng trong bộ nhớ, gợi ý rằng có thể có nhiều hơn một byte cho mỗi ký tự, thì tốt hơn là bạn nên từ bỏ ngay ý tưởng sử dụng bộ so sánh mặc định.

Điều thứ hai cần ghi nhớ là nguyên tắc căn chỉnh trình biên dịch trường cấu trúc. Do chúng, các byte có giá trị rác có thể được hình thành trong bộ nhớ giữa các trường, tất nhiên, điều này sẽ phá vỡ việc sắp xếp byte. Để loại bỏ rác, bạn phải khai báo các trường theo thứ tự được xác định nghiêm ngặt, ghi nhớ các quy tắc căn chỉnh hoặc sử dụng thuộc tính trong khai báo cấu trúc packed.

Thứ tự khóa bởi một bộ so sánh bên ngoài

Logic so sánh khóa có thể trở nên quá phức tạp đối với bộ so sánh nhị phân. Một trong nhiều lý do là sự hiện diện của các lĩnh vực kỹ thuật bên trong các cấu trúc. Tôi sẽ minh họa sự xuất hiện của chúng trên ví dụ về một khóa đã quen thuộc với chúng ta đối với phần tử thư mục.

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

Đối với tất cả sự đơn giản của nó, trong phần lớn các trường hợp, nó tiêu tốn quá nhiều bộ nhớ. Bộ đệm tiêu đề là 256 byte, mặc dù tên tệp và thư mục trung bình hiếm khi vượt quá 20-30 ký tự.

​Một trong những kỹ thuật tiêu chuẩn để tối ưu hóa kích thước của bản ghi là "cắt" nó để phù hợp với kích thước thực tế. Bản chất của nó là nội dung của tất cả các trường có độ dài thay đổi được lưu trữ trong bộ đệm ở cuối cấu trúc và độ dài của chúng được lưu trữ trong các biến riêng biệt. NodeKey được biến đổi theo cách sau.

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

Hơn nữa, trong quá trình tuần tự hóa, kích thước dữ liệu không được chỉ định sizeof toàn bộ cấu trúc và kích thước của tất cả các trường là chiều dài cố định cộng với kích thước của phần thực sự được sử dụng của bộ đệm.

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

Kết quả của việc tái cấu trúc, chúng tôi đã tiết kiệm được đáng kể không gian cho các phím. Tuy nhiên, do lĩnh vực kỹ thuật nameLength, bộ so sánh nhị phân mặc định không còn phù hợp để so sánh khóa. Nếu chúng ta không thay thế nó bằng tên của chính mình, thì độ dài của tên sẽ là yếu tố được ưu tiên hơn trong việc sắp xếp so với chính tên đó.

LMDB cho phép mỗi cơ sở dữ liệu có chức năng so sánh khóa riêng. Điều này được thực hiện bằng cách sử dụng chức năng mdb_set_compare nghiêm ngặt trước khi mở. Vì những lý do rõ ràng, cơ sở dữ liệu không thể thay đổi trong suốt vòng đời của nó. Ở đầu vào, bộ so sánh nhận hai khóa ở định dạng nhị phân và ở đầu ra, nó trả về kết quả so sánh: nhỏ hơn (-1), lớn hơn (1) hoặc bằng (0). Mã giả cho NodeKey trông như vậy.

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 // ...
}​

Miễn là tất cả các khóa trong cơ sở dữ liệu đều thuộc cùng một loại, việc truyền vô điều kiện biểu diễn byte của chúng sang loại cấu trúc ứng dụng của khóa là hợp pháp. Có một sắc thái ở đây, nhưng nó sẽ được thảo luận thấp hơn một chút trong tiểu mục “Hồ sơ đọc”.

Tuần tự hóa giá trị

Với các khóa của bản ghi được lưu trữ, LMDB hoạt động cực kỳ mạnh mẽ. Chúng được so sánh với nhau trong khuôn khổ của bất kỳ hoạt động ứng dụng nào và hiệu suất của toàn bộ giải pháp phụ thuộc vào tốc độ của bộ so sánh. Trong một thế giới lý tưởng, bộ so sánh nhị phân mặc định là đủ để so sánh các khóa, nhưng nếu bạn thực sự phải sử dụng khóa của riêng mình, thì quy trình giải tuần tự hóa các khóa trong đó phải càng nhanh càng tốt.

Cơ sở dữ liệu không đặc biệt quan tâm đến phần Giá trị của bản ghi (giá trị). Việc chuyển đổi từ biểu diễn byte sang đối tượng chỉ xảy ra khi nó đã được yêu cầu bởi mã ứng dụng, ví dụ, để hiển thị nó trên màn hình. Vì điều này tương đối hiếm khi xảy ra, nên các yêu cầu về tốc độ của quy trình này không quá quan trọng và trong quá trình triển khai, chúng tôi có thể tự do hơn nhiều để tập trung vào sự thuận tiện. Ví dụ: để tuần tự hóa siêu dữ liệu về các tệp chưa được tải xuống, chúng tôi sử dụng NSKeyedArchiver.

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

Tuy nhiên, có những lúc hiệu suất có vấn đề. Ví dụ: khi lưu siêu thông tin về cấu trúc tệp của đám mây người dùng, chúng tôi sử dụng cùng một kết xuất bộ nhớ đối tượng. Điểm nổi bật của nhiệm vụ tạo biểu diễn tuần tự hóa của chúng là thực tế là các phần tử của một thư mục được mô hình hóa bởi một hệ thống phân cấp lớp.​

Để triển khai nó bằng ngôn ngữ C, các trường cụ thể của những người thừa kế được đưa vào các cấu trúc riêng biệt và kết nối của chúng với cơ sở được chỉ định thông qua một trường thuộc loại liên kết. Nội dung thực tế của liên kết được chỉ định thông qua thuộc tính kỹ thuật loại.

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

Bổ sung, cập nhật hồ sơ

Khóa và giá trị được tuần tự hóa có thể được thêm vào cửa hàng. Đối với điều này, chức năng được sử dụng mdb_put.

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

Ở giai đoạn cấu hình, kho lưu trữ có thể được phép hoặc cấm lưu trữ nhiều bản ghi với cùng một khóa.​ Nếu việc sao chép các khóa bị cấm thì khi chèn một bản ghi, bạn có thể xác định xem việc cập nhật một bản ghi đã tồn tại có được phép hay không. Nếu sờn chỉ có thể xảy ra do lỗi trong mã, thì bạn có thể bảo đảm chống lại nó bằng cách chỉ định cờ NOOVERWRITE.

Đọc hồ sơ

Chức năng đọc các bản ghi trong LMDB là mdb_get. Nếu cặp khóa-giá trị được biểu thị bằng các cấu trúc đã đổ trước đó, thì quy trình này sẽ giống như sau.

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

Danh sách được trình bày cho thấy cách tuần tự hóa thông qua kết xuất cấu trúc cho phép bạn loại bỏ phân bổ động không chỉ khi viết mà còn khi đọc dữ liệu. Xuất phát từ chức năng mdb_get con trỏ tìm chính xác địa chỉ bộ nhớ ảo nơi cơ sở dữ liệu lưu trữ biểu diễn byte của đối tượng. Trên thực tế, chúng tôi nhận được một loại ORM, gần như miễn phí, cung cấp tốc độ đọc dữ liệu rất cao. Với tất cả vẻ đẹp của phương pháp này, cần phải nhớ một số tính năng liên quan đến nó.

1. Đối với giao dịch chỉ đọc, một con trỏ tới cấu trúc giá trị được đảm bảo chỉ duy trì hiệu lực cho đến khi giao dịch được đóng lại. Như đã lưu ý trước đó, các trang của cây B chứa đối tượng, nhờ nguyên tắc sao chép khi ghi, sẽ không thay đổi miễn là có ít nhất một giao dịch đề cập đến chúng. Đồng thời, ngay sau khi hoàn thành giao dịch cuối cùng được liên kết với chúng, các trang có thể được sử dụng lại cho dữ liệu mới. Nếu các đối tượng cần phải tồn tại trong giao dịch đã tạo ra chúng, thì chúng vẫn phải được sao chép.
2. Đối với giao dịch đọc ghi, con trỏ tới giá trị cấu trúc kết quả sẽ chỉ hợp lệ cho đến thủ tục sửa đổi đầu tiên (ghi hoặc xóa dữ liệu).
3. Mặc dù cấu trúc NodeValue không đầy đủ, nhưng đã được cắt bớt (xem tiểu mục "Sắp xếp các phím theo bộ so sánh bên ngoài"), thông qua con trỏ, bạn có thể dễ dàng truy cập các trường của nó. Điều chính là không dereference nó!
4. Trong mọi trường hợp, bạn không thể sửa đổi cấu trúc thông qua con trỏ nhận được. Tất cả các thay đổi phải được thực hiện chỉ thông qua phương pháp mdb_put. Tuy nhiên, với tất cả mong muốn làm điều này, nó sẽ không hoạt động, vì vùng bộ nhớ chứa cấu trúc này được ánh xạ ở chế độ chỉ đọc.
5. Ánh xạ lại một tệp vào không gian địa chỉ của một quy trình để tăng kích thước lưu trữ tối đa bằng cách sử dụng chức năng mdb_env_set_map_size làm mất hiệu lực hoàn toàn mọi giao dịch và các thực thể liên quan nói chung và các con trỏ để đọc đối tượng nói riêng.

Cuối cùng, một tính năng nữa ngấm ngầm đến mức việc tiết lộ bản chất của nó không phù hợp với một điểm nữa. Trong chương về cây B, tôi đã đưa ra sơ đồ tổ chức các trang của nó trong bộ nhớ. Theo đó, địa chỉ bắt đầu của bộ đệm với dữ liệu được tuần tự hóa có thể hoàn toàn tùy ý. Do đó, con trỏ tới chúng, thu được trong cấu trúc MDB_val và truyền tới một con trỏ tới một cấu trúc thường không được phân bổ. Đồng thời, kiến ​​​​trúc của một số chip (trong trường hợp của iOS, đây là armv7) yêu cầu địa chỉ của bất kỳ dữ liệu nào phải là bội số của kích thước của một từ máy, hay nói cách khác, độ bit của hệ thống (đối với armv7, đây là 32 bit). Nói cách khác, một hoạt động như *(int *foo)0x800002 đối với họ được coi là trốn thoát và dẫn đến việc thực hiện với một bản án EXC_ARM_DA_ALIGN. Có hai cách để tránh một số phận đáng buồn như vậy.

Đầu tiên là sao chép dữ liệu vào một cấu trúc đã biết trước. Ví dụ: trên bộ so sánh tùy chỉnh, điều này sẽ được phản ánh như sau.

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 // ...
}

Một cách khác là thông báo trước cho trình biên dịch rằng các cấu trúc có khóa và giá trị có thể không được căn chỉnh bằng thuộc tính aligned(1). Trên ARM, hiệu ứng tương tự có thể là Hoàn thành và sử dụng thuộc tính được đóng gói. Xem xét rằng nó cũng góp phần tối ưu hóa không gian bị chiếm bởi cấu trúc, phương pháp này đối với tôi có vẻ thích hợp hơn, mặc dù приводит để tăng chi phí cho hoạt động truy cập dữ liệu.

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

Phạm vi truy vấn

Để lặp lại một nhóm bản ghi, LMDB cung cấp một bản tóm tắt con trỏ. Hãy xem cách làm việc với nó bằng cách sử dụng ví dụ về bảng có siêu dữ liệu đám mây người dùng đã quen thuộc với chúng ta.

Là một phần của việc hiển thị danh sách các tệp trong một thư mục, bạn cần tìm tất cả các khóa mà các tệp và thư mục con của nó được liên kết. Trong các tiểu mục trước, chúng tôi đã sắp xếp các phím NodeKey để chúng được sắp xếp đầu tiên bởi ID thư mục mẹ của chúng. Do đó, về mặt kỹ thuật, nhiệm vụ lấy nội dung của một thư mục được rút gọn thành việc đặt con trỏ ở ranh giới trên của một nhóm khóa có tiền tố nhất định, sau đó lặp lại đến ranh giới dưới.

Bạn có thể tìm thấy giới hạn trên "trên trán" bằng cách tìm kiếm tuần tự. Để làm điều này, con trỏ được đặt ở đầu toàn bộ danh sách các khóa trong cơ sở dữ liệu và sau đó tăng dần cho đến khi khóa có mã định danh thư mục mẹ xuất hiện bên dưới nó. Cách tiếp cận này có 2 nhược điểm rõ ràng:

1. Độ phức tạp tuyến tính của tìm kiếm, mặc dù, như bạn biết, trong cây nói chung và cây B nói riêng, nó có thể được thực hiện trong thời gian logarit.​
2. Vô ích, tất cả các trang trước trang mong muốn được nâng lên từ tệp vào bộ nhớ chính, điều này cực kỳ tốn kém.

May mắn thay, API LMDB cung cấp một cách hiệu quả để định vị con trỏ ban đầu.​ Để thực hiện việc này, bạn cần tạo một khóa như vậy, giá trị của khóa này chắc chắn sẽ nhỏ hơn hoặc bằng với khóa nằm ở giới hạn trên của khoảng . Ví dụ, liên quan đến danh sách trong hình trên, chúng ta có thể tạo một khóa trong đó trường parentId sẽ bằng 2 và tất cả phần còn lại được điền bằng số không. Một khóa được điền một phần như vậy được đưa vào đầu vào của hàm mdb_cursor_get chỉ ra hoạt động 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);

Nếu giới hạn trên của nhóm khóa được tìm thấy, thì chúng tôi sẽ lặp lại nó cho đến khi chúng tôi gặp hoặc gặp khóa với khóa khác parentId, hoặc các phím sẽ không hết.​

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​​

Thật tuyệt, là một phần của phép lặp sử dụng mdb_cursor_get, chúng tôi không chỉ nhận được khóa mà còn cả giá trị. Nếu, để đáp ứng các điều kiện lựa chọn, cần phải kiểm tra, trong số những thứ khác, các trường từ phần giá trị của bản ghi, thì chúng hoàn toàn có thể truy cập được mà không cần thêm cử chỉ.

4.3. Mô hình hóa mối quan hệ giữa các bảng

Đến nay, chúng tôi đã cố gắng xem xét tất cả các khía cạnh của việc thiết kế và làm việc với cơ sở dữ liệu một bảng. Chúng ta có thể nói rằng một bảng là một tập hợp các bản ghi được sắp xếp bao gồm các cặp khóa-giá trị cùng loại. Nếu bạn hiển thị một khóa dưới dạng hình chữ nhật và giá trị được liên kết của nó dưới dạng hộp, bạn sẽ có được một sơ đồ trực quan về cơ sở dữ liệu.

â € <

Tuy nhiên, trong cuộc sống thực, hiếm khi có thể tồn tại với ít máu như vậy. Thông thường trong một cơ sở dữ liệu, thứ nhất, cần phải có một số bảng và thứ hai, thực hiện các lựa chọn trong chúng theo thứ tự khác với khóa chính. Phần cuối cùng này được dành cho các vấn đề về sự sáng tạo và kết nối của chúng.

bảng chỉ mục

Ứng dụng đám mây có phần "Thư viện". Nó hiển thị nội dung đa phương tiện từ toàn bộ đám mây, được sắp xếp theo ngày. Để triển khai tối ưu lựa chọn như vậy, bên cạnh bảng chính, bạn cần tạo một bảng khác với loại khóa mới. Chúng sẽ chứa một trường có ngày tệp được tạo, trường này sẽ đóng vai trò là tiêu chí sắp xếp chính. Bởi vì các khóa mới đề cập đến cùng một dữ liệu như các khóa trong bảng bên dưới, nên chúng được gọi là khóa chỉ mục. Chúng được đánh dấu bằng màu cam trong hình bên dưới.

Để tách các khóa của các bảng khác nhau trong cùng một cơ sở dữ liệu, một trường kỹ thuật bổ sung tableId đã được thêm vào tất cả chúng. Bằng cách đặt nó ở mức ưu tiên cao nhất để sắp xếp, trước tiên chúng tôi sẽ nhóm các khóa theo bảng và đã ở trong bảng - theo quy tắc riêng của chúng tôi.​

Khóa chỉ mục đề cập đến cùng một dữ liệu với khóa chính. Việc triển khai đơn giản thuộc tính này bằng cách liên kết với nó một bản sao của phần giá trị của khóa chính là không tối ưu theo nhiều quan điểm cùng một lúc:​

1. Từ quan điểm chiếm dụng không gian, siêu dữ liệu có thể khá phong phú.
2. Từ quan điểm hiệu suất, vì khi cập nhật siêu dữ liệu nút, bạn sẽ phải ghi đè hai khóa.
3. Xét cho cùng, từ quan điểm hỗ trợ mã, nếu chúng tôi quên cập nhật dữ liệu cho một trong các khóa, chúng tôi sẽ gặp một lỗi nhỏ về sự không nhất quán dữ liệu trong bộ lưu trữ.

Tiếp theo, chúng tôi sẽ xem xét làm thế nào để loại bỏ những thiếu sót này.

Tổ chức các mối quan hệ giữa các bảng

Mẫu này rất phù hợp để liên kết bảng chỉ mục với bảng chính "khóa dưới dạng giá trị". Như tên gọi của nó, phần giá trị của bản ghi chỉ mục là bản sao của giá trị khóa chính. Cách tiếp cận này loại bỏ tất cả các nhược điểm được liệt kê ở trên liên quan đến việc lưu trữ một bản sao của phần giá trị của bản ghi chính. Phí duy nhất là để lấy giá trị bằng khóa chỉ mục, bạn cần thực hiện 2 truy vấn tới cơ sở dữ liệu thay vì một. Về mặt sơ đồ, lược đồ cơ sở dữ liệu kết quả như sau.

Một mẫu khác để tổ chức các mối quan hệ giữa các bảng là "chìa khóa dự phòng". Bản chất của nó là thêm các thuộc tính bổ sung vào khóa, các thuộc tính này không cần thiết để sắp xếp mà để tạo lại khóa được liên kết. Tuy nhiên, có những ví dụ thực tế về việc sử dụng nó trong ứng dụng Mail.ru Cloud để tránh đi sâu vào bối cảnh của các khung iOS cụ thể, tôi sẽ đưa ra một ví dụ hư cấu, nhưng dễ hiểu hơn.

Máy khách di động trên đám mây có một trang hiển thị tất cả các tệp và thư mục mà người dùng đã chia sẻ với người khác. Vì có tương đối ít tệp như vậy và có rất nhiều thông tin cụ thể về việc công khai liên quan đến chúng (được cấp quyền truy cập cho ai, với quyền gì, v.v.), nên sẽ không hợp lý khi đặt gánh nặng lên phần giá trị của tệp đó. mục trong bảng chính. Tuy nhiên, nếu bạn muốn hiển thị các tệp đó ngoại tuyến, thì bạn vẫn cần lưu trữ nó ở đâu đó. Một giải pháp tự nhiên là tạo một bảng riêng cho nó. Trong sơ đồ bên dưới, khóa của nó có tiền tố là "P" và phần giữ chỗ "propname" có thể được thay thế bằng giá trị cụ thể hơn "thông tin công khai".​

Tất cả siêu dữ liệu duy nhất, vì mục đích tạo bảng mới, được chuyển đến phần giá trị của bản ghi. Đồng thời, tôi không muốn sao chép dữ liệu về các tệp và thư mục đã được lưu trữ trong bảng chính. Thay vào đó, dữ liệu dư thừa được thêm vào khóa "P" ở dạng trường "ID nút" và "dấu thời gian". Nhờ chúng, bạn có thể tạo khóa chỉ mục, nhờ đó bạn có thể lấy khóa chính, nhờ đó, cuối cùng, bạn có thể lấy siêu dữ liệu của nút.

Phần kết luận

Chúng tôi đánh giá tích cực kết quả triển khai LMDB. Sau đó, số lượng ứng dụng bị đóng băng đã giảm 30%.

Kết quả của công việc được thực hiện đã tìm thấy phản hồi bên ngoài nhóm iOS. Hiện tại, một trong những phần "Tệp" chính trong ứng dụng Android cũng đã chuyển sang sử dụng LMDB và các phần khác đang trong quá trình hoàn thiện. Ngôn ngữ C, trong đó lưu trữ khóa-giá trị được triển khai, là một trợ giúp tốt để ban đầu làm cho ứng dụng liên kết xung quanh nó đa nền tảng bằng ngôn ngữ C ++. Để kết nối liền mạch thư viện C ++ kết quả với mã nền tảng trong Objective-C và Kotlin, một trình tạo mã đã được sử dụng Djinni từ Dropbox, nhưng đó là một câu chuyện khác.

Nguồn: www.habr.com