ในฤดูใบไม้ร่วงปี 2019 เหตุการณ์ที่รอคอยมานานเกิดขึ้นในทีม Mail.ru Cloud iOS ฐานข้อมูลหลักสำหรับการจัดเก็บสถานะแอปพลิเคชันถาวรนั้นค่อนข้างแปลกใหม่สำหรับโลกมือถือ ฐานข้อมูลที่แมปหน่วยความจำ Lightning (แอลเอ็มดีบี). ภายใต้การตัด ความสนใจของคุณจะได้รับการพิจารณาอย่างละเอียดในสี่ส่วน ก่อนอื่นเรามาพูดถึงสาเหตุของตัวเลือกที่ไม่สำคัญและยาก จากนั้น เรามาพิจารณาวาฬสามตัวที่เป็นหัวใจของสถาปัตยกรรม LMDB: ไฟล์ที่แมปหน่วยความจำ, แผนผัง B +, วิธีคัดลอกเมื่อเขียนสำหรับการดำเนินการธุรกรรมและมัลติเวอร์ชัน สุดท้ายสำหรับของหวาน - ส่วนที่ใช้งานได้จริง ในนั้น เราจะดูวิธีการออกแบบและปรับใช้สคีมาพื้นฐานกับตารางหลายตาราง รวมทั้งดัชนีหนึ่ง ที่ด้านบนของคีย์-ค่า 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 เราดูแลการวัดว่าอินเทอร์เฟซของแอปพลิเคชันของเราล่าช้าบ่อยเพียงใด เราไม่ได้ทำเพียงแค่นี้ เรามีข้อร้องเรียนมากขึ้นเรื่อย ๆ เกี่ยวกับความจริงที่ว่าบางครั้งแอปพลิเคชันหยุดตอบสนองต่อการกระทำของผู้ใช้: ไม่กดปุ่ม รายการไม่เลื่อน ฯลฯ เกี่ยวกับกลศาสตร์การวัด บอก บน AvitoTech ดังนั้นที่นี่ฉันจึงให้ลำดับของตัวเลขเท่านั้น

ผลการวัดกลายเป็นน้ำเย็นสำหรับเรา ปรากฎว่าปัญหาที่เกิดจากการค้างมีมากกว่าปัญหาอื่น ๆ หากก่อนที่จะทราบข้อเท็จจริงนี้ ตัวบ่งชี้ทางเทคนิคหลักด้านคุณภาพไม่มีข้อขัดข้อง จากนั้นจึงค่อยโฟกัสทีหลัง เปลี่ยน เมื่อแช่แข็งฟรี

มีการสร้าง แดชบอร์ดที่มีการค้าง และมีการใช้จ่าย เชิงปริมาณ и คุณภาพ การวิเคราะห์สาเหตุของพวกเขา ศัตรูหลักก็ชัดเจน - ตรรกะทางธุรกิจที่หนักหน่วงกำลังดำเนินการอยู่ในเธรดหลักของแอปพลิเคชัน ปฏิกิริยาตามธรรมชาติต่อความอัปยศอดสูนี้คือความปรารถนาอันแรงกล้าที่จะผลักมันเข้าไปในสายงาน สำหรับวิธีแก้ปัญหานี้อย่างเป็นระบบ เราหันไปใช้สถาปัตยกรรมแบบมัลติเธรดโดยอิงจากนักแสดงที่มีน้ำหนักเบา ฉันทุ่มเทให้เธอดัดแปลงเพื่อโลก iOS สองหัวข้อ ในกลุ่ม Twitter และ บทความเกี่ยวกับฮาเบร. ในส่วนหนึ่งของเรื่องราวปัจจุบัน ฉันต้องการเน้นแง่มุมต่างๆ ของการตัดสินใจที่มีอิทธิพลต่อการเลือกฐานข้อมูล​

โมเดลนักแสดงขององค์กรระบบถือว่ามัลติเธรดกลายเป็นสาระสำคัญที่สอง โมเดลวัตถุในนั้นต้องการข้ามขอบเขตของเธรด และพวกเขาไม่ได้ทำเช่นนี้ในบางครั้งและบางแห่ง แต่แทบจะตลอดเวลาและทุกที่

ฐานข้อมูลเป็นหนึ่งในองค์ประกอบที่สำคัญในแผนภาพที่นำเสนอ งานหลักคือการใช้รูปแบบมาโคร ฐานข้อมูลที่ใช้ร่วมกัน. หากในโลกขององค์กรใช้เพื่อจัดระเบียบการซิงโครไนซ์ข้อมูลระหว่างบริการ ในกรณีของสถาปัตยกรรมนักแสดง ข้อมูลระหว่างเธรด ดังนั้นเราจึงต้องการฐานข้อมูลดังกล่าวซึ่งทำงานในสภาพแวดล้อมแบบมัลติเธรดที่ไม่ก่อให้เกิดปัญหาแม้แต่น้อย โดยเฉพาะอย่างยิ่ง หมายความว่าออบเจกต์ที่ได้มาจากออบเจกต์นั้นต้องปลอดภัยต่อเธรดเป็นอย่างน้อย และไม่ควรเปลี่ยนรูปเลย อย่างที่คุณทราบสามารถใช้หลังพร้อมกันจากหลาย ๆ เธรดโดยไม่ต้องหันไปใช้การล็อคใด ๆ ซึ่งมีผลดีต่อประสิทธิภาพ

ปัจจัยสำคัญประการที่สองที่มีอิทธิพลต่อการเลือกฐานข้อมูลคือ Cloud API ของเรา ได้รับแรงบันดาลใจจากแนวทางคอมไพล์ในการซิงโครไนซ์ เช่นเดียวกับเขาที่เราเล็งไว้ API แรกแบบออฟไลน์ซึ่งดูเหมาะสมกว่าสำหรับไคลเอ็นต์ระบบคลาวด์ สันนิษฐานว่าพวกเขาจะสูบสถานะทั้งหมดของคลาวด์เพียงครั้งเดียว จากนั้นการซิงโครไนซ์ในกรณีส่วนใหญ่จะเกิดขึ้นผ่านการเปลี่ยนแปลงแบบต่อเนื่อง อนิจจา ความเป็นไปได้นี้ยังอยู่ในโซนทฤษฎีเท่านั้น และในทางปฏิบัติ ลูกค้ายังไม่ได้เรียนรู้วิธีการทำงานกับแพตช์ มีเหตุผลหลายประการสำหรับสิ่งนี้ ซึ่งเพื่อไม่ให้การแนะนำล่าช้า เราจะละไว้ในวงเล็บ ตอนนี้สิ่งที่น่าสนใจกว่ามากคือผลลัพธ์ของบทเรียนเกี่ยวกับสิ่งที่เกิดขึ้นเมื่อ API พูดว่า "A" และผู้บริโภคไม่ได้พูดว่า "B"

ดังนั้น หากคุณนึกภาพ git ซึ่งเมื่อรันคำสั่ง pull แทนที่จะใช้แพตช์กับสแน็ปช็อตในเครื่อง เปรียบเทียบสถานะเต็มกับเซิร์ฟเวอร์เต็ม คุณจะมีความคิดที่ถูกต้องพอสมควรเกี่ยวกับวิธีการซิงโครไนซ์ เกิดขึ้นในไคลเอนต์คลาวด์ เดาได้ง่ายว่าสำหรับการนำไปใช้นั้นจำเป็นต้องจัดสรรต้นไม้ DOM สองต้นในหน่วยความจำพร้อมข้อมูลเมตาเกี่ยวกับเซิร์ฟเวอร์และไฟล์ในเครื่องทั้งหมด ปรากฎว่าหากผู้ใช้เก็บไฟล์ไว้ 500 ไฟล์ในระบบคลาวด์ จำเป็นต้องสร้างและทำลายต้นไม้สองต้นที่มีโหนด 1 ล้านโหนดเพื่อซิงโครไนซ์ แต่แต่ละโหนดเป็นการรวมที่มีกราฟของวัตถุย่อย ในแง่นี้ ผลลัพธ์ของโปรไฟล์เป็นสิ่งที่คาดหวัง ปรากฎว่าแม้จะไม่คำนึงถึงอัลกอริทึมการผสานขั้นตอนในการสร้างและทำลายวัตถุขนาดเล็กจำนวนมากก็มีราคาค่อนข้างแพง สถานการณ์แย่ลงเนื่องจากข้อเท็จจริงที่ว่าการดำเนินการซิงโครไนซ์พื้นฐานรวมอยู่ในจำนวนมาก ของสคริปต์ผู้ใช้ เป็นผลให้เราแก้ไขเกณฑ์สำคัญที่สองในการเลือกฐานข้อมูล - ความสามารถในการดำเนินการ CRUD โดยไม่ต้องจัดสรรวัตถุแบบไดนามิก

ข้อกำหนดอื่น ๆ เป็นแบบดั้งเดิมมากกว่าและรายการทั้งหมดมีดังนี้

1. ความปลอดภัยของเธรด
2. การประมวลผลหลายตัว กำหนดโดยความต้องการที่จะใช้อินสแตนซ์ฐานข้อมูลเดียวกันเพื่อซิงโครไนซ์สถานะ ไม่เพียงแต่ระหว่างเธรดเท่านั้น แต่ยังรวมถึงระหว่างแอปพลิเคชันหลักและส่วนขยายของ iOS
3. ความสามารถในการแสดงเอนทิตีที่เก็บไว้เป็นวัตถุที่ไม่เปลี่ยนแปลง​...
4. ขาดการจัดสรรแบบไดนามิกภายในการดำเนินการ CRUD
5. การสนับสนุนธุรกรรมสำหรับคุณสมบัติพื้นฐาน กรดคำสำคัญ: ความเป็นปรมาณู ความสม่ำเสมอ การแยกตัว และความน่าเชื่อถือ
6. ความเร็วในกรณียอดนิยม

