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

Grace Murray Hopper, Management and the Computer of the Future (1962)

โดยทั่วไปแล้วฐานข้อมูลแบบกระจาย (distributed database) จะกระจายข้อมูลข้ามโหนดในสองรูปแบบ:

• เก็บสำเนาของข้อมูลชุดเดียวกันไว้บนหลายโหนด นี่คือ replication ซึ่งเราได้พูดถึงไปแล้วใน บทที่ 6 .

• ถ้ามีข้อมูลมากเกินไปหรือมี write throughput สูงเกินกว่าที่โหนดเดียวจะรับไหว ระบบจะแบ่งข้อมูลออกเป็น shard หรือ partition ที่เล็กลง และเก็บ shard ที่ต่างกันไว้บนโหนดที่ต่างกัน เราจะพูดถึง sharding ในบทนี้

โดยปกติแล้ว shard จะถูกกำหนดในลักษณะที่ข้อมูลแต่ละชิ้น (แต่ละ record, row, หรือ document) จะอยู่ใน shard เดียวเท่านั้น มีหลายวิธีในการทำสิ่งนี้ ซึ่งเราจะพูดถึงอย่างละเอียดในบทนี้ โดยสรุปแล้ว แต่ละ shard ก็คือฐานข้อมูลขนาดเล็กในตัวของมันเอง แม้ว่าระบบฐานข้อมูลบางระบบจะรองรับการดำเนินการที่เกี่ยวข้องกับหลาย shard พร้อมกันก็ตาม

โดยทั่วไปแล้ว Sharding มักใช้ร่วมกับ replication เพื่อให้สำเนาของแต่ละ shard ถูกเก็บไว้บนหลายโหนด ซึ่งหมายความว่าแม้แต่ละ record จะอยู่ใน shard เดียวเท่านั้น แต่มันอาจถูกเก็บไว้บนหลายโหนดที่แตกต่างกันเพื่อความทนทานต่อข้อผิดพลาด (fault tolerance)

โหนดหนึ่งอาจเก็บมากกว่าหนึ่ง shard ถ้าใช้โมเดล single-leader replication การรวมกันของ sharding และ replication อาจมีลักษณะดัง รูปที่ 7-1 ตัวอย่างเช่น leader ของแต่ละ shard จะถูกกำหนดให้กับโหนดหนึ่ง และ follower จะถูกกำหนดให้กับโหนดอื่นๆ แต่ละโหนดอาจเป็น leader สำหรับ shard บางตัวและเป็น follower สำหรับ shard อื่นๆ แต่แต่ละ shard จะมี leader เพียงตัวเดียว

Figure 7-1. การรวม replication และ sharding เข้าด้วยกัน: แต่ละโหนดทำหน้าที่เป็น leader สำหรับบาง shard และเป็น follower สำหรับ shard อื่นๆ

Sharding and Partitioning (Sharding และ Partitioning)

สิ่งที่เราเรียกว่า shard ในบทนี้มีชื่อเรียกหลายชื่อขึ้นอยู่กับซอฟต์แวร์ที่คุณใช้ มันถูก เรียกว่า partition ใน Kafka, range ใน CockroachDB, region ใน HBase และ TiDB, vBucket ใน Couchbase, vnode ใน Riak, token-range ใน Cassandra, และ tablet ใน Bigtable, YugabyteDB, และ ScyllaDB เป็นต้น

ฐานข้อมูลบางแห่งถือว่า partition และ shard เป็นสองแนวคิดที่แตกต่างกัน ตัวอย่างเช่น ใน PostgreSQL partitioning เป็นวิธีการแบ่งตารางขนาดใหญ่ออกเป็นหลายไฟล์ที่เก็บไว้บนเครื่องเดียวกัน (ซึ่งมีข้อดีหลายอย่าง เช่น ทำให้การลบทั้ง partition ทำได้เร็วมาก) ในขณะที่ sharding จะแบ่งชุดข้อมูลข้ามหลายเครื่อง [ 1 , 2 ]. ในระบบอื่นๆ หลายระบบ partitioning ก็คืออีกคำหนึ่งของ sharding

แม้ว่า partitioning จะเป็นคำที่สื่อความหมายได้ดี แต่คำว่า sharding อาจฟังดูน่าแปลกใจ ตามทฤษฎีหนึ่ง คำนี้เกิดขึ้นจากเกมออนไลน์แบบสวมบทบาท Ultima Online ซึ่งคริสตัลวิเศษถูกแตกเป็นเสี่ยงๆ และแต่ละเสี่ยง (shard) ก็สะท้อนโลกของเกมออกมา [ 3 ]. คำว่า shard จึงหมายถึงเซิร์ฟเวอร์เกมคู่ขนานหนึ่งในชุด และต่อมาถูกนำมาใช้ในฐานข้อมูล อีกทฤษฎีหนึ่งบอกว่ามันเป็นตัวย่อของ System for Highly Available Replicated Data ซึ่งเป็นฐานข้อมูลในยุค 1980 ที่รายละเอียดสูญหายไปตามกาลเวลา

อนึ่ง partitioning ไม่เกี่ยวข้อง กับ network partitions (netsplits) ซึ่งเป็นข้อผิดพลาดประเภทหนึ่งในเครือข่ายระหว่างโหนด เราจะพูดถึงข้อผิดพลาดเหล่านี้ใน บทที่ 9 .

ทุกอย่างเกี่ยวกับ replication ของฐานข้อมูลใน บทที่ 6 นำไปใช้กับ replication ของ shard ได้เช่นเดียวกัน เนื่องจากการเลือกรูปแบบ sharding ส่วนใหญ่ไม่ขึ้นอยู่กับการเลือกรูปแบบ replication ดังนั้นเพื่อความง่าย เราจะไม่พูดถึง replication ในบทนี้

Pros and Cons of Sharding (ข้อดีและข้อเสียของ Sharding)

เหตุผลหลักในการทำ sharding ให้ฐานข้อมูลคือ scalability (ความสามารถในการขยายขนาด) Sharding เป็นทางออกเมื่อปริมาณข้อมูลหรือ write throughput สูงเกินกว่าที่โหนดเดียวจะรับไหว เพราะมันช่วยให้คุณกระจายข้อมูลและ write เหล่านั้นไปยังหลายโหนด (ถ้าปัญหาคือ read throughput คุณอาจไม่จำเป็นต้องใช้ sharding—คุณสามารถใช้ read scaling ตามที่กล่าวถึงใน บทที่ 6 .)

ที่จริงแล้ว sharding เป็นหนึ่งในเครื่องมือหลักที่เรามีสำหรับการทำ horizontal scaling (สถาปัตยกรรมแบบ scale-out ) ตามที่กล่าวถึงใน "Shared-Memory, Shared-Disk, and Shared-Nothing Architectures" —นั่นคือ การให้ระบบเพิ่มขีดความสามารถไม่ใช่โดยการย้ายไปยังเครื่องที่ใหญ่ขึ้น แต่โดยการเพิ่มเครื่อง (ที่เล็กกว่า) เข้าไปอีก ถ้าคุณสามารถแบ่ง workload ให้แต่ละ shard รับภาระที่เท่าๆ กัน คุณก็สามารถกำหนด shard เหล่านั้นให้กับเครื่องต่างๆ เพื่อประมวลผลข้อมูลและ query แบบขนานได้

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

เหตุผลของคำแนะนำนี้คือ sharding เพิ่มความซับซ้อน คุณมักจะต้องตัดสินใจว่า record ไหนควรอยู่ใน shard ไหนโดยการเลือก partition key ; record ทั้งหมดที่มี partition key เดียวกันจะถูกวางใน shard เดียวกัน [ 4 ]. การเลือกนี้มีความสำคัญเพราะการเข้าถึง record จะเร็วถ้าคุณรู้ว่ามันอยู่ใน shard ไหน แต่ถ้าไม่รู้ คุณจะต้องค้นหาอย่างไม่มีประสิทธิภาพข้ามทุก shard นอกจากนี้รูปแบบ sharding ก็เปลี่ยนแปลงได้ยาก

Sharding มักทำงานได้ดีกับข้อมูลแบบ key-value ซึ่งคุณสามารถ shard ตาม key ได้ง่าย แต่จะยากกว่ากับข้อมูลเชิงสัมพันธ์ (relational data) ที่คุณอาจต้องการค้นหาด้วย secondary index หรือ join record ที่อาจกระจายอยู่ข้าม shard ต่างๆ เราจะพูดถึงเรื่องนี้เพิ่มเติมใน "Sharding and Secondary Indexes" .

ปัญหาอีกอย่างของ sharding คือ write อาจต้องอัปเดต record ที่เกี่ยวข้องกันในหลาย shard ในขณะที่ transaction บนโหนดเดียวเป็นเรื่องปกติ การรับประกันความสอดคล้อง (consistency) ข้ามหลาย shard จำเป็นต้องมี distributed transaction ดังที่เราจะเห็นใน บทที่ 8 distributed transaction มีให้ใช้ในฐานข้อมูลบางระบบ แต่มักจะช้ากว่า transaction บนโหนดเดียวมาก และอาจกลายเป็น bottleneck สำหรับทั้งระบบ

