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

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 เป็นฐานข้อมูลขนาดเล็กในตัวเอง แม้ว่าฐานข้อมูลบางระบบจะรองรับ operation ที่แตะหลาย 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 กับ 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 .

ทุกเรื่องเกี่ยวกับ database 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 แม้แต่บนเครื่องเดียว โดยมักรัน single-threaded 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 เพื่อรองรับหลาย tenant)

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

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

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

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

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

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

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

คุณใช้ sharding ได้ไม่เฉพาะกับ storage แต่กับ service ที่รันโค้ดแอปพลิเคชันของคุณด้วย ใน cell-based architecture service และ storage ของ 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 แยกกัน การ export และลบข้อมูลก็จะเป็นเพียง operation ง่ายๆ บน 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 load ให้สม่ำเสมอทั่วทุกโหนด ถ้าแต่ละโหนดรับส่วนแบ่งเท่าๆ กัน ในทางทฤษฎี 10 โหนดก็ควรรับข้อมูลและ read/write throughput ได้มากกว่าโหนดเดียวถึง 10 เท่า (ไม่นับ replication) เมื่อคุณเพิ่มหรือลบโหนด ก็ต้อง rebalance โหลดใหม่เพื่อให้กระจายสม่ำเสมอตามจำนวนโหนดที่เปลี่ยนไป

ถ้า การแบ่ง shard ไม่สมดุล ทำให้บาง 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 spot ได้

Sharding by Key Range (การ shard ตามช่วงของ key)

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

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

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

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

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

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

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

Rebalancing key-range sharded data (การ rebalance ข้อมูลที่ shard ด้วย key-range)

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

ต่อมาเมื่อข้อมูลและ write throughput เพิ่มขึ้น ระบบที่ใช้ key-range sharding จะขยายตัวโดยแยก shard ที่มีอยู่เป็นสอง shard หรือมากกว่า โดยแต่ละ shard ใหม่จะถือช่วงย่อยที่ต่อเนื่องกันของ key range เดิม 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 เป็น operation ที่แพง เพราะต้องเขียนข้อมูลทั้งหมดใหม่ลงไฟล์ใหม่ คล้ายกับ compaction ใน log-structured storage engine และ shard ที่ต้องถูกแยกมักเป็น shard ที่มีโหลดสูงอยู่แล้ว ต้นทุนของการแยกอาจทำให้โหลดนั้นแย่ลง จน shard overloaded ได้

Sharding by Hash of Key (การ shard ด้วย hash ของ key)

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

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

สำหรับ sharding แล้ว hash function ไม่จำเป็นต้อง cryptographically strong (แข็งแกร่งด้านการเข้ารหัส) เช่น MongoDB ใช้ MD5 ส่วน Cassandra และ ScyllaDB ใช้ Murmur3 ภาษาโปรแกรมหลายภาษามี hash function ง่ายๆ ติดมาให้ (เพราะใช้กับ 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 ให้โหนด การย้ายนี้ไม่ได้เกิดขึ้นทันที เพราะต้องใช้เวลาถ่ายโอนข้อมูลจำนวนมากผ่านเครือข่าย ดังนั้น read และ write ที่เกิดขึ้นระหว่างการถ่ายโอนจะยังใช้การกำหนด shard แบบเก่า

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

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

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

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

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

Sharding by hash range (การ shard ตามช่วงของ hash)

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

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

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

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

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

Partitioning และ Range Query ใน Data Warehouse

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

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

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

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

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

Consistent hashing

algorithm consistent hashing คือ hash function ที่แมป key ไปยัง shard จำนวนหนึ่งที่กำหนด โดยมีคุณสมบัติสองข้อ:

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

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

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

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

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

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

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

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

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

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

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

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

Operations: Automatic Versus Manual Rebalancing (การ rebalance แบบอัตโนมัติกับแบบ manual)

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

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

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

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

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

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

Request Routing (การส่ง request ไปยังโหนดที่ถูกต้อง)

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

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

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

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

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

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

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

แต่ละวิธีมีปัญหาสำคัญที่ต้องแก้:

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

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

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

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

Figure 7-8. การใช้ ZooKeeper ติดตามการกำหนด shard ให้โหนด

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

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

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

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

Sharding กับ Secondary Index

รูปแบบ 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 store มักไม่มี secondary index แต่เป็นฟีเจอร์มาตรฐานของ relational database และพบได้ทั่วไปใน document database การทำ index ประเภทนี้ยังเป็น raison d'être (เหตุผลของการดำรงอยู่) ของ full-text search engines เช่น Solr และ Elasticsearch ปัญหาของ secondary index คือแมปกับ shard ได้ไม่ลงตัว การ shard ฐานข้อมูลที่มี secondary index มีสองแนวทางหลัก คือ local และ global

Local Secondary Indexes (secondary index แบบ local)

ในแนวทางแรก แต่ละ shard จะดูแล secondary index ของตัวเองแยกจากกัน ซึ่งครอบคลุมเฉพาะ 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 index บน color และ make (ใน document database สิ่งเหล่านี้เป็น field ส่วนใน relational database เป็น column) ถ้าคุณประกาศ index ไว้ ฐานข้อมูลจะทำ index ให้โดยอัตโนมัติ ตัวอย่างเช่น เมื่อมีการเพิ่มรถสีแดงลงฐานข้อมูล shard นั้นจะเพิ่ม ID ของมันลงในรายการ ID ของ index entry color:red ดังที่กล่าวถึงใน บทที่ 4 รายการ ID นั้นยังเรียกว่า postings list .

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

Warning (คำเตือน)

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

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

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

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

Global Secondary Indexes (secondary index แบบ global)

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

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

Figure 7-10. Global secondary index ครอบคลุมข้อมูลจากทุก shard และถูก shard ด้วยค่าที่ถูกทำ 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 index คือ query ที่มีเงื่อนไขเดียว (เช่น color = red ) อ่านจาก shard เดียวก็ดึง postings list ได้ แต่ถ้าต้องการ record ไม่ใช่แค่ ID ก็ยังต้องอ่านจากทุก shard ที่รับผิดชอบ ID เหล่านั้น

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

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

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

Summary (สรุป)

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

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

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

Key range sharding (การ shard ตามช่วงของ key)

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

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

Hash sharding (การ shard ด้วย hash)

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

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

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

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

สุดท้าย เราได้ดูว่า sharding ทำงานร่วมกับ secondary index อย่างไร secondary index ก็ต้องถูก shard เช่นกัน ซึ่งทำได้สองวิธี:

Local secondary indexes (secondary index แบบ local)

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

Global secondary indexes (secondary index แบบ global)

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

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