ด้วยข้อกำหนดชุดนี้ SQLite จึงเป็นตัวเลือกที่ดี อย่างไรก็ตาม ในส่วนหนึ่งของการศึกษาทางเลือก ฉันไปเจอหนังสือเล่มหนึ่ง "เริ่มต้นใช้งาน LevelDB". ภายใต้การนำของเธอ เกณฑ์มาตรฐานเขียนขึ้นเพื่อเปรียบเทียบความเร็วในการทำงานกับฐานข้อมูลต่างๆ ในสถานการณ์คลาวด์จริง ผลลัพธ์เกินความคาดหมายที่สุด ในกรณีที่ได้รับความนิยมมากที่สุด - รับเคอร์เซอร์ในรายการที่เรียงลำดับของไฟล์ทั้งหมดและรายการที่เรียงลำดับของไฟล์ทั้งหมดสำหรับไดเร็กทอรีที่กำหนด - LMDB เร็วกว่า SQLite ถึง 10 เท่า ทางเลือกก็ชัดเจน

2. การวางตำแหน่ง LMDB

LMDB เป็นไลบรารีขนาดเล็กมาก (เพียง 10 บรรทัด) ซึ่งใช้ชั้นฐานข้อมูลพื้นฐานที่ต่ำที่สุด ซึ่งก็คือที่เก็บข้อมูล

แผนภาพด้านบนแสดงให้เห็นว่าการเปรียบเทียบ LMDB กับ SQLite ซึ่งใช้ระดับที่สูงกว่านั้น โดยทั่วไปแล้วไม่ถูกต้องมากกว่า SQLite กับ Core Data มันจะยุติธรรมกว่าหากอ้างถึงเครื่องมือจัดเก็บข้อมูลเดียวกันกับคู่แข่งที่เท่าเทียมกัน - BerkeleyDB, LevelDB, Sophia, RocksDB และอื่น ๆ มีการพัฒนาแม้กระทั่งโดยที่ LMDB ทำหน้าที่เป็นส่วนประกอบเครื่องมือจัดเก็บข้อมูลสำหรับ SQLite การทดลองดังกล่าวครั้งแรกในปี 2012 ค่าใช้จ่าย ผู้เขียน LMDB ฮาเวิร์ด ชู. ผลการวิจัย กลายเป็นสิ่งที่น่าสนใจมากจนผู้ที่ชื่นชอบ OSS หยิบความคิดริเริ่มของเขาขึ้นมา และพบความต่อเนื่องในการเผชิญหน้ากับ LumoSQL. ในเดือนมกราคม 2020 ผู้เขียนโครงการนี้คือ Den Shearer นำเสนอ บน LinuxConfAu

การใช้งานหลักของ LMDB คือเป็นเครื่องมือสำหรับฐานข้อมูลแอปพลิเคชัน ห้องสมุดเป็นหนี้นักพัฒนา OpenLDAPซึ่งไม่พอใจอย่างมากกับ BerkeleyDB ที่เป็นพื้นฐานของโครงการ ผลักออกจากห้องสมุดต่ำต้อย บีทรีHoward Chu สามารถสร้างหนึ่งในทางเลือกที่ได้รับความนิยมมากที่สุดในยุคของเรา เขาอุทิศรายงานที่ยอดเยี่ยมให้กับเรื่องนี้ เช่นเดียวกับโครงสร้างภายในของ LMDB "ฐานข้อมูลที่แมปหน่วยความจำ Lightning". ลีโอนิด ยูริเยฟ (หรืออีกชื่อหนึ่งว่า ยอ) จาก Positive Technologies ในการพูดคุยของเขาที่ Highload 2015 "เครื่องยนต์ LMDB เป็นแชมป์พิเศษ". ในนั้น เขาพูดถึง LMDB ในบริบทของงานที่คล้ายกันในการนำ ReOpenLDAP ไปใช้ และ LevelDB ก็ผ่านคำวิจารณ์เปรียบเทียบมาแล้ว ผลจากการนำไปใช้งาน Positive Technologies ยังได้รับการพัฒนาอย่างแข็งขัน เอ็มดีบีเอ็กซ์ ด้วยคุณสมบัติที่อร่อยมาก การเพิ่มประสิทธิภาพ และ แก้ไขข้อผิดพลาด.

LMDB มักใช้เป็นที่เก็บข้อมูลเช่นกัน ตัวอย่างเช่น เบราว์เซอร์ Mozilla Firefox เลือก สำหรับความต้องการหลายประการ และตั้งแต่ Xcode เวอร์ชัน 9 เป็นต้นมา ที่ต้องการ SQLite เพื่อจัดเก็บดัชนี

เครื่องยนต์ยังติดอยู่ในโลกของการพัฒนามือถือ ร่องรอยการใช้งานสามารถ เพื่อค้นหา ในไคลเอ็นต์ iOS สำหรับ Telegram LinkedIn ก้าวไปอีกขั้นและเลือก LMDB เป็นที่เก็บข้อมูลเริ่มต้นสำหรับเฟรมเวิร์กการแคชข้อมูลที่ผลิตขึ้นเองซึ่งก็คือ Rocket Data บอก ในบทความในปี 2016

LMDB ประสบความสำเร็จในการต่อสู้เพื่อตำแหน่งในดวงอาทิตย์ในช่องที่ BerkeleyDB ทิ้งไว้หลังจากการเปลี่ยนแปลงภายใต้การควบคุมของ Oracle ห้องสมุดแห่งนี้เป็นที่ชื่นชอบในด้านความเร็วและความน่าเชื่อถือ แม้จะเปรียบเทียบกับห้องสมุดประเภทเดียวกันก็ตาม อย่างที่คุณทราบ ไม่มีอาหารกลางวันฟรี และฉันต้องการเน้นย้ำถึงการแลกเปลี่ยนที่คุณจะต้องเผชิญเมื่อเลือกระหว่าง LMDB และ SQLite แผนภาพด้านบนแสดงให้เห็นอย่างชัดเจนถึงความเร็วที่เพิ่มขึ้น ประการแรก เราไม่จ่ายเงินสำหรับการเพิ่มชั้นของสิ่งที่เป็นนามธรรมที่ด้านบนของที่เก็บข้อมูลดิสก์ แน่นอนว่าในสถาปัตยกรรมที่ดี คุณยังไม่สามารถทำได้หากไม่มีมัน และมันจะปรากฏในรหัสแอปพลิเคชันอย่างหลีกเลี่ยงไม่ได้ แต่จะบางลงมาก พวกเขาจะไม่มีคุณสมบัติที่ไม่จำเป็นสำหรับแอปพลิเคชันเฉพาะ ตัวอย่างเช่น การรองรับการสืบค้นในภาษา SQL ประการที่สอง เป็นไปได้ที่จะใช้การแมปการดำเนินการของแอปพลิเคชันอย่างเหมาะสมกับคำขอไปยังที่เก็บข้อมูลดิสก์ ถ้า SQLite ในงานของฉัน มาจากความต้องการเฉลี่ยของแอปพลิเคชันทั่วไป ดังนั้นคุณในฐานะผู้พัฒนาแอปพลิเคชันจึงตระหนักดีถึงสถานการณ์การโหลดหลัก สำหรับโซลูชันที่มีประสิทธิผลมากขึ้น คุณจะต้องจ่ายป้ายราคาที่เพิ่มขึ้นสำหรับทั้งการพัฒนาโซลูชันเริ่มต้นและการสนับสนุนที่ตามมา

3. LMDB สามวาฬ

หลังจากดู LMDB จากมุมสูงแล้ว ก็ถึงเวลาลงลึก สามส่วนถัดไปจะอุทิศให้กับการวิเคราะห์วาฬหลักที่สถาปัตยกรรมสตอเรจวางอยู่:

1. ไฟล์ที่แมปหน่วยความจำเป็นกลไกสำหรับการทำงานกับดิสก์และการซิงโครไนซ์โครงสร้างข้อมูลภายใน
2. B+-tree เป็นองค์กรของโครงสร้างข้อมูลที่เก็บไว้
3. Copy-on-write เป็นแนวทางเพื่อให้คุณสมบัติการทำธุรกรรมของ ACID และ multiversioning

3.1. ปลาวาฬ #1. ไฟล์ที่แมปหน่วยความจำ

ไฟล์ที่แมปหน่วยความจำเป็นองค์ประกอบทางสถาปัตยกรรมที่สำคัญที่ปรากฏในชื่อของที่เก็บด้วยซ้ำ ปัญหาของการแคชและการซิงโครไนซ์การเข้าถึงข้อมูลที่เก็บไว้ล้วนขึ้นอยู่กับความเมตตาของระบบปฏิบัติการ LMDB ไม่มีแคชภายในตัวมันเอง นี่เป็นการตัดสินใจอย่างมีสติของผู้เขียน เนื่องจากการอ่านข้อมูลโดยตรงจากไฟล์ที่แมปทำให้คุณสามารถลดขั้นตอนต่างๆ มากมายในการติดตั้งเอ็นจิ้น ด้านล่างนี้ยังห่างไกลจากรายชื่อบางส่วนทั้งหมด