บางระบบใช้ sharding แม้แต่บนเครื่องเดียว โดยปกติจะรันหนึ่ง process ต่อหนึ่ง CPU core เพื่อใช้ประโยชน์จาก parallelism ใน CPU หรือใช้ประโยชน์จากสถาปัตยกรรม nonuniform memory access (NUMA) ซึ่งหน่วยความจำบาง bank จะอยู่ใกล้ CPU บางตัวมากกว่าตัวอื่น [ 5 ]. ตัวอย่างเช่น Redis, VoltDB, และ FoundationDB ใช้หนึ่ง process ต่อหนึ่ง core และพึ่งพา sharding เพื่อกระจายโหลดข้าม CPU core ในเครื่องเดียวกัน [ 6 ].

Sharding for Multitenancy (Sharding สำหรับระบบหลายผู้เช่า)

สินค้าประเภท Software as a Service (SaaS) และ cloud services มักเป็นแบบ multitenant โดยที่แต่ละ tenant คือลูกค้าหนึ่งราย ผู้ใช้หลายคนอาจมี login ใน tenant เดียวกัน แต่แต่ละ tenant จะมีชุดข้อมูลที่แยกจาก tenant อื่นๆ ตัวอย่างเช่น ในบริการการตลาดทางอีเมล แต่ละธุรกิจที่สมัครใช้บริการมักจะเป็น tenant แยกกัน เนื่องจากการสมัครรับจดหมายข่าว ข้อมูลการจัดส่ง ฯลฯ ของธุรกิจหนึ่งจะแยกจากธุรกิจอื่น

ในบางครั้ง sharding ถูกใช้เพื่อสร้างระบบ multitenant โดยแต่ละ tenant จะได้รับ shard แยก หรือ tenant ขนาดเล็กหลายตัวอาจถูกรวมกันเป็น shard ที่ใหญ่ขึ้น shard เหล่านี้อาจเป็นฐานข้อมูลที่แยกจากกันทางกายภาพ (ซึ่งเราได้กล่าวถึงก่อนหน้านี้ใน "Embedded Storage Engines" ) หรือเป็นส่วนที่จัดการแยกกันได้ของฐานข้อมูลเชิงตรรกะที่ใหญ่กว่า [ 7 ]. การใช้ sharding สำหรับ multitenancy มีข้อดีหลายประการ:

Resource isolation (การแยกทรัพยากร)

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

Permission isolation (การแยกสิทธิ์)

ถ้ามีบั๊กในตรรกะการควบคุมการเข้าถึงของคุณ ก็มีโอกาสน้อยที่คุณจะให้ tenant หนึ่งเข้าถึงข้อมูลของ tenant อื่นโดยไม่ได้ตั้งใจ ถ้าชุดข้อมูลของ tenant เหล่านั้นถูกจัดเก็บแยกจากกันทางกายภาพ

Cell-based architecture (สถาปัตยกรรมแบบเซลล์)

คุณสามารถใช้ sharding ไม่เพียงแต่ในระดับการจัดเก็บข้อมูล แต่ยังรวมถึง service ที่รันโค้ดแอปพลิเคชันของคุณด้วย ใน cell-based architecture service และระบบจัดเก็บข้อมูลสำหรับ tenant กลุ่มหนึ่งจะถูกรวมเป็น cell ที่เป็นอิสระ และ cell ที่แตกต่างกันจะถูกตั้งค่าให้ทำงานแยกจากกันได้เป็นส่วนใหญ่ วิธีการนี้ให้ fault isolation (การแยกข้อผิดพลาด): ข้อผิดพลาดใน cell หนึ่งจะจำกัดอยู่แค่ใน cell นั้น และ tenant ใน cell อื่นจะไม่ได้รับผลกระทบ [ 8 ].

Per-tenant backup and restore (การสำรองและกู้คืนข้อมูลเฉพาะ tenant)

การสำรองข้อมูล shard ของแต่ละ tenant แยกกันทำให้สามารถกู้คืนสถานะของ tenant จาก backup โดยไม่กระทบต่อ tenant อื่น ซึ่งมีประโยชน์ถ้า tenant ลบหรือเขียนทับข้อมูลสำคัญโดยไม่ตั้งใจ [ 9 ].

Regulatory compliance (การปฏิบัติตามกฎระเบียบ)

กฎระเบียบด้านความเป็นส่วนตัวของข้อมูล เช่น GDPR และ CCPA ให้สิทธิ์แก่บุคคลในการเข้าถึงและขอให้ลบข้อมูลส่วนบุคคลที่ธุรกิจจัดเก็บเกี่ยวกับพวกเขา ถ้าข้อมูลของแต่ละบุคคลถูกเก็บไว้ใน shard แยกกัน นี่จะกลายเป็นการดำเนินการส่งออกและลบข้อมูลที่ง่ายบน shard ของพวกเขา [ 10 ].

Data residence (การจัดเก็บข้อมูลตามภูมิภาค)

ถ้าข้อมูลของ tenant เฉพาะรายจำเป็นต้องถูกจัดเก็บในเขตอำนาจศาลที่กำหนดเพื่อให้เป็นไปตามกฎหมาย data residency ฐานข้อมูลที่รองรับ region จะช่วยให้คุณสามารถกำหนด shard ของ tenant นั้นไปยัง region ที่กำหนดได้

Gradual schema rollout (การปรับใช้ Schema แบบค่อยเป็นค่อยไป)

Schema migration (ที่กล่าวถึงก่อนหน้านี้ใน "Schema flexibility in the document model" ) สามารถทยอยปรับใช้ทีละ tenant ได้ ซึ่งช่วยลดความเสี่ยง เพราะคุณสามารถตรวจจับปัญหาได้ก่อนที่จะกระทบ tenant ทั้งหมด แต่อาจทำได้ยากในลักษณะ transactional [ 11 ].

ความท้าทายหลักของการใช้ sharding สำหรับ multitenancy มีดังนี้:

• วิธีการนี้สมมติว่า tenant แต่ละรายมีขนาดเล็กพอที่จะอยู่ในโหนดเดียว ถ้าไม่เป็นเช่นนั้น และคุณมี tenant หนึ่งที่ใหญ่เกินไปสำหรับเครื่องเดียว คุณจะต้องทำ sharding เพิ่มเติมภายใน tenant นั้น ซึ่งนำเรากลับมาที่หัวข้อ sharding เพื่อ scalability [ 12 ].

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

• ถ้าคุณจำเป็นต้องรองรับฟีเจอร์ที่เชื่อมต่อข้อมูลข้ามหลาย tenant สิ่งเหล่านี้จะทำได้ยากขึ้นถ้าคุณต้อง join ข้อมูลข้ามหลาย shard

Sharding of Key-Value Data (การแบ่งส่วนข้อมูลแบบ Key-Value)

สมมติว่าคุณมีข้อมูลจำนวนมาก และคุณต้องการ shard ข้อมูลนั้น คุณจะตัดสินใจได้อย่างไรว่า record ไหนควรเก็บไว้บนโหนดใด?

เป้าหมายของ sharding คือการกระจายข้อมูลและปริมาณ query ให้ evenly ทั่วทุกโหนด ถ้าแต่ละโหนดรับส่วนแบ่งที่เท่าเทียมกัน—ในทางทฤษฎี—10 โหนดควรจะสามารถรับมือกับข้อมูลและ throughput การอ่านเขียนได้มากกว่าโหนดเดียวถึง 10 เท่า (ไม่นับ replication) เมื่อคุณเพิ่มหรือลบโหนด คุณก็ต้องการที่จะ rebalance โหลดเพื่อให้กระจายอย่างเท่าเทียมกันตามจำนวนโหนดใหม่

ถ้า การ sharding ไม่ยุติธรรม ทำให้บาง shard มีข้อมูลหรือ query มากกว่าตัวอื่น เราเรียกสิ่งนี้ว่า skewed . การมี skew ทำให้ sharding มีประสิทธิภาพน้อยลงมาก ในกรณีที่รุนแรง โหลดทั้งหมดอาจไปรวมที่ shard เดียว ทำให้ 9 ใน 10 โหนดว่างงาน และ bottleneck ของคุณคือโหนดเดียวที่ทำงานหนัก shard ที่มีโหลดสูงอย่างไม่สมส่วนเรียกว่า hot shard หรือ hot spot . ถ้าหนึ่ง key มีโหลดสูงเป็นพิเศษ (เช่น คนดังใน social network) เราเรียกว่า hot key .

ในการแบ่งชุดข้อมูลออกเป็น shard เราจำเป็นต้องมี algorithm ที่รับ partition key ของ record เป็น input และบอกว่า record นั้นอยู่ใน shard ไหน ใน key-value store partition key มักจะเป็น key หรือส่วนแรกของ key ในโมเดล relational partition key อาจเป็น column ใด column หนึ่งของตาราง (ไม่จำเป็นต้องเป็น primary key ของมัน) algorithm นั้นต้องสามารถปรับ rebalancing ได้เพื่อลด hot spots