1. การรักษาความสอดคล้องของข้อมูลในที่จัดเก็บเมื่อทำงานกับมันจากหลาย ๆ กระบวนการกลายเป็นความรับผิดชอบของระบบปฏิบัติการ ในหัวข้อถัดไป จะกล่าวถึงกลไกนี้อย่างละเอียดพร้อมรูปภาพ
2. การไม่มีแคชช่วยลด LMDB ของโอเวอร์เฮดที่เกี่ยวข้องกับการจัดสรรแบบไดนามิกโดยสิ้นเชิง การอ่านข้อมูลในทางปฏิบัติคือการตั้งค่าตัวชี้ไปยังที่อยู่ที่ถูกต้องในหน่วยความจำเสมือนและไม่มีอะไรเพิ่มเติม ฟังดูเหมือนเพ้อฝัน แต่ในแหล่งที่เก็บ การเรียกใช้ calloc ทั้งหมดจะรวมอยู่ในฟังก์ชันการกำหนดค่าที่เก็บ
3. การไม่มีแคชหมายถึงไม่มีการล็อกที่เกี่ยวข้องกับการซิงโครไนซ์เพื่อเข้าถึงแคช Reader ซึ่งสามารถมีหมายเลขตามอำเภอใจได้ในเวลาเดียวกัน จะไม่พบ mutex เดียวระหว่างทางไปยังข้อมูล ด้วยเหตุนี้ ความเร็วในการอ่านจึงมีความสามารถในการปรับขนาดเชิงเส้นในอุดมคติในแง่ของจำนวนซีพียู ใน LMDB จะซิงโครไนซ์การดำเนินการแก้ไขเท่านั้น สามารถมีผู้เขียนได้ครั้งละหนึ่งคนเท่านั้น
4. ตรรกะการแคชและการซิงโครไนซ์ขั้นต่ำจะบันทึกรหัสจากข้อผิดพลาดประเภทที่ซับซ้อนอย่างยิ่งที่เกี่ยวข้องกับการทำงานในสภาพแวดล้อมแบบมัลติเธรด มีการศึกษาฐานข้อมูลที่น่าสนใจสองรายการในการประชุม Usenix OSDI 2014: "ระบบไฟล์ทั้งหมดไม่ได้ถูกสร้างขึ้นมาอย่างเท่าเทียมกัน: ความซับซ้อนของการสร้างแอปพลิเคชันที่สอดคล้องกับความผิดพลาด" и ทรมานฐานข้อมูลเพื่อความสนุกและผลกำไร. จากข้อมูลเหล่านี้ คุณจะได้รับข้อมูลเกี่ยวกับทั้งความน่าเชื่อถือที่ไม่เคยมีมาก่อนของ LMDB และการนำคุณสมบัติ ACID ของธุรกรรมไปใช้อย่างไร้ที่ติ ซึ่งเหนือกว่าใน SQLite เดียวกัน
5. ความเรียบง่ายของ LMDB ทำให้สามารถแสดงรหัสของเครื่องในแคช L1 ของโปรเซสเซอร์ได้อย่างสมบูรณ์ด้วยลักษณะความเร็วที่เป็นผลลัพธ์

น่าเสียดายที่ใน iOS ไฟล์ที่แมปหน่วยความจำนั้นไม่เป็นสีดอกกุหลาบอย่างที่เราต้องการ หากต้องการพูดคุยเกี่ยวกับข้อเสียที่เกี่ยวข้องอย่างมีสติมากขึ้นจำเป็นต้องระลึกถึงหลักการทั่วไปสำหรับการนำกลไกนี้ไปใช้ในระบบปฏิบัติการ

ข้อมูลทั่วไปเกี่ยวกับไฟล์ที่แมปหน่วยความจำ

ระบบปฏิบัติการจะเชื่อมโยงเอนทิตีที่เรียกว่ากระบวนการกับแอปพลิเคชันปฏิบัติการแต่ละรายการ แต่ละกระบวนการได้รับการจัดสรรช่วงที่อยู่ติดกันซึ่งวางทุกสิ่งที่จำเป็นในการทำงาน ที่อยู่ต่ำสุดมีส่วนที่มีโค้ดและข้อมูลและทรัพยากรแบบฮาร์ดโค้ด ถัดมาคือบล็อกพื้นที่ที่อยู่แบบไดนามิกที่เติบโตขึ้นเรื่อยๆ ซึ่งเรารู้จักกันดีในชื่อฮีป ประกอบด้วยที่อยู่ของเอนทิตีที่ปรากฏระหว่างการทำงานของโปรแกรม ที่ด้านบนคือพื้นที่หน่วยความจำที่ใช้โดยแอปพลิเคชันสแต็ก ไม่ว่าจะขยายใหญ่ขึ้นหรือย่อลง หรืออีกนัยหนึ่งก็คือ ขนาดของมันยังมีลักษณะไดนามิกอีกด้วย เพื่อไม่ให้สแต็กและฮีปถูกผลักและรบกวนซึ่งกันและกันพวกมันจะถูกแยกออกจากกันที่ปลายด้านต่างๆ ของ address space มีช่องระหว่างส่วนไดนามิกทั้งสองที่ด้านบนและด้านล่าง ที่อยู่ในส่วนตรงกลางนี้ถูกใช้โดยระบบปฏิบัติการเพื่อเชื่อมโยงกับกระบวนการของเอนทิตีต่างๆ โดยเฉพาะอย่างยิ่ง มันสามารถจับคู่ชุดที่อยู่ต่อเนื่องกับไฟล์บนดิสก์ ไฟล์ดังกล่าวเรียกว่าไฟล์แมปหน่วยความจำ.

พื้นที่แอดเดรสที่จัดสรรให้กับกระบวนการนั้นมีขนาดใหญ่มาก ในทางทฤษฎี จำนวนแอดเดรสจะถูกจำกัดด้วยขนาดของพอยน์เตอร์เท่านั้น ซึ่งกำหนดโดย bitness ของระบบ หากหน่วยความจำกายภาพถูกกำหนดให้เป็น 1-in-1 กระบวนการแรกจะกิน RAM ทั้งหมด และจะไม่มีคำถามเกี่ยวกับการทำงานหลายอย่างพร้อมกัน

อย่างไรก็ตาม เราทราบจากประสบการณ์ว่าระบบปฏิบัติการสมัยใหม่สามารถเรียกใช้กระบวนการต่างๆ ได้มากเท่าที่คุณต้องการในเวลาเดียวกัน สิ่งนี้เป็นไปได้เนื่องจากพวกเขาจัดสรรหน่วยความจำจำนวนมากเพื่อประมวลผลบนกระดาษเท่านั้น แต่ในความเป็นจริงพวกเขาโหลดลงในหน่วยความจำกายภาพหลักเฉพาะส่วนที่ต้องการที่นี่และตอนนี้ ดังนั้นหน่วยความจำที่เกี่ยวข้องกับกระบวนการจึงเรียกว่าเสมือน

ระบบปฏิบัติการจัดระเบียบหน่วยความจำเสมือนและหน่วยความจำกายภาพเป็นหน้าที่มีขนาดที่แน่นอน ทันทีที่มีความต้องการหน่วยความจำเสมือนบางหน้าระบบปฏิบัติการจะโหลดลงในหน่วยความจำกายภาพและวางการติดต่อระหว่างกันในตารางพิเศษ หากไม่มีช่องว่าง หน้าที่โหลดไว้ก่อนหน้านี้หน้าใดหน้าหนึ่งจะถูกคัดลอกไปยังดิสก์ และหน้าที่ร้องขอจะเข้ามาแทนที่ ขั้นตอนนี้ซึ่งเราจะย้อนกลับไปในไม่ช้านี้เรียกว่าการแลกเปลี่ยน รูปภาพด้านล่างแสดงกระบวนการที่อธิบายไว้ ในนั้น หน้า A ที่มีที่อยู่ 0 ถูกโหลดและวางบนหน้าหน่วยความจำหลักที่มีที่อยู่ 4 ข้อเท็จจริงนี้สะท้อนให้เห็นในตารางการติดต่อในเซลล์หมายเลข 0​

ด้วยไฟล์ที่แมปหน่วยความจำ เรื่องราวจะเหมือนกันทุกประการ ตามเหตุผลแล้ว พวกเขาควรจะวางอย่างต่อเนื่องและทั้งหมดในพื้นที่ที่อยู่เสมือน อย่างไรก็ตามพวกเขาจะเข้าสู่หน่วยความจำกายภาพทีละหน้าและตามต้องการเท่านั้น การแก้ไขหน้าดังกล่าวจะซิงโครไนซ์กับไฟล์บนดิสก์ ดังนั้น คุณสามารถดำเนินการกับไฟล์ I / O เพียงแค่ทำงานกับไบต์ในหน่วยความจำ การเปลี่ยนแปลงทั้งหมดจะถูกถ่ายโอนโดยอัตโนมัติโดยเคอร์เนลของระบบปฏิบัติการไปยังไฟล์ต้นฉบับ​
†<
ภาพด้านล่างแสดงวิธีที่ LMDB ซิงโครไนซ์สถานะเมื่อทำงานกับฐานข้อมูลจากกระบวนการต่างๆ ด้วยการแมปหน่วยความจำเสมือนของกระบวนการต่างๆ ลงในไฟล์เดียวกัน เรากำหนดให้ระบบปฏิบัติการต้องซิงโครไนซ์บล็อกของพื้นที่แอดเดรสกับแต่ละช่วงเป็นระยะๆ ซึ่งเป็นลักษณะของ LMDB​
†<

ข้อแตกต่างที่สำคัญคือ LMDB แก้ไขไฟล์ข้อมูลตามค่าเริ่มต้นผ่านกลไกการเรียกระบบการเขียน และตัวไฟล์จะแสดงในโหมดอ่านอย่างเดียว วิธีการนี้มีนัยสำคัญสองประการ

ผลลัพธ์แรกพบได้ทั่วไปในระบบปฏิบัติการทั้งหมด สาระสำคัญคือการเพิ่มการป้องกันความเสียหายที่ไม่ได้ตั้งใจไปยังฐานข้อมูลด้วยรหัสที่ไม่ถูกต้อง อย่างที่คุณทราบ คำสั่งเรียกทำงานของกระบวนการมีอิสระในการเข้าถึงข้อมูลได้จากทุกที่ในพื้นที่แอดเดรส ในขณะเดียวกัน อย่างที่เราเพิ่งจำได้ การแสดงไฟล์ในโหมดอ่าน-เขียนหมายความว่าคำสั่งใด ๆ ก็สามารถแก้ไขเพิ่มเติมได้เช่นกัน หากเธอทำสิ่งนี้โดยไม่ได้ตั้งใจ เช่น พยายามเขียนทับองค์ประกอบอาร์เรย์ที่ดัชนีที่ไม่มีอยู่จริง ด้วยวิธีนี้ เธอสามารถเปลี่ยนไฟล์ที่แมปไปยังที่อยู่นี้โดยไม่ได้ตั้งใจ ซึ่งจะนำไปสู่การเสียหายของฐานข้อมูล หากไฟล์แสดงในโหมดอ่านอย่างเดียว ความพยายามที่จะเปลี่ยนพื้นที่ที่อยู่ที่เกี่ยวข้องจะทำให้โปรแกรมหยุดทำงานด้วยสัญญาณ SIGSEGVและไฟล์จะยังคงอยู่เหมือนเดิม

ผลลัพธ์ที่สองมีไว้สำหรับ iOS โดยเฉพาะแล้ว ทั้งผู้เขียนและแหล่งข้อมูลอื่นไม่ได้กล่าวถึงอย่างชัดเจน แต่ถ้าไม่มี LMDB ก็ไม่เหมาะสำหรับการรันบนระบบปฏิบัติการมือถือนี้ ส่วนถัดไปจะอุทิศให้กับการพิจารณา

ข้อมูลเฉพาะของไฟล์ที่แมปหน่วยความจำใน iOS

ในปี 2018 มีรายงานที่ยอดเยี่ยมที่ WWDC เจาะลึกหน่วยความจำ iOS. มันบอกว่าใน iOS หน้าทั้งหมดที่อยู่ในหน่วยความจำกายภาพเป็นของหนึ่งใน 3 ประเภท: สกปรก บีบอัด และสะอาด

หน่วยความจำสะอาดคือชุดของหน้าที่สามารถสลับออกจากหน่วยความจำกายภาพได้อย่างปลอดภัย ข้อมูลที่มีอยู่สามารถโหลดซ้ำจากแหล่งเดิมได้ตามต้องการ ไฟล์ที่แมปหน่วยความจำแบบอ่านอย่างเดียวจัดอยู่ในประเภทนี้ iOS ไม่กลัวที่จะยกเลิกการโหลดหน้าที่แมปกับไฟล์จากหน่วยความจำเมื่อใดก็ได้ เนื่องจากรับประกันว่าจะซิงโครไนซ์กับไฟล์บนดิสก์
†<
หน้าที่แก้ไขทั้งหมดจะเข้าสู่หน่วยความจำสกปรกไม่ว่าจะอยู่ที่เดิม โดยเฉพาะอย่างยิ่ง ไฟล์ที่แมปหน่วยความจำที่แก้ไขโดยการเขียนไปยังหน่วยความจำเสมือนที่เกี่ยวข้องจะถูกจัดประเภทในลักษณะนี้ด้วย กำลังเปิด LMDB ด้วยแฟล็ก MDB_WRITEMAPหลังจากทำการเปลี่ยนแปลงคุณจะเห็นด้วยตัวคุณเอง.

ทันทีที่แอปพลิเคชันเริ่มใช้หน่วยความจำกายภาพมากเกินไป iOS จะบีบอัดหน้าที่สกปรก คอลเลกชันของหน่วยความจำที่ถูกครอบครองโดยเพจที่สกปรกและถูกบีบอัดคือสิ่งที่เรียกว่ารอยเท้าหน่วยความจำของแอปพลิเคชัน เมื่อถึงค่าเกณฑ์ที่กำหนด OOM killer system daemon จะเข้ามาหลังจากกระบวนการและบังคับให้ยุติ นี่คือลักษณะเฉพาะของ iOS เมื่อเปรียบเทียบกับระบบปฏิบัติการเดสก์ท็อป ในทางตรงกันข้าม iOS ไม่มีการลดรอยเท้าของหน่วยความจำโดยการสลับหน้าจากหน่วยความจำกายภาพไปยังดิสก์ มีเพียงเหตุผลเท่านั้นที่สามารถเดาได้ บางทีขั้นตอนสำหรับการย้ายหน้าไปยังดิสก์และย้อนกลับอย่างเข้มข้นนั้นใช้พลังงานมากเกินไปสำหรับอุปกรณ์พกพา หรือ iOS ช่วยประหยัดทรัพยากรในการเขียนเซลล์ใหม่ในไดรฟ์ SSD หรือบางทีนักออกแบบอาจไม่พอใจกับประสิทธิภาพโดยรวมของระบบ เปลี่ยนไปเรื่อยๆ อย่างไรก็ตามข้อเท็จจริงยังคงอยู่

ข่าวดีที่กล่าวถึงก่อนหน้านี้คือ LMDB ไม่ได้ใช้กลไก mmap เพื่ออัปเดตไฟล์ตามค่าเริ่มต้น ตามมาว่าข้อมูลที่แสดงผลนั้นจัดอยู่ในประเภทหน่วยความจำสะอาดโดย iOS และไม่มีส่วนทำให้หน่วยความจำเสียหาย สามารถตรวจสอบได้โดยใช้เครื่องมือ Xcode ที่เรียกว่า VM Tracker ภาพหน้าจอด้านล่างแสดงสถานะหน่วยความจำเสมือนของแอปพลิเคชัน iOS Cloud ระหว่างการทำงาน ในตอนเริ่มต้น อินสแตนซ์ LMDB 2 รายการได้รับการเริ่มต้นในนั้น อันแรกได้รับอนุญาตให้แมปไฟล์กับหน่วยความจำเสมือน 1GiB อันที่สอง - 512MiB แม้ว่าที่เก็บข้อมูลทั้งสองจะใช้หน่วยความจำภายในจำนวนหนึ่ง แต่ก็ไม่มีส่วนทำให้ขนาดสกปรก

ตอนนี้เป็นเวลาสำหรับข่าวร้าย ด้วยกลไกการสลับในระบบปฏิบัติการเดสก์ท็อป 64 บิต แต่ละกระบวนการสามารถใช้พื้นที่ที่อยู่เสมือนได้มากเท่ากับพื้นที่ว่างบนฮาร์ดดิสก์ที่อนุญาตให้มีการสลับได้ การแทนที่ swap ด้วยการบีบอัดใน iOS จะลดค่าสูงสุดตามทฤษฎีลงอย่างมาก ตอนนี้กระบวนการมีชีวิตทั้งหมดต้องพอดีกับหน่วยความจำหลัก (RAM อ่าน) และกระบวนการทั้งหมดที่ไม่พอดีจะถูกยกเลิกโดยบังคับ ดังมีกล่าวไว้ข้างต้น รายงาน, และใน เอกสารราชการ. ด้วยเหตุนี้ iOS จึงจำกัดจำนวนหน่วยความจำที่พร้อมสำหรับการจัดสรรผ่าน mmap อย่างมาก ที่นี่ ที่นี่ คุณสามารถดูขีดจำกัดเชิงประจักษ์เกี่ยวกับจำนวนหน่วยความจำที่สามารถจัดสรรบนอุปกรณ์ต่างๆ โดยใช้การเรียกระบบนี้ ในสมาร์ทโฟนรุ่นที่ทันสมัยที่สุด iOS มีขนาดใหญ่ถึง 2 กิกะไบต์และบน iPad รุ่นยอดนิยม - ถึง 4 แน่นอนว่าในทางปฏิบัติคุณต้องมุ่งเน้นไปที่รุ่นอุปกรณ์ที่รองรับที่อายุน้อยที่สุดซึ่งทุกอย่างน่าเศร้ามาก ยิ่งแย่ไปกว่านั้น เมื่อดูที่สถานะหน่วยความจำของแอปพลิเคชันใน VM Tracker คุณจะพบว่า LMDB นั้นห่างไกลจากหน่วยความจำที่แมปหน่วยความจำเพียงตัวเดียวที่อ้างสิทธิ์ ตัวจัดสรรระบบ ไฟล์ทรัพยากร อิมเมจเฟรมเวิร์ก และผู้ล่าที่มีขนาดเล็กกว่าอื่นๆ จะกินส่วนที่ดี

จากการทดลองในระบบคลาวด์ เราได้ค่าการประนีประนอมของหน่วยความจำที่จัดสรรโดย LMDB ดังต่อไปนี้: 384 เมกะไบต์สำหรับอุปกรณ์ 32 บิต และ 768 สำหรับอุปกรณ์ 64 บิต หลังจากใช้โวลุ่มนี้หมดแล้ว การดำเนินการแก้ไขใดๆ จะเริ่มดำเนินการให้เสร็จสมบูรณ์ด้วยรหัส MDB_MAP_FULL. เราสังเกตเห็นข้อผิดพลาดดังกล่าวในการตรวจสอบของเรา แต่ก็เล็กน้อยพอที่จะละเลยในขั้นตอนนี้