Sharding by Key Range (การแบ่งส่วนตามช่วงของ Key)

วิธีหนึ่งในการ sharding คือการกำหนดช่วงของ partition key ที่ต่อเนื่องกัน (จากค่าต่ำสุดถึงค่าสูงสุด) ให้กับแต่ละ shard เช่นเดียวกับเล่มของสารานุกรมกระดาษ ดังแสดงใน รูปที่ 7-2 . ในตัวอย่างนี้ partition key ของรายการคือชื่อเรื่อง (title) ถ้าคุณต้องการค้นหารายการสำหรับชื่อเรื่องใดชื่อเรื่องหนึ่ง คุณสามารถระบุได้อย่างง่ายดายว่า shard ไหนมีรายการนั้น และหยิบเล่มที่ถูกต้องจากชั้นวาง โดยหาเล่มที่ช่วง key ครอบคลุมชื่อเรื่องที่คุณกำลังค้นหา

Figure 7-2. สารานุกรมฉบับพิมพ์ถูก sharding ตามช่วงของ key

ช่วงของ key ไม่จำเป็นต้องมีระยะห่างเท่ากัน เพราะข้อมูลของคุณอาจกระจายตัวไม่เท่ากัน ตัวอย่างเช่น ใน รูปที่ 7-2 เล่มที่ 1 มีคำที่ขึ้นต้นด้วย A และ B แต่เล่มที่ 12 มีคำที่ขึ้นต้นด้วย T , U , V , W , X , Y , และ Z . การมีหนึ่งเล่มต่อสองตัวอักษรของตัวอักษรจะทำให้บางเล่มมีขนาดใหญ่กว่าอีกเล่มมาก ในการกระจายข้อมูลอย่างเท่าเทียมกัน ขอบเขตของ shard ต้องปรับตามข้อมูล

ขอบเขตของ shard อาจถูกเลือกด้วยตนเองโดยผู้ดูแลระบบ หรือฐานข้อมูลสามารถเลือกได้โดยอัตโนมัติ การ sharding แบบ manual key-range ถูกใช้โดย Vitess (ชั้น sharding สำหรับ MySQL) เป็นต้น ส่วนแบบอัตโนมัติถูกใช้โดย Bigtable และ Hbase ซึ่งเป็นโอเพนซอร์สที่เทียบเท่ากัน ตัวเลือกการ sharding แบบ range-based ใน MongoDB รวมถึง CockroachDB, RethinkDB, และ FoundationDB [ 6 ]. YugabyteDB มีทั้งแบบแยก tablet แบบ manual และ automatic

ภายในแต่ละ shard key จะถูกเก็บในลำดับที่เรียง sorted (เช่น ใน B-tree หรือ SSTables ตามที่กล่าวถึงใน บทที่ 4 ). สิ่งนี้มีข้อดีคือการสแกนแบบช่วง (range scan) ทำได้ง่าย และคุณสามารถใช้ key เป็น concatenated index เพื่อดึงข้อมูล record ที่เกี่ยวข้องกันหลายรายการใน query เดียว (ดู "Multidimensional and Full-Text Indexes" ). ตัวอย่างเช่น พิจารณาแอปพลิเคชันที่เก็บข้อมูลจากเครือข่ายเซ็นเซอร์ โดยที่ key คือ timestamp ของการวัด การสแกนแบบช่วงมีประโยชน์มากในกรณีนี้ เพราะมันช่วยให้คุณดึงข้อมูล เช่น ค่าที่อ่านได้ทั้งหมดในเดือนใดเดือนหนึ่งได้อย่างง่ายดาย

ข้อเสียของ key-range sharding คือคุณอาจได้ hot shard ได้ง่ายถ้ามี write จำนวนมากไปที่ key ที่อยู่ใกล้กัน ตัวอย่างเช่น ถ้า key คือ timestamp shard จะสอดคล้องกับช่วงเวลา—เช่น หนึ่ง shard ต่อเดือน ถ้าคุณเขียนข้อมูลจากเซ็นเซอร์ไปยังฐานข้อมูลตามเวลาที่วัดค่าเกิดขึ้น write ทั้งหมดจะไปที่ shard เดียว (shard ของเดือนนี้) ทำให้ shard นั้นมี write เกินโหลดในขณะที่ shard อื่นๆ ไม่ได้ใช้งาน [ 13 ].

เพื่อหลีกเลี่ยงปัญหานี้ในฐานข้อมูลเซ็นเซอร์ คุณต้องใช้สิ่งอื่นที่ไม่ใช่ timestamp เป็นส่วนแรกของ key ตัวอย่างเช่น คุณสามารถนำหน้า timestamp แต่ละอันด้วย sensor ID เพื่อให้การเรียงลำดับ key เป็นไปตาม sensor ID ก่อนแล้วค่อยตาม timestamp สมมติว่าคุณมีเซ็นเซอร์หลายตัวทำงานพร้อมกัน write load จะกระจายไปทั่ว shard ได้เท่าเทียมกันมากขึ้น ข้อเสียคือเมื่อคุณต้องการดึงค่าจากเซ็นเซอร์หลายตัวภายในช่วงเวลา คุณจะต้องดำเนินการ range query แยกต่างหากสำหรับแต่ละเซ็นเซอร์

Rebalancing key-range sharded data (การปรับสมดุลข้อมูลที่ sharded ด้วย key-range)

เมื่อคุณตั้งค่าฐานข้อมูลครั้งแรก ยังไม่มีช่วง key ที่จะแบ่งออกเป็น shard ฐานข้อมูลบางระบบ เช่น HBase และ MongoDB อนุญาตให้คุณกำหนดค่า shard เริ่มต้นในฐานข้อมูลว่าง ซึ่งเรียกว่า pre-splitting . สิ่งนี้ต้องการให้คุณมีความคิดอยู่แล้วว่าการกระจาย key จะมีลักษณะอย่างไร เพื่อให้คุณสามารถเลือกขอบเขตของช่วง key ที่เหมาะสม [ 14 ].

ต่อมาเมื่อปริมาณข้อมูลและ write throughput เพิ่มขึ้น ระบบที่มี key-range sharding จะเติบโตโดยการแยก shard ที่มีอยู่ออกเป็นสอง shard หรือมากกว่าที่เล็กลง โดยแต่ละ shard จะถือช่วงย่อยที่ต่อเนื่องกันของช่วง key ของ shard ดั้งเดิม shard ที่เล็กลงที่ได้สามารถกระจายไปยังหลายโหนดได้ ถ้าข้อมูลจำนวนมากถูกลบ คุณอาจต้องรวม shard ที่อยู่ติดกันหลายตัวที่เล็กลงเป็นหนึ่ง shard ที่ใหญ่ขึ้น กระบวนการนี้คล้ายกับสิ่งที่เกิดขึ้นที่ระดับบนสุดของ B-tree (ดู "B-Trees" ).

ในฐานข้อมูลที่จัดการขอบเขตของ shard โดยอัตโนมัติ การแยก shard มักจะถูกกระตุ้นเมื่อ shard มีขนาดถึงเกณฑ์ที่กำหนดไว้ (เช่น บน HBase ค่าเริ่มต้นคือ 10 GB) หรือในบางระบบเมื่อ write throughput สูงเกินเกณฑ์ที่กำหนดอย่างต่อเนื่อง ดังนั้น hot shard อาจถูกแยกแม้ว่าจะไม่ได้เก็บข้อมูลจำนวนมาก เพื่อให้ write load ของมันกระจายตัวได้สม่ำเสมอมากขึ้น

ข้อดีคือจำนวน shard ปรับตามปริมาณข้อมูล ถ้ามีข้อมูลเพียงเล็กน้อย จำนวน shard เล็กน้อยก็เพียงพอ ดังนั้น overhead จึงน้อย ถ้ามีข้อมูลจำนวนมาก ขนาดของแต่ละ shard จะถูกจำกัดไว้ที่ขนาดสูงสุดที่กำหนดค่าได้ [ 15 ].

ข้อเสียคือการแยก shard เป็นการดำเนินการที่มีราคาแพง เนื่องจากต้องเขียนข้อมูลทั้งหมดใหม่เป็นไฟล์ใหม่ คล้ายกับการ compaction ใน log-structured storage engine shard ที่จำเป็นต้องถูกแยกมักจะเป็น shard ที่มีโหลดสูงด้วย และค่าใช้จ่ายของการแยกอาจทำให้โหลดนั้นแย่ลง เสี่ยงที่จะทำให้ shard นั้น overloaded

Sharding by Hash of Key (การแบ่งส่วนโดยใช้ Hash ของ Key)

Key-range sharding มีประโยชน์ถ้าคุณต้องการให้ record ที่มี partition key ที่อยู่ใกล้กัน (แต่ต่างกัน) ถูกรวมอยู่ใน shard เดียวกัน—ตัวอย่างเช่น ในกรณีของ timestamp ถ้าคุณไม่สนใจว่า partition key อยู่ใกล้กันหรือไม่ (เช่น ถ้าพวกมันเป็น tenant ID ในแอปพลิเคชัน multitenant) วิธีการทั่วไปคือการ hash partition key ก่อนที่จะแมปไปยัง shard