เหตุผลที่ไม่ชัดเจนสำหรับการใช้หน่วยความจำมากเกินไปโดยการจัดเก็บอาจเป็นธุรกรรมที่มีอายุการใช้งานยาวนาน เพื่อทำความเข้าใจว่าปรากฏการณ์ทั้งสองนี้เกี่ยวข้องกันอย่างไร จะช่วยให้เราพิจารณาวาฬ LMDB ที่เหลืออีกสองตัว

3.2. ปลาวาฬ #2. B+-ต้นไม้

หากต้องการจำลองตารางที่อยู่ด้านบนของที่เก็บคีย์-ค่า การดำเนินการต่อไปนี้ต้องแสดงอยู่ใน API ของตาราง:

1. การแทรกองค์ประกอบใหม่
2. ค้นหาองค์ประกอบด้วยคีย์ที่กำหนด
3. การลบองค์ประกอบ
4. วนซ้ำตามช่วงคีย์ตามลำดับการจัดเรียง

โครงสร้างข้อมูลที่ง่ายที่สุดที่สามารถนำการดำเนินการทั้งสี่ไปใช้ได้อย่างง่ายดายคือแผนผังการค้นหาแบบไบนารี แต่ละโหนดเป็นคีย์ที่แบ่งชุดย่อยทั้งหมดของคีย์ย่อยออกเป็นสองทรีย่อย ทางซ้ายคืออันที่เล็กกว่าพาเรนต์และทางขวา - อันที่ใหญ่กว่า การได้รับชุดกุญแจที่สั่งทำได้ผ่านหนึ่งในเส้นทางผ่านต้นไม้แบบคลาสสิก​

ไบนารีทรีมีข้อบกพร่องพื้นฐาน XNUMX ประการที่ป้องกันไม่ให้มีผลเป็นโครงสร้างข้อมูลบนดิสก์ ประการแรก ระดับความสมดุลนั้นไม่สามารถคาดเดาได้ มีความเสี่ยงมากที่จะได้รับต้นไม้ซึ่งความสูงของกิ่งก้านที่แตกต่างกันอาจแตกต่างกันมาก ซึ่งทำให้ความซับซ้อนของอัลกอริทึมของการค้นหาแย่ลงอย่างมากเมื่อเทียบกับที่คาดไว้ ประการที่สอง การเชื่อมโยงข้ามจำนวนมากระหว่างโหนดทำให้ไบนารีทรีของท้องถิ่นในหน่วยความจำขาดหายไป ปิดโหนด (ในแง่ของการเชื่อมโยงระหว่างโหนด) สามารถอยู่ในเพจที่แตกต่างกันโดยสิ้นเชิงในหน่วยความจำเสมือน ผลที่ตามมาก็คือ แม้แต่การข้ามไปยังโหนดที่อยู่ใกล้เคียงหลายๆ โหนดในแผนผังแบบง่ายๆ ก็อาจจำเป็นต้องไปที่หน้าในจำนวนที่ใกล้เคียงกัน นี่เป็นปัญหาแม้เมื่อเราพูดถึงประสิทธิภาพของไบนารีทรีในฐานะโครงสร้างข้อมูลในหน่วยความจำ เนื่องจากการหมุนหน้าอย่างต่อเนื่องในแคชของโปรเซสเซอร์นั้นไม่ถูก เมื่อพูดถึงการดึงเพจที่เกี่ยวข้องกับโหนดจากดิสก์บ่อยๆ สิ่งต่างๆ จะเลวร้ายมาก น่าเสียดาย.

B-tree ซึ่งเป็นวิวัฒนาการของ binary tree ช่วยแก้ปัญหาที่ระบุไว้ในย่อหน้าก่อนหน้า อย่างแรก พวกเขาสร้างสมดุลในตัวเอง ประการที่สอง โหนดแต่ละโหนดแยกชุดของคีย์ลูกไม่ใช่ 2 แต่แยกออกเป็นชุดย่อยที่สั่งโดย M และจำนวน M อาจมีขนาดค่อนข้างใหญ่ตามลำดับหลายร้อยหรือหลายพัน

ด้วยวิธีนี้:

1. แต่ละโหนดมีคีย์ที่สั่งซื้อแล้วจำนวนมากและทรีต่ำมาก
2. ต้นไม้ได้รับคุณสมบัติของพื้นที่ในหน่วยความจำ เนื่องจากคีย์ที่มีค่าใกล้เคียงกันจะอยู่ติดกันโดยธรรมชาติบนโหนดเดียวหรือโหนดข้างเคียง
3. ลดจำนวนของโหนดการขนส่งเมื่อลงจากต้นไม้ระหว่างการค้นหา
4. ลดจำนวนโหนดเป้าหมายที่อ่านสำหรับการค้นหาช่วง เนื่องจากโหนดแต่ละโหนดมีคีย์ที่สั่งซื้อจำนวนมากอยู่แล้ว

LMDB ใช้ตัวแปรของ B-tree ที่เรียกว่า B+ tree เพื่อเก็บข้อมูล แผนภาพด้านบนแสดงโหนดสามประเภทที่มี:

1. ที่ด้านบนคือราก มันไม่มีอะไรเป็นรูปธรรมมากไปกว่าแนวคิดของฐานข้อมูลภายในที่เก็บ ภายในอินสแตนซ์ LMDB เดียว คุณสามารถสร้างฐานข้อมูลหลายฐานข้อมูลที่ใช้พื้นที่ที่อยู่เสมือนที่แมปร่วมกัน แต่ละคนเริ่มต้นจากรากของตัวเอง
2. ที่ระดับต่ำสุดคือใบไม้ (ใบไม้) มีเพียงคู่คีย์-ค่าที่จัดเก็บไว้ในฐานข้อมูลเท่านั้น อย่างไรก็ตาม นี่คือลักษณะเฉพาะของต้นไม้ B+ ถ้า B-tree ปกติเก็บส่วนของค่าไว้ที่โหนดของทุกระดับ ดังนั้น B+-variation จะอยู่ที่ค่าต่ำสุดเท่านั้น หลังจากแก้ไขข้อเท็จจริงนี้แล้ว ต่อไปนี้เราจะเรียกประเภทย่อยของแผนผังที่ใช้ใน LMDB ว่า B-tree
3. ระหว่าง root และ leaf มีระดับเทคนิคตั้งแต่ 0 ระดับขึ้นไปพร้อมโหนดการนำทาง (สาขา) หน้าที่ของพวกเขาคือแบ่งชุดกุญแจที่เรียงไว้ระหว่างใบไม้

ในทางกายภาพ โหนดคือบล็อกของหน่วยความจำที่มีความยาวที่กำหนดไว้ล่วงหน้า ขนาดของพวกเขาคือขนาดของหน้าหน่วยความจำหลายเท่าในระบบปฏิบัติการซึ่งเราได้พูดถึงข้างต้น โครงสร้างโหนดแสดงไว้ด้านล่าง ส่วนหัวประกอบด้วยข้อมูลเมตา ซึ่งตัวอย่างที่ชัดเจนที่สุดคือการตรวจสอบ ถัดมาข้อมูลเกี่ยวกับการชดเชย ซึ่งรวมถึงเซลล์ที่มีข้อมูลอยู่ บทบาทของข้อมูลสามารถเป็นได้ทั้งคีย์หากเรากำลังพูดถึงโหนดการนำทางหรือคู่คีย์-ค่าทั้งหมดในกรณีของ leaf คุณสามารถอ่านเพิ่มเติมเกี่ยวกับโครงสร้างของเพจได้ในผลงาน "การประเมินร้านค้าคีย์-ค่าที่มีประสิทธิภาพสูง".

หลังจากจัดการกับเนื้อหาภายในของโหนดเพจแล้ว เราจะนำเสนอทรี LMDB B-tree ในรูปแบบที่ง่ายขึ้นในรูปแบบต่อไปนี้

เพจที่มีโหนดจะถูกจัดเรียงตามลำดับบนดิสก์ หน้าที่มีจำนวนสูงกว่าจะอยู่ที่ส่วนท้ายของไฟล์ หน้าเมตาที่เรียกว่า (หน้าเมตา) มีข้อมูลเกี่ยวกับการชดเชยซึ่งสามารถใช้เพื่อค้นหารากของต้นไม้ทั้งหมด เมื่อเปิดไฟล์ LMDB จะสแกนไฟล์ทีละหน้าตั้งแต่ต้นจนจบเพื่อค้นหาเมตาเพจที่ถูกต้องและค้นหาฐานข้อมูลที่มีอยู่ผ่านไฟล์

ตอนนี้เมื่อมีความคิดเกี่ยวกับโครงสร้างเชิงตรรกะและกายภาพขององค์กรข้อมูลแล้ว เราสามารถพิจารณาวาฬตัวที่สามของ LMDB ต่อไปได้ ด้วยความช่วยเหลือของการปรับเปลี่ยนที่เก็บข้อมูลทั้งหมดเกิดขึ้นทางธุรกรรมและแยกออกจากกันทำให้ฐานข้อมูลโดยรวมมีคุณสมบัติการคูณด้วย

3.3. ปลาวาฬ #3. คัดลอกเมื่อเขียน

การดำเนินการ B-tree บางอย่างเกี่ยวข้องกับการเปลี่ยนแปลงโหนดทั้งชุด ตัวอย่างหนึ่งคือการเพิ่มคีย์ใหม่ให้กับโหนดที่มีความจุสูงสุดแล้ว ในกรณีนี้ อันดับแรก จำเป็นต้องแยกโหนดออกเป็นสองโหนด และประการที่สอง เพื่อเพิ่มลิงก์ไปยังโหนดย่อยที่แยกออกจากโหนดย่อยในพาเรนต์ ขั้นตอนนี้อาจเป็นอันตรายมาก หากด้วยเหตุผลบางประการ (เครื่องขัดข้อง ไฟดับ ฯลฯ) การเปลี่ยนแปลงเพียงบางส่วนจากซีรีส์นี้เกิดขึ้น ต้นไม้จะยังคงอยู่ในสถานะที่ไม่สอดคล้องกัน

วิธีแก้ปัญหาดั้งเดิมวิธีหนึ่งในการสร้างความทนทานต่อความผิดพลาดของฐานข้อมูลคือการเพิ่มโครงสร้างข้อมูลบนดิสก์เพิ่มเติม บันทึกธุรกรรม หรือที่เรียกว่าบันทึกการเขียนล่วงหน้า (WAL) ถัดจาก B-tree มันเป็นไฟล์ที่ส่วนท้ายของการดำเนินการที่ตั้งใจไว้ก่อนที่จะทำการแก้ไข B-tree นั้นจะถูกเขียนขึ้น ดังนั้น หากตรวจพบความเสียหายของข้อมูลระหว่างการวินิจฉัยตัวเอง ฐานข้อมูลจะพิจารณาบันทึกเพื่อล้างตัวเอง

LMDB ได้เลือกวิธีอื่นเป็นกลไกการยอมรับข้อผิดพลาด ซึ่งเรียกว่าการคัดลอกเมื่อเขียน สาระสำคัญของมันคือแทนที่จะอัปเดตข้อมูลในหน้าที่มีอยู่ ขั้นแรกจะคัดลอกข้อมูลทั้งหมดและทำการแก้ไขทั้งหมดในสำเนา

นอกจากนี้ เพื่อให้ข้อมูลที่อัปเดตพร้อมใช้งาน จำเป็นต้องเปลี่ยนลิงก์ไปยังโหนดที่เป็นปัจจุบันในโหนดพาเรนต์ที่เกี่ยวข้อง เนื่องจากจะต้องมีการแก้ไขสำหรับสิ่งนี้ด้วย จึงมีการคัดลอกไว้ล่วงหน้าด้วย กระบวนการนี้วนซ้ำไปเรื่อย ๆ จนถึงราก ข้อมูลในหน้าเมตาเป็นข้อมูลสุดท้ายที่จะเปลี่ยนแปลง​

หากจู่ๆ กระบวนการเกิดขัดข้องในระหว่างขั้นตอนการอัปเดต จะไม่มีการสร้างเมตาเพจใหม่ หรือจะไม่เขียนลงดิสก์จนกว่าจะสิ้นสุด และผลรวมการตรวจสอบจะไม่ถูกต้อง ในทั้งสองกรณีนี้ หน้าใหม่จะไม่สามารถเข้าถึงได้และหน้าเก่าจะไม่ได้รับผลกระทบ สิ่งนี้ทำให้ LMDB ไม่จำเป็นต้องเขียนบันทึกล่วงหน้าเพื่อรักษาความสอดคล้องของข้อมูล โดยพฤตินัยแล้ว โครงสร้างของการจัดเก็บข้อมูลบนดิสก์ที่อธิบายไว้ข้างต้น ทำหน้าที่ของมันไปพร้อม ๆ กัน การไม่มีบันทึกธุรกรรมที่ชัดเจนเป็นคุณลักษณะหนึ่งของ LMDB ซึ่งให้ความเร็วในการอ่านข้อมูลสูง​

โครงสร้างผลลัพธ์ที่เรียกว่าต่อท้าย B-tree เท่านั้น ให้การแยกธุรกรรมและมัลติเวอร์ชันโดยธรรมชาติ ใน LMDB ธุรกรรมที่เปิดอยู่แต่ละรายการมีรูทของต้นไม้ล่าสุดที่เชื่อมโยงอยู่ ตราบเท่าที่การทำธุรกรรมไม่เสร็จสมบูรณ์ หน้าของแผนผังที่เกี่ยวข้องจะไม่ถูกเปลี่ยนแปลงหรือใช้ซ้ำสำหรับข้อมูลเวอร์ชันใหม่ ดังนั้น คุณสามารถทำงานได้ตราบเท่าที่คุณต้องการด้วยชุดข้อมูลที่เกี่ยวข้องกันที่ เวลาที่ธุรกรรมเปิดขึ้น แม้ว่าพื้นที่เก็บข้อมูลจะยังคงได้รับการอัปเดตอย่างต่อเนื่องในขณะนี้ นี่คือสาระสำคัญของการมีหลายเวอร์ชัน ทำให้ LMDB เป็นแหล่งข้อมูลในอุดมคติสำหรับผู้ที่รักเรา UICollectionView. เมื่อเปิดธุรกรรมแล้ว คุณไม่จำเป็นต้องเพิ่มพื้นที่หน่วยความจำของแอปพลิเคชัน ดึงข้อมูลปัจจุบันออกอย่างเร่งรีบไปยังโครงสร้างในหน่วยความจำบางส่วน โดยไม่ต้องกลัวว่าจะไม่เหลืออะไรเลย คุณลักษณะนี้ทำให้ LMDB แตกต่างจาก SQLite เดียวกัน ซึ่งไม่สามารถโอ้อวดการแยกทั้งหมดได้ หลังจากเปิดธุรกรรมสองรายการในอันหลังและลบเรคคอร์ดบางอย่างภายในหนึ่งในนั้น จะไม่สามารถรับเรกคอร์ดเดียวกันได้อีกต่อไปในอันที่สองที่เหลือ

ข้อเสียของเหรียญคือการใช้หน่วยความจำเสมือนที่สูงขึ้นอย่างเห็นได้ชัด สไลด์นี้แสดงให้เห็นว่าโครงสร้างฐานข้อมูลจะมีลักษณะอย่างไรหากได้รับการแก้ไขพร้อมกันโดยเปิดธุรกรรมการอ่าน 3 รายการโดยดูที่เวอร์ชันต่างๆ ของฐานข้อมูล เนื่องจาก LMDB ไม่สามารถใช้โหนดซ้ำที่สามารถเข้าถึงได้จากรูทที่เกี่ยวข้องกับธุรกรรมจริง พื้นที่จัดเก็บจึงไม่มีทางเลือกนอกจากต้องจัดสรรรูทที่สี่ในหน่วยความจำและโคลนเพจที่แก้ไขภายใต้นั้นอีกครั้ง

ที่นี่จะไม่ฟุ่มเฟือยที่จะเรียกคืนส่วนในไฟล์ที่แมปหน่วยความจำ ดูเหมือนว่าการใช้หน่วยความจำเสมือนเพิ่มเติมไม่ควรรบกวนเรามากนักเนื่องจากไม่ได้ส่งผลต่อหน่วยความจำของแอปพลิเคชัน อย่างไรก็ตาม ในเวลาเดียวกัน มีข้อสังเกตว่า iOS นั้นตระหนี่มากในการจัดสรร และเราไม่สามารถจัดเตรียมพื้นที่ LMDB ขนาด 1 เทราไบต์บนเซิร์ฟเวอร์หรือเดสก์ท็อปจากไหล่ของต้นแบบได้ และไม่ได้คิดเกี่ยวกับคุณลักษณะนี้เลย เมื่อเป็นไปได้ คุณควรพยายามรักษาอายุการใช้งานของการทำธุรกรรมให้สั้นที่สุด

4. การออกแบบสคีมาข้อมูลที่ด้านบนของคีย์-ค่า API

เรามาเริ่มแยกวิเคราะห์ API โดยดูที่นามธรรมพื้นฐานที่จัดทำโดย LMDB: สภาพแวดล้อมและฐานข้อมูล คีย์และค่า ธุรกรรมและเคอร์เซอร์

หมายเหตุเกี่ยวกับรายการรหัส

ฟังก์ชันทั้งหมดใน API สาธารณะของ LMDB ส่งคืนผลลัพธ์ของการทำงานในรูปแบบของรหัสข้อผิดพลาด แต่ในรายการที่ตามมาทั้งหมด การตรวจสอบจะถูกละไว้เพื่อความกระชับ ในทางปฏิบัติ เราใช้รหัสของเราเองเพื่อโต้ตอบกับที่เก็บ ส้อม ห่อ C ++ lmdbxxซึ่งข้อผิดพลาดที่เกิดขึ้นเป็นข้อยกเว้น C++

ในฐานะที่เป็นวิธีที่เร็วที่สุดในการเชื่อมต่อ LMDB กับโปรเจ็กต์ iOS หรือ macOS ฉันขอนำเสนอ CocoaPod ของฉัน POSLMDB.

4.1. นามธรรมพื้นฐาน

สิ่งแวดล้อม

โครงสร้าง MDB_env เป็นที่เก็บสถานะภายในของ 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 ทำให้เอนทิตีทั้งหมด (เคอร์เซอร์ ธุรกรรม คีย์ และค่า) ที่ได้รับจากเอนจิ้นก่อนหน้านี้ใช้ไม่ได้ การบัญชีสำหรับเหตุการณ์ที่เปลี่ยนไปในรหัสจะนำไปสู่ความยุ่งยากที่สำคัญ หากอย่างไรก็ตาม หน่วยความจำเสมือนเป็นที่รักของคุณมาก นี่อาจเป็นเหตุผลที่ควรมองหาทางแยกที่ล้ำหน้าไปมาก เอ็มดีบีเอ็กซ์ซึ่งในบรรดาคุณสมบัติที่ประกาศนั้นมี "การปรับขนาดฐานข้อมูลแบบทันทีทันใดโดยอัตโนมัติ"