ฟังก์ชัน hash ที่ดีจะรับข้อมูลที่ skewed และทำให้มันกระจายอย่างสม่ำเสมอ สมมติว่าคุณมีฟังก์ชัน hash แบบ 32-bit ที่รับ string เมื่อไหร่ก็ตามที่คุณให้ string ใหม่ มันจะคืนค่าเลขที่ดูเหมือนสุ่มตั้งแต่ 0 ถึง 2 32  − 1. แม้ว่า input strings จะคล้ายกันมาก hash ของพวกมันจะกระจายอย่างสม่ำเสมอทั่วช่วงของตัวเลขนั้น (แต่ input เดียวกันจะให้ output เดียวกันเสมอ)

สำหรับวัตถุประสงค์ของ sharding ฟังก์ชัน hash ไม่จำเป็นต้องมีความแข็งแกร่งด้านการเข้ารหัส (cryptographically strong): ตัวอย่างเช่น MongoDB ใช้ MD5 ในขณะที่ Cassandra และ ScyllaDB ใช้ Murmur3 ภาษาโปรแกรมมิ่งหลายภาษามีฟังก์ชัน hash ง่ายๆ ในตัว (เนื่องจากใช้สำหรับ hash table) แต่มันอาจไม่เหมาะสมสำหรับ sharding: ตัวอย่างเช่น ใน Java's Object.hashCode() และ Ruby's Object#hash key เดียวกันอาจมีค่า hash ที่แตกต่างกันใน process ที่ต่างกัน ทำให้ไม่เหมาะสมสำหรับ sharding [ 16 ].

Hash modulo number of nodes (Hash Modulo จำนวนโหนด)

เมื่อคุณ hash key แล้ว คุณจะเลือก shard ไหนเพื่อเก็บมัน? สิ่งแรกที่คุณอาจนึกถึงคือการนำค่า hash ไป modulo ด้วยจำนวนโหนดในระบบ (ใช้ % operator ในภาษาโปรแกรมมิ่งหลายภาษา) ตัวอย่างเช่น hash ( key ) % 10 จะคืนค่าเลขตั้งแต่ 0 ถึง 9 (ถ้าเราเขียน hash เป็นเลขฐานสิบ hash  % 10 จะเป็นเลขหลักสุดท้าย) ถ้าเรามี 10 โหนด หมายเลข 0 ถึง 9 นั่นดูเหมือนเป็นวิธีง่ายๆ ในการกำหนดแต่ละ key ให้กับโหนด

ปัญหาของวิธีการ mod N คือถ้าจำนวนโหนด N เปลี่ยนแปลง key ส่วนใหญ่จะต้องถูกย้ายจากโหนดหนึ่งไปยังอีกโหนดหนึ่ง รูปที่ 7-3 แสดงให้เห็นสิ่งที่เกิดขึ้นเมื่อคุณมีสามโหนดและเพิ่มโหนดที่สี่ ก่อนการ rebalance โหนด 0 เก็บ key ที่มี hash 0, 3, 6, 9 และอื่นๆ หลังจากเพิ่มโหนดที่สี่ key ที่มี hash 3 ย้ายไปโหนด 3, key ที่มี hash 6 ย้ายไปโหนด 2, key ที่มี hash 9 ย้ายไปโหนด 1 และอื่นๆ

Figure 7-3. การกำหนด key ให้กับโหนดโดยการ hash key แล้วนำไป modulo ด้วยจำนวนโหนด การเปลี่ยนจำนวนโหนดส่งผลให้ key จำนวนมากย้ายจากโหนดหนึ่งไปยังอีกโหนดหนึ่ง

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

Fixed number of shards (จำนวน Shard แบบตายตัว)

วิธีแก้ปัญหาที่ง่ายแต่ใช้กันอย่างแพร่หลายคือการสร้าง shard จำนวนมากกว่าโหนดที่มีอยู่ และกำหนดหลาย shard ให้กับแต่ละโหนด ตัวอย่างเช่น ฐานข้อมูลที่รันบนคลัสเตอร์ 10 โหนดอาจถูกแบ่งออกเป็น 1,000 shard ตั้งแต่เริ่มต้น เพื่อให้ 100 shard ถูกกำหนดให้กับแต่ละโหนด จากนั้น key จะถูกเก็บไว้ใน shard หมายเลข hash ( key ) % 1,000 และระบบจะติดตามแยกต่างหากว่า shard ไหนถูกเก็บไว้บนโหนดใด

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

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

Figure 7-4. การเพิ่มโหนดใหม่ให้กับคลัสเตอร์ฐานข้อมูลที่มีหลาย shard ต่อโหนด

เป็นเรื่องปกติที่จะเลือกจำนวน shard ที่สามารถหารด้วยตัวประกอบหลายๆ ตัวได้ลงตัว เพื่อให้ชุดข้อมูลสามารถแบ่งเท่าๆ กันในจำนวนโหนดที่หลากหลาย—ไม่จำเป็นต้องให้จำนวนโหนดเป็นเลขยกกำลัง 2 เป็นต้น [ 4 ]. คุณสามารถคำนึงถึงฮาร์ดแวร์ที่ไม่เท่ากันในคลัสเตอร์ของคุณได้ด้วย: โดยการกำหนด shard ให้มากขึ้นกับโหนดที่มีพลังประมวลผลมากกว่า คุณสามารถทำให้โหนดเหล่านั้นรับส่วนแบ่งโหลดที่มากขึ้น

วิธีการ sharding นี้ถูกใช้ใน Citus (ชั้น sharding สำหรับ PostgreSQL), Riak, Elasticsearch, และ Couchbase เป็นต้น มันทำงานได้ดีตราบใดที่คุณมีการประมาณจำนวน shard ที่ดีที่คุณจะต้องการเมื่อคุณสร้างฐานข้อมูลครั้งแรก จากนั้นคุณสามารถเพิ่มหรือลบโหนดได้อย่างง่ายดาย โดยมีข้อจำกัดคือคุณไม่สามารถมีโหนดมากกว่าจำนวน shard ที่คุณมี

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

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

Sharding by hash range (การแบ่งส่วนตามช่วงของ Hash)

ถ้าจำนวน shard ที่ต้องการไม่สามารถคาดการณ์ล่วงหน้าได้ ควรใช้รูปแบบที่จำนวน shard สามารถปรับเปลี่ยนได้ง่ายตาม workload รูปแบบ key-range sharding ที่กล่าวถึงก่อนหน้านี้มีคุณสมบัตินี้ แต่มันมีความเสี่ยงที่จะเกิด hot spots เมื่อมี write จำนวนมากไปยัง key ที่อยู่ใกล้กัน วิธีแก้ปัญหาหนึ่งคือการรวม key-range sharding เข้ากับฟังก์ชัน hash เพื่อให้แต่ละ shard มีช่วงของ hash values แทนที่จะเป็นช่วงของ keys .

รูปที่ 7-5 แสดงตัวอย่างโดยใช้ฟังก์ชัน hash แบบ 16-bit ที่คืนค่าเลขตั้งแต่ 0 ถึง 65,535 = 2 16  − 1 (ในความเป็นจริง hash มักจะเป็น 32 bit หรือมากกว่า) แม้ว่า input keys จะคล้ายกันมาก (เช่น timestamp ที่ต่อเนื่องกัน) hash ของพวกมันจะกระจายอย่างสม่ำเสมอทั่วช่วงนั้น จากนั้นเราสามารถกำหนดช่วงของ hash values ให้กับแต่ละ shard—เช่น ค่าตั้งแต่ 0 ถึง 16,383 ให้กับ shard 0, ค่าตั้งแต่ 16,384 ถึง 32,767 ให้กับ shard 1 และอื่นๆ

Figure 7-5. การกำหนดช่วงของค่า hash ที่ต่อเนื่องกันให้กับแต่ละ shard

เช่นเดียวกับ key-range sharding ใน hash-range sharding shard สามารถถูกแยกได้เมื่อมันใหญ่เกินไปหรือมีโหลดหนักเกินไป นี่ยังคงเป็นการดำเนินการที่มีราคาแพง แต่มันสามารถเกิดขึ้นได้ตามต้องการ ดังนั้นจำนวน shard จะปรับตามปริมาณข้อมูลแทนที่จะถูกกำหนดตายตัวล่วงหน้า

ข้อเสียเมื่อเทียบกับ key-range sharding คือ range queries บน partition key จะไม่มีประสิทธิภาพ เนื่องจาก key ในช่วงนั้นจะกระจายไปทั่วทุก shard อย่างไรก็ตาม ถ้า key ประกอบด้วยสอง column หรือมากกว่า และ partition key เป็นเพียง column แรกในบรรดา column เหล่านี้ คุณยังคงสามารถทำ range queries ที่มีประสิทธิภาพบน column ที่สองและ column ต่อๆ ไปได้ ตราบใดที่ record ทั้งหมดใน range query มี partition key เดียวกัน พวกมันจะอยู่ใน shard เดียวกัน

Partitioning and Range Queries in Data Warehouses (Partitioning และ Range Queries ใน Data Warehouse)

Data warehouses เช่น BigQuery, Snowflake, และ Delta Lake รองรับวิธีการทำ index ที่คล้ายกัน แม้ว่าคำศัพท์จะแตกต่างกัน ใน BigQuery ตัวอย่างเช่น partition key จะกำหนดว่า record อยู่ใน partition ไหน ในขณะที่ "cluster columns" จะกำหนดว่า record ถูกเรียงลำดับอย่างไรภายใน partition Snowflake กำหนด record ให้กับ "micro-partitions" โดยอัตโนมัติ แต่อนุญาตให้ผู้ใช้กำหนด cluster keys สำหรับตาราง Delta Lake รองรับทั้งการกำหนด partition แบบ manual และ automatic และรองรับ cluster keys การทำ clustering ข้อมูลไม่เพียงแต่ปรับปรุงประสิทธิภาพการสแกนแบบช่วง แต่ยังสามารถปรับปรุงประสิทธิภาพการบีบอัดและการกรองข้อมูลได้อีกด้วย

YugabyteDB และ DynamoDB [ 17 ] ใช้ hash-range sharding และมันเป็นตัวเลือกใน MongoDB ด้วย Cassandra และ ScyllaDB ใช้รูปแบบที่แตกต่างของวิธีการนี้ ดังแสดงใน รูปที่ 7-6 .

Figure 7-6. Cassandra และ ScyllaDB แบ่งช่วงของค่า hash ที่เป็นไปได้ (ในที่นี้ 0–1024) ออกเป็นช่วงต่อเนื่องกันที่มีขอบเขตแบบสุ่ม และกำหนดหลายช่วงให้กับแต่ละโหนด

พื้นที่ของค่า hash ถูกแบ่งออกเป็นจำนวนช่วงที่เป็นสัดส่วนกับจำนวนโหนด (รูปแสดง 3 ช่วงต่อโหนด แต่ใน Cassandra จำนวนจริงคือ 16 ช่วงต่อโหนดโดยค่าเริ่มต้น และ 256 ช่วงต่อโหนดใน ScyllaDB) โดยมีขอบเขตแบบสุ่มระหว่างช่วงเหล่านั้น ซึ่งหมายความว่าบางช่วงมีขนาดใหญ่กว่าช่วงอื่น แต่การมีหลายช่วงต่อโหนด แนวโน้มความไม่สมดุลเหล่านั้นจะค่อยๆ ปรับสมดุลกัน [ 15 ].

เมื่อเพิ่มหรือลบโหนด ขอบเขตของช่วงจะถูกปรับและ shard จะถูกแยกหรือรวมตามนั้น ใน รูปที่ 7-6 เมื่อเพิ่มโหนด 3 โหนด 1 โอนส่วนหนึ่งของสองช่วงไปยังโหนด 3 และโหนด 2 โอนส่วนหนึ่งของช่วงหนึ่งไปยังโหนด 3 ผลคือทำให้โหนดใหม่ได้รับส่วนแบ่งข้อมูลที่ยุติธรรมโดยประมาณ โดยไม่ต้องถ่ายโอนข้อมูลมากเกินความจำเป็นจากโหนดหนึ่งไปยังอีกโหนดหนึ่ง

Consistent hashing (การแฮชแบบ Consistent)

อัลกอริทึม consistent hashing คือฟังก์ชัน hash ที่จับคู่ key ไปยังจำนวน shard ที่กำหนด ในลักษณะที่เป็นไปตามคุณสมบัติสองประการ:

• จำนวน key ที่จับคู่ไปยังแต่ละ shard มีประมาณเท่าๆ กัน

• เมื่อจำนวน shard เปลี่ยนแปลง key ที่ถูกย้ายจาก shard หนึ่งไปยังอีก shard หนึ่งจะมีจำนวนน้อยที่สุดเท่าที่เป็นไปได้

โปรดทราบว่า consistent ในที่นี้ไม่เกี่ยวข้องกับ replica consistency (ดู บทที่ 6 ) หรือ ACID consistency (ดู บทที่ 8 ) แต่อธิบายถึงแนวโน้มของ key ที่จะอยู่ใน shard เดิมถ้าเป็นไปได้

อัลกอริทึม sharding ที่ใช้โดย Cassandra และ ScyllaDB คล้ายกับนิยามดั้งเดิมของ consistent hashing [ 18 ] แต่อัลกอริทึม consistent hashing อื่นๆ ก็ถูกเสนอขึ้นมาเช่นกัน [ 19 ] เช่น highest random weight หรือที่รู้จักในชื่อ rendezvous hashing [ 20 ], และ jump consistent hashing [ 21 ]. ด้วยวิธีการเหล่านี้ แทนที่จะแยก shard ที่มีอยู่จำนวนน้อยออกเป็นช่วงย่อยเพื่อสร้าง shard ใหม่สำหรับโหนดที่ถูกเพิ่ม โหนดใหม่จะได้รับ key แต่ละตัวที่ก่อนหน้านี้กระจายอยู่ทั่วทุกโหนดอื่น วิธีไหนดีกว่ากันขึ้นอยู่กับแอปพลิเคชัน

Skewed Workloads and Relieving Hot Spots (Workload ที่เบ้และการบรรเทา Hot Spots)

Consistent hashing ช่วยให้แน่ใจว่า key กระจายอย่างสม่ำเสมอทั่วโหนด แต่นั่นไม่ได้หมายความว่าโหลดจริงจะกระจายอย่างสม่ำเสมอ ถ้า workload มีความเบ้สูง—นั่นคือ มีข้อมูลภายใต้ partition key บางตัวมากกว่าตัวอื่นมาก หรืออัตราคำขอไปยัง key บางตัวสูงกว่าตัวอื่นมาก—คุณยังคงลงเอยด้วยเซิร์ฟเวอร์บางตัวที่ overloaded ในขณะที่ตัวอื่นแทบไม่ได้ทำงาน

ตัวอย่างเช่น บนเว็บไซต์โซเชียลมีเดีย โพสต์ของผู้มีชื่อเสียงที่มีผู้ติดตามหลายล้านคนอาจทำให้เกิดกิจกรรมจำนวนมาก [ 22 ]. เหตุการณ์นี้สามารถส่งผลให้มีการอ่านและเขียนปริมาณมากไปยัง key เดียวกัน (โดยที่ partition key อาจเป็น user ID ของคนดัง หรือ ID ของการกระทำที่ผู้คนกำลังแสดงความคิดเห็น)

ในสถานการณ์เช่นนี้ จำเป็นต้องมีนโยบาย sharding ที่ยืดหยุ่นมากขึ้น [ 23 , 24 ]. ระบบที่กำหนด shard ตามช่วงของ key (หรือช่วงของ hash) ทำให้สามารถใส่ hot key แต่ละตัวไว้ใน shard ของมันเอง โดยอาจจะกำหนดเครื่องเฉพาะให้มันได้ [ 25 ].

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

อย่างไรก็ตาม เมื่อแยก write ข้ามหลาย key แล้ว read ใดๆ จะต้องทำงานเพิ่มเติม เพราะต้องอ่านข้อมูลจากทั้ง 100 key และรวมมันเข้าด้วยกัน ปริมาณการอ่านในแต่ละ shard ของ hot key ไม่ได้ลดลง มีเพียง write load เท่านั้นที่ถูกแยก เทคนิคนี้ยังต้องการการทำ bookkeeping เพิ่มเติม: การต่อท้ายเลขสุ่มนั้นสมเหตุสมผลเฉพาะกับ hot key จำนวนเล็กน้อยเท่านั้น สำหรับ key ส่วนใหญ่ที่มี write throughput ต่ำ นี่จะเป็น overhead ที่ไม่จำเป็น ดังนั้นคุณยังต้องการวิธีในการติดตามว่า key ไหนถูกแยก และกระบวนการในการแปลง key ปกติให้เป็น hot key ที่ถูกจัดการเป็นพิเศษ

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

บางระบบ (โดยเฉพาะ cloud services ที่ออกแบบมาสำหรับขนาดใหญ่) มีวิธีการอัตโนมัติในการจัดการกับ hot shards ตัวอย่างเช่น Amazon เรียกมันว่า heat management [ 26 ] หรือ adaptive capacity [ 17 ]. รายละเอียดว่าระบบเหล่านี้ทำงานอย่างไรนั้นอยู่นอกเหนือขอบเขตของหนังสือเล่มนี้

Operations: Automatic Versus Manual Rebalancing (การดำเนินงาน: การปรับสมดุลอัตโนมัติกับด้วยตนเอง)

เรามองข้ามคำถามสำคัญข้อหนึ่งเกี่ยวกับการ rebalance: การแยก shard และ rebalance เกิดขึ้นโดยอัตโนมัติหรือด้วยตนเอง?