พารามิเตอร์ที่สองซึ่งเป็นค่าเริ่มต้นที่ไม่เหมาะกับเราควบคุมกลไกในการรับประกันความปลอดภัยของเธรด น่าเสียดายที่อย่างน้อยใน iOS 10 มีปัญหาเกี่ยวกับการสนับสนุนที่เก็บข้อมูลในเครื่องของเธรด ด้วยเหตุผลนี้ ในตัวอย่างด้านบน ที่เก็บถูกเปิดด้วยแฟล็ก MDB_NOTLS. นอกจากนี้ยังต้องใช้ ส้อม เสื้อคลุม C ++ lmdbxxเพื่อตัดตัวแปรที่มีและอยู่ในแอตทริบิวต์นี้

ฐานข้อมูล

ฐานข้อมูลเป็นอินสแตนซ์แยกต่างหากของ B-tree ที่เราพูดถึงข้างต้น การเปิดเกิดขึ้นภายในธุรกรรม ซึ่งในตอนแรกอาจดูแปลกเล็กน้อย

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. รองรับคุณสมบัติพื้นฐานทั้งหมด กรดคำสำคัญ: ความเป็นปรมาณู ความสม่ำเสมอ การแยกตัว และความน่าเชื่อถือ ฉันอดไม่ได้ที่จะสังเกตว่าในแง่ของความทนทานบน 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 Cloud เป็นการโหลดเนื้อหาอัตโนมัติจากแกลเลอรีสื่อระบบ ด้วยการเชื่อมต่อที่ดี ไคลเอนต์สามารถเพิ่มภาพถ่ายหลายภาพต่อวินาทีไปยังเซิร์ฟเวอร์ หากคุณอัปเดตหลังจากการดาวน์โหลดแต่ละครั้ง UICollectionView ด้วยเนื้อหาสื่อในระบบคลาวด์ของผู้ใช้ คุณจะลืมเกี่ยวกับ 60 fps และการเลื่อนได้อย่างราบรื่นในระหว่างกระบวนการนี้ เพื่อป้องกันการอัปเดตหน้าจอบ่อยครั้ง คุณต้องจำกัดอัตราการเปลี่ยนแปลงข้อมูลเป็นพื้นฐาน UICollectionViewDataSource.

หากฐานข้อมูลไม่รองรับการมีหลายเวอร์ชันและอนุญาตให้คุณทำงานกับสถานะปัจจุบันเท่านั้น หากต้องการสร้างสแนปชอตข้อมูลที่คงตามเวลา คุณต้องคัดลอกไปยังโครงสร้างข้อมูลในหน่วยความจำบางส่วนหรือตารางชั่วคราว วิธีใดวิธีหนึ่งเหล่านี้มีราคาแพงมาก ในกรณีของการจัดเก็บในหน่วยความจำ เราได้รับทั้งต้นทุนหน่วยความจำที่เกิดจากการเก็บวัตถุที่สร้างขึ้นและต้นทุนเวลาที่เกี่ยวข้องกับการแปลง ORM ที่ซ้ำซ้อน สำหรับตารางชั่วคราวนี่เป็นความสุขที่มีราคาแพงกว่าซึ่งสมเหตุสมผลในกรณีที่ไม่สำคัญเท่านั้น

LMDB หลายเวอร์ชันช่วยแก้ปัญหาของการรักษาแหล่งข้อมูลที่เสถียรด้วยวิธีที่สวยงามมาก แค่เปิดธุรกรรมก็เพียงพอแล้ว - จนกว่าเราจะดำเนินการเสร็จสิ้น ชุดข้อมูลจะได้รับการแก้ไข ตรรกะของอัตราการอัปเดตตอนนี้อยู่ในมือของเลเยอร์การนำเสนอทั้งหมด โดยไม่มีค่าใช้จ่ายทรัพยากรที่สำคัญ

เคอร์เซอร์

เคอร์เซอร์จัดเตรียมกลไกสำหรับการวนซ้ำอย่างเป็นระเบียบบนคู่คีย์-ค่าโดยผ่าน B-tree หากไม่มีสิ่งเหล่านี้ คงเป็นไปไม่ได้ที่จะสร้างแบบจำลองตารางในฐานข้อมูลอย่างมีประสิทธิภาพ ซึ่งตอนนี้เราหันไปใช้

4.2. การสร้างแบบจำลองตาราง

คุณสมบัติการจัดลำดับคีย์ช่วยให้คุณสร้างสิ่งที่เป็นนามธรรมระดับบนสุด เช่น ตารางที่อยู่ด้านบนของสิ่งที่เป็นนามธรรมพื้นฐาน ลองพิจารณากระบวนการนี้ในตัวอย่างตารางหลักของไคลเอนต์คลาวด์ซึ่งแคชข้อมูลเกี่ยวกับไฟล์และโฟลเดอร์ทั้งหมดของผู้ใช้

สคีมาตาราง

หนึ่งในสถานการณ์ทั่วไปที่ควรปรับปรุงโครงสร้างของตารางที่มีโครงสร้างโฟลเดอร์คือการเลือกองค์ประกอบทั้งหมดที่อยู่ในไดเร็กทอรีที่กำหนด รูปแบบองค์กร ข้อมูลที่ดีสำหรับการสืบค้นข้อมูลประเภทนี้ที่มีประสิทธิภาพคือ รายการ Adjacency. หากต้องการนำไปใช้ที่ด้านบนของที่จัดเก็บคีย์-ค่า จำเป็นต้องจัดเรียงคีย์ของไฟล์และโฟลเดอร์ในลักษณะที่จัดกลุ่มตามที่อยู่ในไดเร็กทอรีหลัก นอกจากนี้ เพื่อแสดงเนื้อหาของไดเร็กทอรีในรูปแบบที่ผู้ใช้ 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 ทั้งหมด ตัวแปรจำนวนเต็มจะถูกจัดเก็บในรูปแบบ Endian น้อย. ซึ่งหมายความว่าไบต์ที่มีนัยสำคัญน้อยที่สุดจะอยู่ทางด้านซ้าย และคุณจะไม่สามารถจัดเรียงจำนวนเต็มโดยใช้การเปรียบเทียบแบบไบต์ต่อไบต์ได้ ตัวอย่างเช่น การพยายามทำเช่นนี้กับชุดตัวเลขตั้งแต่ 0 ถึง 511 จะได้ผลลัพธ์ดังต่อไปนี้

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

ในการแก้ปัญหานี้ จำนวนเต็มจะต้องถูกเก็บไว้ในคีย์ในรูปแบบที่เหมาะสมสำหรับตัวเปรียบเทียบไบต์ ฟังก์ชั่นจากครอบครัวจะช่วยในการเปลี่ยนแปลงที่จำเป็น hton* (โดยเฉพาะอย่างยิ่ง htons สำหรับตัวเลขแบบไบต์คู่จากตัวอย่าง)

รูปแบบสำหรับการแสดงสตริงในการเขียนโปรแกรมนั้นเป็นไปตามที่คุณทราบ история. หากความหมายของสตริงรวมถึงการเข้ารหัสที่ใช้แทนค่าเหล่านี้ในหน่วยความจำแสดงว่าอาจมีมากกว่าหนึ่งไบต์ต่ออักขระ ดังนั้นควรละทิ้งแนวคิดในการใช้ตัวเปรียบเทียบเริ่มต้นทันที

สิ่งที่สองที่ควรทราบคือ หลักการจัดตำแหน่ง struct ฟิลด์คอมไพเลอร์ ด้วยเหตุนี้จึงสามารถสร้างไบต์ที่มีค่าขยะในหน่วยความจำระหว่างฟิลด์ซึ่งแน่นอนว่าจะแบ่งการเรียงลำดับไบต์ ในการกำจัดขยะ คุณต้องประกาศฟิลด์ตามลำดับที่กำหนดไว้อย่างเคร่งครัด โดยคำนึงถึงกฎการจัดตำแหน่ง หรือใช้แอตทริบิวต์ในการประกาศโครงสร้าง 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-tree ซึ่งมีวัตถุอยู่ ซึ่งต้องขอบคุณหลักการคัดลอกเมื่อเขียน จะไม่เปลี่ยนแปลง ตราบใดที่ธุรกรรมอย่างน้อยหนึ่งรายการอ้างอิงถึงสิ่งเหล่านั้น ในเวลาเดียวกัน ทันทีที่ธุรกรรมล่าสุดที่เกี่ยวข้องเสร็จสิ้น เพจจะสามารถนำมาใช้ซ้ำสำหรับข้อมูลใหม่ได้ หากจำเป็นสำหรับออบเจ็กต์เพื่อความอยู่รอดของธุรกรรมที่สร้างอ็อบเจ็กต์นั้น ก็ยังต้องคัดลอกออบเจ็กต์
2. สำหรับธุรกรรม readwrite ตัวชี้ไปยังค่าโครงสร้างที่เป็นผลลัพธ์จะใช้ได้จนถึงขั้นตอนการแก้ไขครั้งแรกเท่านั้น (การเขียนหรือการลบข้อมูล)
3. แม้ว่าโครงสร้าง NodeValue ไม่เต็มเปี่ยม แต่ถูกตัดแต่ง (ดูส่วนย่อย "การสั่งซื้อคีย์โดยตัวเปรียบเทียบภายนอก") คุณสามารถเข้าถึงฟิลด์ได้อย่างง่ายดายผ่านตัวชี้ สิ่งสำคัญคืออย่าละเลย!
4. ไม่ว่าในกรณีใดคุณสามารถแก้ไขโครงสร้างผ่านตัวชี้ที่ได้รับ การเปลี่ยนแปลงทั้งหมดต้องทำผ่านเมธอดเท่านั้น mdb_put. อย่างไรก็ตามด้วยความปรารถนาที่จะทำเช่นนี้จะไม่ทำงานเนื่องจากพื้นที่หน่วยความจำที่โครงสร้างนี้ตั้งอยู่นั้นถูกแมปในโหมดอ่านอย่างเดียว
5. ทำการแมปไฟล์ใหม่ไปยังพื้นที่ที่อยู่ของกระบวนการ ตัวอย่างเช่น เพิ่มขนาดพื้นที่จัดเก็บสูงสุดโดยใช้ฟังก์ชัน mdb_env_set_map_size ทำให้ธุรกรรมและเอนทิตีที่เกี่ยวข้องทั้งหมดเป็นโมฆะโดยสิ้นเชิง และชี้ให้อ่านวัตถุโดยเฉพาะ

ประการสุดท้าย อีกหนึ่งคุณสมบัติที่ร้ายกาจมากจนการเปิดเผยสาระสำคัญไม่เข้ากับอีกประเด็นหนึ่ง ในบท B-tree ฉันได้ให้ไดอะแกรมของการจัดระเบียบหน้าในหน่วยความจำ จากนั้นที่อยู่ของจุดเริ่มต้นของบัฟเฟอร์ที่มีข้อมูลต่อเนื่องสามารถเป็นไปโดยพลการ ด้วยเหตุนี้ตัวชี้ถึงพวกเขาจึงได้รับในโครงสร้าง MDB_val และส่งไปยังตัวชี้ไปยังโครงสร้างโดยทั่วไปจะไม่จัดแนว ในขณะเดียวกัน สถาปัตยกรรมของชิปบางตัว (ในกรณีของ iOS นี่คือ armv7) กำหนดให้ที่อยู่ของข้อมูลใด ๆ มีขนาดทวีคูณของขนาดของคำเครื่อง หรืออีกนัยหนึ่งคือ bitness ของระบบ (สำหรับ 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 เอฟเฟกต์เดียวกันสามารถเป็นได้ บรรลุ และใช้แอตทริบิวต์ที่บรรจุ เมื่อพิจารณาว่ามันมีส่วนช่วยในการเพิ่มประสิทธิภาพของพื้นที่ที่ถูกครอบครองโดยโครงสร้าง วิธีนี้ดูเหมือนจะดีกว่าสำหรับฉัน แม้ว่า приводит เพื่อเพิ่มค่าใช้จ่ายในการดำเนินการเข้าถึงข้อมูล

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

แบบสอบถามช่วง

หากต้องการวนซ้ำกับกลุ่มของเรคคอร์ด LMDB ให้เคอร์เซอร์เป็นนามธรรม มาดูวิธีใช้งานโดยใช้ตัวอย่างตารางที่มีข้อมูลเมตาบนคลาวด์ของผู้ใช้ที่เราคุ้นเคยอยู่แล้ว

ในการแสดงรายการไฟล์ในไดเร็กทอรี คุณต้องค้นหาคีย์ทั้งหมดที่เกี่ยวข้องกับไฟล์และโฟลเดอร์ลูก ในส่วนย่อยก่อนหน้านี้ เราจัดเรียงคีย์ NodeKey เพื่อให้เรียงลำดับตาม ID ไดเร็กทอรีหลักก่อน ดังนั้น ในทางเทคนิคแล้ว งานในการรับเนื้อหาของโฟลเดอร์จะลดลงเหลือเพียงการวางเคอร์เซอร์บนขอบเขตบนของกลุ่มคีย์ที่มีคำนำหน้าตามที่กำหนด ตามด้วยการวนซ้ำไปยังขอบเขตล่าง

คุณสามารถค้นหาขอบเขตบน "ที่หน้าผาก" ได้โดยการค้นหาตามลำดับ ในการดำเนินการนี้ เคอร์เซอร์จะอยู่ที่จุดเริ่มต้นของรายการคีย์ทั้งหมดในฐานข้อมูล จากนั้นจึงเพิ่มขึ้นจนกระทั่งคีย์ที่มีตัวระบุไดเร็กทอรีหลักปรากฏอยู่ด้านล่าง วิธีนี้มีข้อเสียที่ชัดเจน 2 ประการ:

1. ความซับซ้อนเชิงเส้นของการค้นหา แม้ว่าอย่างที่คุณทราบ ในต้นไม้โดยทั่วไปและโดยเฉพาะใน B-tree สามารถทำได้ในเวลาลอการิทึม​
2. โดยเปล่าประโยชน์ ทุกหน้าก่อนหน้าหน้าที่ต้องการจะถูกยกขึ้นจากไฟล์ไปยังหน่วยความจำหลักซึ่งมีราคาแพงมาก

โชคดีที่ LMDB API มีวิธีที่มีประสิทธิภาพในการวางตำแหน่งเคอร์เซอร์ในตอนแรก ในการทำเช่นนี้ คุณต้องสร้างคีย์ดังกล่าว ซึ่งค่าของคีย์ดังกล่าวจะน้อยกว่าหรือเท่ากับคีย์ที่อยู่ในขอบเขตบนของช่วงเวลาอย่างแน่นอน . ตัวอย่างเช่น ในส่วนที่เกี่ยวข้องกับรายการในรูปด้านบน เราสามารถสร้างคีย์ที่ฟิลด์ได้ parentId จะเท่ากับ 2 และส่วนที่เหลือทั้งหมดจะเต็มไปด้วยศูนย์ คีย์ที่เติมบางส่วนดังกล่าวจะถูกส่งไปยังอินพุตของฟังก์ชัน 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 รายการไปยังฐานข้อมูลแทนที่จะเป็น XNUMX รายการ แผนผัง สคีมาฐานข้อมูลที่ได้จะเป็นดังนี้

อีกรูปแบบหนึ่งสำหรับการจัดความสัมพันธ์ระหว่างตารางคือ "กุญแจสำรอง". สาระสำคัญของมันคือการเพิ่มแอตทริบิวต์เพิ่มเติมให้กับคีย์ซึ่งไม่จำเป็นสำหรับการเรียงลำดับแต่สำหรับการสร้างคีย์ที่เกี่ยวข้องขึ้นใหม่ อย่างไรก็ตาม มีตัวอย่างจริงของการใช้งานในแอปพลิเคชัน Mail.ru Cloud เพื่อหลีกเลี่ยงการเจาะลึกลงไปใน บริบทของเฟรมเวิร์ก iOS เฉพาะ ฉันจะให้ตัวอย่างที่สมมติขึ้น แต่เป็นตัวอย่างที่เข้าใจได้มากขึ้น

ไคลเอนต์มือถือระบบคลาวด์มีหน้าที่แสดงไฟล์และโฟลเดอร์ทั้งหมดที่ผู้ใช้แบ่งปันกับบุคคลอื่น เนื่องจากมีไฟล์ดังกล่าวค่อนข้างน้อย และมีข้อมูลเฉพาะจำนวนมากเกี่ยวกับการเผยแพร่ที่เกี่ยวข้องกับไฟล์เหล่านั้น (ผู้ที่ได้รับสิทธิ์ในการเข้าถึง สิทธิ์ใดบ้าง ฯลฯ) จึงไม่มีเหตุผลที่จะรับภาระในส่วนมูลค่าของไฟล์ รายการในตารางหลัก อย่างไรก็ตาม หากคุณต้องการแสดงไฟล์ดังกล่าวแบบออฟไลน์ คุณยังคงต้องจัดเก็บไฟล์นั้นไว้ที่ใดที่หนึ่ง ทางออกตามธรรมชาติคือการสร้างตารางแยกต่างหากสำหรับมัน ในแผนภาพด้านล่าง คีย์จะนำหน้าด้วย "P" และตัวยึดตำแหน่ง "propname" สามารถแทนที่ด้วยค่า "ข้อมูลสาธารณะ" ที่เฉพาะเจาะจงมากขึ้น​

ข้อมูลเมตาที่ไม่ซ้ำกันทั้งหมด เพื่อจุดประสงค์ในการสร้างตารางใหม่ จะถูกย้ายไปยังส่วนค่าของเรกคอร์ด ในเวลาเดียวกัน ฉันไม่ต้องการทำซ้ำข้อมูลเกี่ยวกับไฟล์และโฟลเดอร์ที่เก็บอยู่ในตารางหลัก แต่จะเพิ่มข้อมูลที่ซ้ำซ้อนให้กับคีย์ "P" ในรูปแบบของฟิลด์ "node ID" และ "timestamp" ต้องขอบคุณพวกเขา คุณสามารถสร้างคีย์ดัชนี ซึ่งคุณจะได้รับคีย์หลัก ซึ่งในที่สุด คุณจะได้รับข้อมูลเมตาของโหนด

บทสรุป

เราประเมินผลลัพธ์ของการนำ LMDB ไปใช้งานในเชิงบวก หลังจากนั้น จำนวนแอปพลิเคชันค้างลดลง 30%

ผลงานที่ทำได้พบการตอบรับนอกทีม iOS ปัจจุบัน หนึ่งในส่วน "ไฟล์" หลักในแอปพลิเคชัน Android ได้เปลี่ยนไปใช้ LMDB แล้ว และส่วนอื่นๆ กำลังอยู่ระหว่างดำเนินการ ภาษา C ซึ่งใช้การจัดเก็บคีย์-ค่าเป็นความช่วยเหลือที่ดีในการเริ่มต้นแอปพลิเคชันที่เชื่อมโยงกับข้ามแพลตฟอร์มในภาษา C ++ สำหรับการเชื่อมต่อที่ราบรื่นของไลบรารี C ++ ที่เป็นผลลัพธ์กับโค้ดแพลตฟอร์มใน Objective-C และ Kotlin จะใช้ตัวสร้างโค้ด จินนี จาก Dropbox แต่นั่นเป็นอีกเรื่องหนึ่ง

ที่มา: will.com