บางระบบจะตัดสินใจโดยอัตโนมัติว่าเมื่อใดควรแยก shard และเมื่อใดควรย้ายมันจากโหนดหนึ่งไปยังอีกโหนดหนึ่ง โดยไม่ต้องมีการปฏิสัมพันธ์จากมนุษย์ ในขณะที่ระบบอื่นปล่อยให้การ sharding ถูกกำหนดค่าอย่างชัดเจนโดยผู้ดูแลระบบ นอกจากนี้ยังมีจุดกึ่งกลาง—ตัวอย่างเช่น Couchbase และ Riak จะสร้างการกำหนด shard ที่แนะนำโดยอัตโนมัติ แต่ต้องให้ผู้ดูแลระบบยืนยันก่อนที่จะมีผล

การ rebalance แบบอัตโนมัติเต็มรูปแบบสามารถสะดวกได้ เพราะมีงานปฏิบัติการน้อยกว่าสำหรับการบำรุงรักษาปกติ และระบบดังกล่าวสามารถปรับขนาดอัตโนมัติเพื่อปรับให้เข้ากับการเปลี่ยนแปลงของ workload ฐานข้อมูลบนคลาวด์เช่น DynamoDB ถูกโปรโมทว่าสามารถเพิ่มและลบ shard โดยอัตโนมัติเพื่อปรับให้เข้ากับการเพิ่มขึ้นหรือลดลงของโหลดภายในเวลาไม่กี่นาที [ 17 , 27 ].

อย่างไรก็ตาม การจัดการ shard แบบอัตโนมัติอาจคาดเดาไม่ได้เช่นกัน การ rebalance เป็นการดำเนินการที่มีราคาแพง เพราะมันต้อง reroute คำขอและย้ายข้อมูลจำนวนมากจากโหนดหนึ่งไปยังอีกโหนดหนึ่ง ถ้ากระบวนการนี้ไม่ได้ทำอย่างระมัดระวัง มันอาจทำให้เครือข่ายหรือโหนด overloaded และอาจเป็นอันตรายต่อประสิทธิภาพของคำขออื่นๆ ระบบต้องดำเนินการ write ต่อไปในขณะที่การ rebalance กำลังดำเนินการ ถ้าระบบใกล้ถึง write throughput สูงสุด กระบวนการแยก shard อาจไม่สามารถตามทันอัตราการเขียนที่เข้ามา [ 27 ].

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

ด้วยเหตุนั้น การให้มนุษย์อยู่ในวงจรการตัดสินใจ (human in the loop) สำหรับการ rebalance จึงอาจเป็นสิ่งที่ดี มันช้ากว่ากระบวนการอัตโนมัติเต็มรูปแบบ แต่สามารถช่วยป้องกันความประหลาดใจในการปฏิบัติการได้ การ rebalance ด้วยตนเองยังมีประโยชน์สำหรับการ rebalance เชิงป้องกัน ถ้ามีการคาดการณ์ว่าจะมีปริมาณการใช้งานเพิ่มขึ้นเนื่องจากเหตุการณ์ที่ทราบล่วงหน้า เช่น Cyber Monday หรือการขายตั๋วสำหรับการแข่งขันกีฬายอดนิยมอย่างฟุตบอลโลก

Request Routing (การกำหนดเส้นทางคำขอ)

เราได้พูดถึงวิธีการ shard ชุดข้อมูลข้ามหลายโหนด และวิธีการ rebalance shard เหล่านั้นเมื่อเพิ่มหรือลบโหนด ตอนนี้เรามาดูคำถามอีกข้อ: ถ้าคุณต้องการอ่านหรือเขียน key เฉพาะ คุณจะรู้ได้อย่างไรว่าต้องเชื่อมต่อกับโหนดใด—นั่นคือ ที่อยู่ IP และหมายเลขพอร์ตใด?

เราเรียกปัญหานี้ว่า request routing และมันคล้ายกันมากกับ service discovery ที่เราได้พูดถึงก่อนหน้านี้ใน "Load balancers, service discovery, and service meshes" . ความแตกต่างที่ใหญ่ที่สุดระหว่างทั้งสองคือกับ service ที่รันโค้ดแอปพลิเคชัน แต่ละ instance มักจะ stateless และ load balancer สามารถส่งคำขอไปยัง instance ใดก็ได้ กับฐานข้อมูลที่ sharded แล้ว คำขอสำหรับ key หนึ่งสามารถจัดการได้โดยโหนดที่เป็น replica สำหรับ shard ที่มี key นั้นเท่านั้น

ซึ่งหมายความว่า request routing ต้องรับรู้ถึงการกำหนด (assignment) จาก key ไปยัง shard และจาก shard ไปยังโหนด ในระดับสูง มีวิธีการสองสามวิธีสำหรับปัญหานี้ (แสดงใน รูปที่ 7-7 ):

1. อนุญาตให้ client ติดต่อโหนดใดก็ได้ (เช่น ผ่าน round-robin load balancer) ถ้าโหนดนั้นบังเอิญเป็นเจ้าของ shard ที่คำขอเกี่ยวข้อง โหนดก็สามารถจัดการคำขอได้โดยตรง มิฉะนั้น มันจะส่งต่อคำขอไปยังโหนดที่เหมาะสม รับคำตอบ และส่งคำตอบกลับไปยัง client

2. ส่งคำขอทั้งหมดจาก client ไปยัง routing tier ก่อน ซึ่งจะกำหนดโหนดที่ควรจัดการแต่ละคำขอและส่งต่อตามนั้น routing tier นี้ไม่ได้จัดการคำขอใดๆ ด้วยตัวเอง มันทำหน้าที่เป็น load balancer ที่รับรู้ shard เท่านั้น

3. กำหนดให้ client ต้องรู้จักการ sharding และการกำหนด shard ให้กับโหนด ในกรณีนี้ client สามารถเชื่อมต่อโดยตรงกับโหนดที่เหมาะสม โดยไม่มีตัวกลาง

Figure 7-7. สามวิธีในการกำหนดเส้นทางคำขอไปยังโหนดที่ถูกต้อง

แต่ละกรณีมีปัญหาสำคัญบางประการ:

• ใครเป็นคนตัดสินว่า shard ไหนควรอยู่บนโหนดไหน? วิธีที่ง่ายที่สุดคือให้มี coordinator ตัวเดียวทำการตัดสินใจนั้น แต่ในกรณีนั้นคุณจะทำให้มันทนทานต่อข้อผิดพลาดได้อย่างไรในกรณีที่โหนดที่รัน coordinator หยุดทำงาน? และถ้าบทบาท coordinator สามารถ fail over ไปยังโหนดอื่นได้ คุณจะป้องกันสถานการณ์ split-brain (ดู "Handling Node Outages" ) ที่ coordinator สองตัวที่แตกต่างกันทำการกำหนด shard ที่ขัดแย้งกันได้อย่างไร?

• component ที่ทำ routing (ซึ่งอาจเป็นหนึ่งในโหนด หรือ routing tier หรือ client) เรียนรู้เกี่ยวกับการเปลี่ยนแปลงในการกำหนด shard ให้กับโหนดได้อย่างไร?

• ในขณะที่ shard กำลังถูกย้ายจากโหนดหนึ่งไปยังอีกโหนดหนึ่ง จะมีช่วง cutover ที่โหนดใหม่รับช่วงต่อแล้ว แต่คำขอไปยังโหนดเก่าอาจยังคงดำเนินการอยู่ คุณจัดการกับคำขอเหล่านั้นอย่างไร?

ระบบข้อมูลแบบกระจายหลายระบบพึ่งพา coordination service แยกต่างหาก เช่น ZooKeeper หรือ etcd เพื่อติดตามการกำหนด shard ดังแสดงใน รูปที่ 7-8 . พวกมันใช้ consensus algorithms (ดู บทที่ 10 ) เพื่อให้ความทนทานต่อข้อผิดพลาดและการป้องกัน split brain แต่ละโหนดลงทะเบียนตัวเองใน ZooKeeper และ ZooKeeper รักษา mapping ที่เชื่อถือได้ของ shard ไปยังโหนด ตัวแสดงอื่นๆ เช่น routing tier หรือ sharding-aware client สามารถสมัครรับข้อมูลนี้ใน ZooKeeper เมื่อใดก็ตามที่ shard เปลี่ยนเจ้าของ หรือมีการเพิ่มหรือลบโหนด ZooKeeper จะแจ้ง routing tier เพื่อให้มันสามารถอัปเดตข้อมูล routing ให้ทันสมัยอยู่เสมอ

Figure 7-8. การใช้ ZooKeeper เพื่อติดตามการกำหนด shard ให้กับโหนด

ตัวอย่างเช่น HBase และ SolrCloud ใช้ ZooKeeper เพื่อจัดการการกำหนด shard และ Kubernetes ใช้ etcd เพื่อติดตามว่า service instance ไหนกำลังทำงานอยู่ที่ไหน MongoDB มีสถาปัตยกรรมที่คล้ายกัน แต่มันพึ่งพาการใช้งาน config server ของตัวเองและ mongos daemons เป็น routing tier Kafka, YugabyteDB, TiDB, และ ScyllaDB [ 28 ] ใช้การติดตั้งใช้งานในตัวของ Raft consensus protocol เพื่อทำหน้าที่ประสานงานนี้

Riak ใช้วิธีการที่แตกต่าง: มันใช้ gossip protocol ระหว่างโหนดเพื่อเผยแพร่การเปลี่ยนแปลงใดๆ ในสถานะคลัสเตอร์ สิ่งนี้ให้ consistency ที่อ่อนแอกว่า consensus protocol มาก มันเป็นไปได้ที่จะเกิด split brain ซึ่งส่วนต่างๆ ของคลัสเตอร์มีการกำหนดโหนดที่แตกต่างกันสำหรับ shard เดียวกัน ฐานข้อมูลแบบ Leaderless สามารถทนต่อสิ่งนี้ได้เพราะโดยทั่วไปแล้วพวกมันรับประกัน consistency แบบอ่อนอยู่แล้ว (ดู "Understanding the limitations of quorum consistency" ).

เมื่อ ใช้ routing tier หรือเมื่อส่งคำขอไปยังโหนดแบบสุ่ม client ยังคงต้องค้นหาที่อยู่ IP เพื่อเชื่อมต่อ สิ่งเหล่านี้ไม่ได้เปลี่ยนแปลงเร็วเท่าการกำหนด shard ให้กับโหนด ดังนั้นการใช้ DNS เพื่อจุดประสงค์นี้มักจะเพียงพอ

การอภิปรายเกี่ยวกับ request routing นี้เน้นไปที่การค้นหา shard สำหรับ key แต่ละตัว ซึ่งเกี่ยวข้องมากที่สุดกับฐานข้อมูล OLTP ที่ sharded ฐานข้อมูลเชิงวิเคราะห์ (analytical databases) มักใช้ sharding เช่นกัน แต่โดยทั่วไปแล้วพวกมันมีรูปแบบการเรียกใช้ query ที่แตกต่างกันมาก: แทนที่จะดำเนินการใน shard เดียว query มักจะต้องรวมและ join ข้อมูลจากหลาย shard แบบขนาน เราจะพูดถึงเทคนิคสำหรับการดำเนินการ query แบบขนานดังกล่าวใน บทที่ 11 .

Sharding and Secondary Indexes (Sharding และ Secondary Indexes)

รูปแบบ sharding ที่เราได้พูดถึงมาจนถึงตอนนี้ขึ้นอยู่กับการที่ client รู้จัก partition key สำหรับ record ใดๆ ที่มันต้องการเข้าถึง ทำได้ง่ายที่สุดในโมเดลข้อมูลแบบ key-value โดยที่ partition key คือส่วนแรกของ primary key (หรือ primary key ทั้งหมด) ดังนั้นเราสามารถใช้ partition key เพื่อกำหนด shard และนำทาง read และ write ไปยังโหนดที่รับผิดชอบ key นั้น

สถานการณ์จะซับซ้อนมากขึ้นถ้ามี secondary index เข้ามาเกี่ยวข้อง (ดู "Multicolumn and Secondary Indexes" ). โดยปกติแล้ว secondary index ไม่ได้ระบุ record ที่ไม่ซ้ำกัน แต่มันเป็นวิธีในการค้นหาการเกิดขึ้นของค่าเฉพาะ: ค้นหาการกระทำทั้งหมดโดยผู้ใช้ 123 , ค้นหาบทความทั้งหมดที่มีคำว่า hogwash , ค้นหารถทั้งหมดที่มีสี red , และอื่นๆ

Key-value stores มักจะไม่มี secondary index แต่มันเป็นฟีเจอร์มาตรฐานของ relational databases และพบได้ทั่วไปใน document databases การทำ index ประเภทนี้ยังเป็น raison d'être (เหตุผลของการดำรงอยู่) ของ full-text search engines เช่น Solr และ Elasticsearch ปัญหาของ secondary indexes คือมันไม่สามารถแมปกับ shard ได้อย่างลงตัว มีสองแนวทางหลักในการ sharding ฐานข้อมูลที่มี secondary indexes: local และ global

Local Secondary Indexes (Secondary Index แบบท้องถิ่น)

ในแนวทางการทำ index แบบแรก แต่ละ shard จะรักษา secondary indexes ของตัวเองอย่างอิสระ ซึ่งครอบคลุมเฉพาะ record ใน shard นั้นเท่านั้น มันไม่สนใจว่าข้อมูลอะไรถูกเก็บไว้ใน shard อื่น เมื่อใดก็ตามที่คุณเขียนไปยังฐานข้อมูล—เพื่อเพิ่ม, ลบ, หรืออัปเดต record—คุณจำเป็นต้องจัดการกับ shard ที่มี record ที่คุณกำลังเขียนเท่านั้น ด้วยเหตุนี้ secondary index ประเภทนี้จึงถูกเรียกว่า local index . ในบริบทของการค้นคืนสารสนเทศ (information retrieval) มันยังรู้จักในชื่อ document-partitioned index [ 29 ].

ตัวอย่างเช่น สมมติว่าคุณดำเนินการเว็บไซต์สำหรับขายรถมือสอง แต่ละรายการมี ID ที่ไม่ซ้ำกัน และคุณใช้ ID นั้นเป็น partition key สำหรับ sharding ดังแสดงใน รูปที่ 7-9 (ID 0 ถึง 499 ใน shard 0, ID 500 ถึง 999 ใน shard 1, ฯลฯ) ถ้าคุณต้องการให้ผู้ใช้ค้นหารถ โดยให้พวกเขากรองตามสีและยี่ห้อ คุณต้องมี secondary indexes บน color และ make (ใน document database สิ่งเหล่านี้จะเป็น field; ใน relational database พวกมันจะเป็น column) ถ้าคุณได้ประกาศ index ไว้ ฐานข้อมูลสามารถทำการ index โดยอัตโนมัติ ตัวอย่างเช่น เมื่อใดก็ตามที่มีการเพิ่มรถสีแดงลงในฐานข้อมูล database shard จะเพิ่ม ID ของมันลงในรายการ ID สำหรับรายการ index color:red ดังที่ได้กล่าวถึงใน บทที่ 4 รายการ ID นั้นยังเรียกว่า postings list .

Figure 7-9. ด้วย local secondary indexes แต่ละ shard จะทำ index เฉพาะ record ที่มันมีอยู่

Warning (คำเตือน)

ถ้าฐานข้อมูลของคุณรองรับเฉพาะโมเดล key-value คุณอาจถูกล่อลวงให้ implement secondary index ด้วยตัวเองโดยการสร้าง mapping จากค่าไปยัง ID ในโค้ดแอปพลิเคชัน ถ้าคุณเลือกเส้นทางนี้ คุณต้องระมัดระวังอย่างมากเพื่อให้แน่ใจว่า index ของคุณยังคง consistent กับข้อมูลพื้นฐาน race conditions และความล้มเหลวในการเขียนเป็นระยะ (ที่การเปลี่ยนแปลงบางอย่างถูกบันทึกแต่บางอย่างไม่ถูกบันทึก) สามารถทำให้ข้อมูลไม่ตรงกันได้อย่างง่ายดาย—ดู "The need for multi-object transactions" .

เมื่ออ่านจาก local secondary index ถ้าคุณรู้ partition key ของ record ที่คุณกำลังค้นหาอยู่แล้ว คุณสามารถค้นหาใน shard ที่เหมาะสมได้ ยิ่งไปกว่านั้น ถ้าคุณต้องการแค่ บาง ผลลัพธ์และไม่ต้องการทั้งหมด คุณสามารถส่งคำขอไปยัง shard ใดก็ได้ อย่างไรก็ตาม ถ้าคุณต้องการผลลัพธ์ทั้งหมดและไม่รู้ partition key ล่วงหน้า คุณจะต้องส่ง query ไปยังทุก shard และรวมผลลัพธ์ที่ได้กลับมา เพราะ record ที่ตรงกันอาจกระจายอยู่ทั่วทุก shard ใน รูปที่ 7-9 ตัวอย่างเช่น รถสีแดงปรากฏในทั้ง shard 0 และ shard 1

วิธีการ query ฐานข้อมูลที่ sharded นี้สามารถทำให้ read queries บน secondary indexes มีราคาแพงมาก แม้ว่าคุณจะ query shard แบบขนาน มันก็มีแนวโน้มที่จะเกิด tail latency amplification (ดู "Use of Response Time Metrics" ). มันยังจำกัดความสามารถในการปรับขนาด (scalability) ของแอปพลิเคชันของคุณ: การเพิ่ม shard มากขึ้นช่วยให้คุณเก็บข้อมูลได้มากขึ้น แต่มันไม่ได้เพิ่ม query throughput ถ้าทุก shard ต้องประมวลผลทุก query อยู่ดี

อย่างไรก็ตาม local secondary indexes ถูกใช้อย่างแพร่หลาย [ 30 ]—ตัวอย่างเช่น MongoDB, Riak, Cassandra [ 31 ], Elasticsearch [ 32 ], SolrCloud, และ VoltDB [ 33 ] ล้วนใช้ local secondary indexes

Global Secondary Indexes (Secondary Index แบบสากล)

แทนที่จะให้แต่ละ shard มี local secondary index ของตัวเอง เราสามารถสร้าง global index ที่ครอบคลุมข้อมูลในทุก shard อย่างไรก็ตาม เราไม่สามารถเก็บ index นั้นไว้บนโหนดเดียวได้ เพราะมันมักจะกลายเป็น bottleneck และทำลายจุดประสงค์ของ sharding global index ก็ต้องถูก sharded เช่นกัน แต่มันสามารถ sharded แตกต่างจาก primary-key index

รูปที่ 7-10 แสดงให้เห็นว่าสิ่งนี้อาจมีลักษณะอย่างไร ID ของรถสีแดงจากทุก shard ปรากฏภายใต้ color:red ใน index แต่ index ถูก sharded เพื่อให้สีที่ขึ้นต้นด้วยตัวอักษร a ถึง r ปรากฏใน shard 0 และสีที่ขึ้นต้นด้วย s ถึง z ปรากฏใน shard 1 index บนยี่ห้อรถก็ถูกแบ่ง partition ในลักษณะเดียวกัน (โดยมีขอบเขต shard อยู่ระหว่าง f และ h )

Figure 7-10. Global secondary index สะท้อนข้อมูลจากทุก shard และถูก sharded ด้วยค่าที่ถูกทำ index

index ประเภทนี้ยังเรียกว่า term-partitioned [ 29 ]. ย้อนกลับไปที่ "Full-Text Search" ในการค้นหาข้อความแบบเต็ม (full-text search) term คือคำสำคัญในข้อความที่คุณสามารถค้นหาได้ ในที่นี้เราขยายความหมายให้ครอบคลุมถึงค่าใดๆ ที่คุณสามารถค้นหาได้ใน secondary index

global index ใช้ term เป็น partition key เพื่อที่เมื่อคุณกำลังค้นหา term หรือค่าเฉพาะ คุณสามารถหาว่าต้อง query shard ไหน เช่นเดียวกัน shard สามารถมีช่วง term ที่ต่อเนื่องกัน (ดังใน รูปที่ 7-10 ) หรือคุณสามารถกำหนด term ให้กับ shard ตาม hash ของ term

Global indexes มีข้อดีคือ query ที่มีเงื่อนไขเดียว (เช่น color = red ) ต้องอ่านจาก shard เพียง shard เดียวเพื่อดึง postings list อย่างไรก็ตาม ถ้าคุณต้องการดึง record ไม่ใช่แค่ ID คุณยังคงต้องอ่านจากทุก shard ที่รับผิดชอบ ID เหล่านั้น

ถ้าคุณมีหลายเงื่อนไขการค้นหาหรือหลาย term (เช่น ค้นหารถที่มีสีและยี่ห้อที่แน่นอน หรือค้นหาคำหลายคำที่ปรากฏในข้อความเดียวกัน) term เหล่านั้นมักจะถูกกำหนดให้กับ shard ที่แตกต่างกัน ในการคำนวณ logical AND ของสองเงื่อนไข ระบบต้องหา ID ทั้งหมดที่ปรากฏใน postings lists ทั้งสอง ไม่ใช่ปัญหาถ้า postings lists สั้น แต่ถ้ามันยาว การส่งพวกมันผ่านเครือข่ายเพื่อคำนวณ intersection อาจช้า [ 29 ].

ความท้าทายอีกอย่างของ global secondary indexes คือ write ซับซ้อนกว่า local indexes เพราะการเขียน record เดียวอาจกระทบหลาย shard ของ index (ทุก term ในเอกสารอาจอยู่บน shard ที่แตกต่างกัน) สิ่งนี้ทำให้การรักษา secondary index ให้ sync กับข้อมูลพื้นฐานทำได้ยากขึ้น ทางเลือกหนึ่งคือการใช้ distributed transaction เพื่ออัปเดต shard ที่เก็บ primary record และ secondary indexes อย่าง atomic (ดู บทที่ 8 ).

Global secondary indexes ถูกใช้โดย CockroachDB, TiDB, และ YugabyteDB; DynamoDB รองรับทั้ง local และ global secondary indexes ในกรณีของ DynamoDB write จะถูกสะท้อนใน global indexes แบบ asynchronous ดังนั้นการอ่านจาก global index อาจได้ข้อมูลที่ล้าสมัย (คล้ายกับสถานการณ์ที่กล่าวถึงใน "Problems with Replication Lag" ). อย่างไรก็ตาม global indexes มีประโยชน์ถ้า read throughput สูงกว่า write throughput และถ้า postings lists ไม่ยาวเกินไป

Summary (สรุป)

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

เป้าหมายของ sharding คือการกระจายข้อมูลและปริมาณ query อย่างเท่าเทียมกันข้ามหลายเครื่อง หลีกเลี่ยง hot spots (โหนดที่มีโหลดสูงอย่างไม่สมส่วน) สิ่งนี้ต้องการการเลือกรูปแบบ sharding ที่เหมาะสมกับข้อมูลของคุณ และการ rebalance shard เมื่อมีการเพิ่มหรือลบโหนดออกจากคลัสเตอร์

เราได้พูดถึงสองแนวทางหลักในการ sharding:

Key range sharding (การแบ่งส่วนตามช่วง Key)

Key ถูกเรียงลำดับ และ shard หนึ่งเป็นเจ้าของ key ทั้งหมดตั้งแต่ค่าต่ำสุดถึงค่าสูงสุด การเรียงลำดับมีข้อดีคือสามารถทำ range queries ที่มีประสิทธิภาพได้ แต่มีความเสี่ยงที่จะเกิด hot spots ถ้าแอปพลิเคชันมักเข้าถึง key ที่อยู่ใกล้กันในลำดับที่เรียง

ในแนวทางนี้ โดยทั่วไปแล้ว shard จะถูก rebalance โดยการแบ่งช่วงออกเป็นสองช่วงย่อยเมื่อ shard ใหญ่เกินไป

Hash sharding (การแบ่งส่วนด้วย Hash)

ฟังก์ชัน hash ถูกนำไปใช้กับแต่ละ key และ shard จะเป็นเจ้าของช่วงของค่า hash (หรืออาจใช้อัลกอริทึม consistent hashing อื่นๆ เพื่อจับคู่ hash ไปยัง shard) วิธีนี้ทำลายการเรียงลำดับของ key ทำให้ range queries ไม่มีประสิทธิภาพ แต่มันอาจกระจายโหลดได้สม่ำเสมอมากขึ้น

เมื่อ sharding ด้วย hash เป็นเรื่องปกติที่จะสร้างจำนวน shard ที่แน่นอนล่วงหน้า กำหนดหลาย shard ให้กับแต่ละโหนด และย้าย shard ทั้งหมดจากโหนดหนึ่งไปยังอีกโหนดหนึ่งเมื่อเพิ่มหรือลบโหนด การแยก shard เช่นเดียวกับ key ranges ก็สามารถทำได้เช่นกัน

เป็นเรื่องปกติที่จะใช้ส่วนแรกของ key เป็น partition key (เช่น เพื่อระบุ shard) และเรียงลำดับ record ภายใน shard นั้นด้วยส่วนที่เหลือของ key วิธีนี้คุณยังคงสามารถทำ range queries ที่มีประสิทธิภาพระหว่าง record ที่มี partition key เดียวกันได้

เรายังได้พูดถึงเทคนิคในการ routing query ไปยัง shard ที่เหมาะสม และเราได้ดูว่า coordination service มักถูกใช้เพื่อติดตามการกำหนด shard ให้กับโหนดอย่างไร

สุดท้าย เราได้พิจารณาปฏิสัมพันธ์ระหว่าง sharding และ secondary indexes secondary index ก็ต้องถูก sharded เช่นกัน มีสองวิธีสำหรับสิ่งนี้:

Local secondary indexes (Secondary Index แบบท้องถิ่น)

secondary indexes ถูกเก็บ ไว้ใน shard เดียวกับ primary key และ value มีเพียง shard เดียวที่ต้องถูกอัปเดตเมื่อเขียน แต่การค้นหา secondary index ต้องอ่านจากทุก shard

Global secondary indexes (Secondary Index แบบสากล)

secondary indexes ถูก sharded แยกต่างหากตามค่าที่ถูกทำ index รายการใน secondary index อาจอ้างถึง record จากทุก shard ของ primary key เมื่อมีการเขียน record อาจต้องอัปเดตหลาย secondary index shard; อย่างไรก็ตาม การอ่าน postings list สามารถให้บริการจาก shard เดียว (การดึง record จริงยังคงต้องอ่านจากหลาย shard)

โดยการออกแบบ แต่ละ shard ทำงานอย่างอิสระเป็นส่วนใหญ่—นั่นคือสิ่งที่ทำให้ฐานข้อมูลที่ sharded สามารถขยายขนาดไปยังหลายเครื่องได้ อย่างไรก็ตาม การดำเนินการที่ต้องเขียนไปยังหลาย shard อาจเป็นปัญหา—ตัวอย่างเช่น จะเกิดอะไรขึ้นถ้า write ไปยัง shard หนึ่งสำเร็จ แต่อีก shard ล้มเหลว? เราจะตอบคำถามนั้นในบทต่อๆ ไป