จากข้อมูลของ wikipedia [1] Redundancy คือการคัดลอกหรือทำความซ้ำซ้อนให้กับองค์ประกอบหรือชิ้นส่วนใดๆของระบบให้มี มากกว่า 1 หน่วย ด้วยจุดประสงค์ในการเพิ่มความน่าเชื่อถือ (reliability) ให้กับระบบ เสมือนเป็นการสำรองชิ้นส่วนของระบบ ในกรณีที่ชิ้นส่วนหนึ่งผิดพลาด ก็ยังมีชิ้นส่วนอื่นที่เหมือนกันทำงานแทนกันได้ ดังนั้น ระบบก็ยังทำงานได้ต่อเนื่อง โดยไม่จำเป็นต้องรอการซ่อมแซมชิ้นส่วนที่เสียหายนั้น ถ้าหากเราไม่มี Redundancy สำหรับบางระบบ อาจถือว่าเป็นเรื่องใหญ่มากครับ เช่น หากฮาร์ดดิสก์ของ Server เว็บ Amazon.com เกิดพังขึ้นมา และถ้า amazon เขาไม่มีการ Redundancy ฮาร์ดดิสก์นี้ไว้ (เช่นใช้วิธี RAID) amazon คงต้องเสียรายได้ไปใช่น้อย

สำหรับในบทความนี้ ผมจะลงรายละเอียดถึงการทำความซ้ำซ้อนให้กับข้อมูล (Data Redundancy) หรือการจัดเก็บข้อมูล (Storage Redundancy) ที่ออกแบบมาใช้กับระบบแบบกระจาย โดยเป็นที่ต้องการมากในเครือข่ายแบบ Peer-to-Peer ครับ (คุณสามารถทำความเข้าใจพื้นฐานของ Peer-to-Peer ได้จากบทความเก่าของผมครับที่ [2] ครับ) ในที่นี้ ผมขอระบุว่าข้อมูลในที่นี้หมายถึงไฟล์ (File) หรือการทำ File Redundancy นั่นเองครับ

ขอให้เรานึกถึงระบบ Peer-to-Peer ประเภทแชร์ไฟล์ (Peer-to-Peer File Sharing) อย่าง BitTorrent และ KaZaa เป็นต้น ถ้าสมมติว่าเรามีไฟล์ที่ชื่อ A และ A มีเพียงแค่ 1 ไฟล์ในระบบ หากว่าคอมพิวเตอร์ที่เก็บไฟล์ A นี้ออกจากระบบ ก็หมายถึงไฟล์ A ต้องหายจากระบบไปด้วยนั่นเอง จึงทำให้ A ไม่มีให้บริการในระบบอีกต่อไป ซึ่งทำให้คุณสมบัติของระบบ Peer-to-Peer อย่างความคงอยู่ยาวนาน (หรือ Availability) ต้องหมดไปด้วย ดังนั้น นักวิจัยจึงนำRedundancy ในการแก้ปัญหานี้นั่นเองครับ หากว่าเรามี A เก็บอยู่บนคอมพิวเตอร์มากกว่า 1 เครื่อง (หรือมี A มากกว่า 1 ที่) A ก็ย่อมคงอยู่ในระบบยาวนานยิ่งขึ้น ถ้าหาก A ตัวหนึ่งต้องสูญหายไป ก็ยังมี A ตัวอื่นๆคงอยู่ในระบบ

เมื่อเราทำ File Redundancy เราจะได้อะไรมาบ้างเหรอครับ ผมขอสรุปสิ่งที่เราจะได้จาก Redundancy ไว้ 3 ข้อดังนี้

ความคงอยู่ยาวนาน (Availability) อันนี้ก็กล่าวไว้แล้วครับ ซึ่งเป็นการเพิ่มความคงทนให้กับระบบ (Fault tolerance) วิธีหนึ่ง เพราะเรามีไฟล์มากกว่า 1 แห่ง ไฟล์ก็ยังคงอยู่ในระบบยาวนานขึ้น
การแบ่งเบาภาระ (Load balancing) เช่น หากผมมีไฟล์ A บริการไว้บนคอมพิวเตอร์เซิร์ฟเวอร์ที่ชื่อ X แน่นอนครับหากว่ามีคนเข้ามาดาวน์โหลด A พร้อมกันจำนวนมากๆ คอมพิวเตอร์ X ก็ย่อมทำงานหนักไปด้วย คนที่เข้ามาโหลด A บางคนอาจจะพบปัญหา Server Busy (เคยเจอกันหรือเปล่า) อันเนื่องจาก X ทำงานหนักมากจนให้บริการไม่ไหวหรือตอบสนองการให้บริการให้ผู้ใช้ได้ไม่ทั่ว ถึง เป็นต้น แต่ถ้าหากผมมีคอมพิวเตอร์มากกว่า 1 เครื่องมาให้บริการ A ผมก็สามารถแบ่งเบาภาระการให้บริการไฟล์ A แก่ผู้ใช้จำนวนมากได้ด้วย
แคชชิ่ง (Caching) ซึ่งเป็นการคัดลอกไฟล์ให้อยู่ใกล้ผู้ที่ต้องการไฟล์ให้มากขึ้น หรือเรียกว่าเป็นวิธีการทำ Locality (ทำให้อยู่ในพื้นที่เดียวกัน) เช่น หากผมดาวน์โหลดไฟล์ A จากคอมพิวเตอร์ที่อเมริกามาแล้ว (สมมติผมอยู่ไทย) ครั้งต่อไปหากผมต้องการ A อีกครั้ง ผมก็ใช้ A บนคอมของผมได้เลย ไม่ต้องไปโหลดจากอเมริกาใหม่ และผมยังแชร์ A ให้คนที่อยู่เมืองไทยได้โหลด A ในความเร็วที่สูงกว่าไปโหลดจากอเมริกาได้ด้วย

กฎไตรลักษณ์กับ Redundancy

หากเราทำ Redundancy ได้แล้ว เราก็ไม่ได้ Availability, Load Balancing และ Caching ทันทีหรอกครับ หรืออาจจะได้มาแต่ก็ไม่ได้คงอยู่ไปตลอดกาลหรอกครับ ดั่งคำสอนของพระพุทธเจ้า “ทุกขัง อนิจจัง อนัตตา” กฎไตรลักษณ์ ที่ว่าไม่มีสิ่งใดคงอยู่ยั่งยืนถาวร อย่างเช่น ในเรื่อง Availability หากว่าเรามีไฟล์ A จำนวน 100 แห่ง หากว่า 100 แห่งเกิดล่มไปพร้อมๆกัน เราก็คงไม่ได้มาซึ่ง Availability ของไฟล์ A อีกต่อไป แต่ก็กล่าวได้ว่ามี Avaiability ที่สูงกว่ามี A เก็บไว้แค่ 2 – 3 ที่ เป็นต้น ส่วน Load Balancing กับ Caching นั้น เราจะได้สิ่งเหล่านี้มาจำเป็นต้องอาศัยเทคนิคอื่นๆเข้ามาช่วยเสริมด้วย หรือมีเหตุการณ์บางอย่างเข้ามาสนับสนุนด้วย แต่ผมไม่ขอกล่าวไว้ในบทความนี้ นะครับ ผมจะกล่าวเพียงกลยุทธ์ในการทำ Redundancy เท่านั้นครับ

กระบวนการทำ Redundancy

เรามีกระบวนการ (process) สำหรับทำความซ้ำซ้อนให้กับไฟล์ได้ 2 แบบคือ

Replication หรือการคัดลอก (ก๊อปปี้) ไฟล์ให้มีมากกว่า 1 สำเนา สมมติมีทั้งหมด N สำเนา จากนั้นเราสามารถกระจายสำเนานี้ไปตามคอมพิวเตอร์ในระบบให้ช่วยจัด เก็บและให้บริการสำเนาของไฟล์นี้ครับ และแน่นอนครับ หากเรามีไฟล์ N สำเนา เราก็ควรมีคอมพิวเตอร์ทั้งหมด N เครื่องสำหรับบริการไฟล์นี้ด้วยเช่นกัน โดยคอมพิวเตอร์ 1 เครื่องจะเก็บสำเนาของไฟล์ไว้ 1 สำเนา (จากทั้งหมด N) เมื่อไหร่ก็ตามที่ผู้ใช้ต้องการเข้าถึง (หรือใช้) ไฟล์นี้ ผู้ใช้เพียงดาวน์โหลดสำเนาของไฟล์เพียง 1 สำเนาจากคอมพิวเตอร์เครื่องใดๆที่เก็บสำเนานี้ไว้อยู่
Erasure Code เป็นวิธีการเข้ารหัสหรือการแปลงข้อมูลแบบหนึ่ง (Coding) ผมคงไม่อธิบายว่าเราจะสร้างกระบวนการของ Erasure code ได้อย่างไร เพราะมันก็ซับซ้อนพอสมควรครับ แต่ผมจะกล่าวถึงผลลัพธ์ของการทำ Erasure code โดยเมื่อไหร่ก็ตามที่เรานำไฟล์ (หรือข้อมูลใดๆ) ผ่านกระบวนการ Erasure code เราจะได้ชิ้นส่วนย่อย (fragment) ออกมาทั้งหมด N ชิ้น จากนั้น เราสามารถกระจายชิ้นส่วนย่อย N ชิ้น ไปตามคอมพิวเตอร์ในระบบ ซึ่งอาจจะเป็นไปได้ว่าชิ้นส่วนย่อยของไฟล์เดียวกันมากกว่า 1 ชิ้นอาจจะอยู่บนคอมพิวเตอร์เครื่องเดียวกัน และเมื่อไหร่ก็ตามที่ผู้ใช้ต้องการเข้าถึงไฟล์นี้ ผู้ใช้จำเป็นต้องดาวน์โหลดชิ้นส่วนให้ได้ทั้งหมด M ชิ้นที่ไม่ซ้ำกัน (ไม่จำเป็นต้องให้ได้ N ชิ้นนะ) เมื่อได้มา M ชิ้นแล้ว ต้องนำ M ชิ้นมาประกอบใหม่ (Reconstruct) เพื่อให้ได้ไฟล์ต้นฉบับ โดยสรุป Erasure code คือการสร้างชิ้นส่วนย่อย N ชิ้น โดยต้องการเพียง M ชิ้นที่แตกต่างกันเพื่อประกอบเป็นไฟล์ต้นฉบับ และ M ≤ N

Fix-Rate Code vs. Rateless Code

หากเราพิจารณาดีๆนะครับ Replication ก็คือ Erasure code แบบหนึ่ง เพราะ Replication คือการสร้างชิ้นส่วน N ชิ้น แต่ตอนประกอบไฟล์เราต้องการเพียง 1 ชิ้นเท่านั้น และหากเรามีข้อมูลขนาดใหญ่ เราสามารถแบ่งไฟล์นี้หลายๆชิ้นที่มีขนาดเท่ากัน เพื่อความรวดเร็วในการขนส่งไฟล์นั่นเอง แต่ละชิ้นเรียกว่า fragment สมมติผมแบ่งไฟล์มาได้ M ชิ้น (M fragments) จากนั้น ผมก็กระจาย M ชิ้นนี้ไปตามคอมพิวเตอร์ต่างๆ นอกจากนี้แล้ว ผมยังสามารถสำเนา fragment ได้ด้วย เพื่อรับประกันความคงอยู่ยาวนานของไฟล์นั่นเอง อย่างไรก็ดี แม้ว่าผมสำเนา fragment จากทั้ง M ชิ้นมากมายเท่าไหร่ก็ตาม แต่ตอนที่ผมต้องการประกอบไฟล์ต้นฉบับ ผมต้องรวบรวม fragment ทั้ง M ชิ้นที่แตกต่างกันมาให้ได้ แน่นอนครับ ต่อให้ผมรวบรวมมาได้ M ชิ้น แต่มีอยู่ 2 ชิ้นใน M ที่เป็นชิ้นส่วนเดียวกัน ผมก็ประกอบไฟล์ต้นฉบับไม่ได้แล้วครับ ลักษณะ Erasure code เช่นนี้เรียกว่า Fix-rate code ซึ่ง Replication ก็เป็น Fix-rate code แบบหนึ่ง

นอกจาก Fix-rate แล้วยังมี Erasure code อีกแบบหนึ่ง คือ Rateless code (อย่างเช่น Fountain code) ที่สามารถผลิต fragment จำนวน N ชิ้นที่ไม่ซ้ำกันทุกๆครั้ง และเมื่อต้องการประกอบชิ้นส่วนให้ได้ไฟล์ต้นฉบับ เราต้องการเพียงแค่ M ชิ้นเท่านั้น ยกตัวอย่างเช่น สมมติเราต้องการผลิตชิ้นส่วน fragment ของไฟล์ต้นฉบับบออกมา 5 ชิ้น โดยใช้ Rateless code เราก็สามารถผลิตชิ้นส่วน f1, f2, f3, f4, f5 ออกมา หากครั้งต่อไปเราผลิต fragment จำนวน 5 ชิ้นอีกครั้ง สมมติว่าได้ x1, x2, x3, x4, x5 ข้อมูลกลุ่มใหม่นี้ จะไม่ซ้ำกับข้อมูลกลุ่มอี่นที่เคยผลิตมาก่อนหน้านี้ (นั่นคือกลุ่ม f1, f2,…, f5) และเมื่อเราจะประกอบไฟล์ต้นฉบับ เราต้องการเพียงแค่ fragment เพียง M ชิ้น สมมติ M=3 ดังนั้น เราจึงต้องรวบรวม fragment ให้ได้ 3 ชิ้นจากทั้งหมดที่มีตอนนี้ 10 ชิ้น (ตอนนี้เรามี f1,f2,…, f5 และ x1,x2,…,x5) ซึ่งชิ้นส่วนทั้ง 3 นี้อาจจะเป็น (x1, x2, x5) ก็ได้ หรือ (f3, f4, f5) ก็ได้ หรือแม้กระทั่ง (x2, f1, f3) ก็ยังได้ ทั้งนี้เพราะว่า Ralteless นั้นผลิต fragment ไม่มีทางซ้ำกันเลย เราจึงเลือก fragment อะไรก็ได้ ขอเพียงให้ครบ M ชิ้นก็พอ เป็นต้น

สรุปความแตกต่างระหว่าง Fix-rate กับ Rateless ให้เราพิจารณาที่การรับประกัน Availability หรือความคงอยู่ยาวนานของข้อมูล เมื่อเราใช้ Fix-rate code เราจำเป็นต้องสำเนาหรือทำ replication ให้กับ fragment ให้มีจำนวนเยอะๆ เพราะเดิมทีเมื่อข้อมูลผ่านกระบวนการ Fix-rate แล้ว เราจะได้ fragment จำนวน M ชิ้น ดังนั้น เราต้องทำสำเนา fragment ใน M ชิ้นนี้ให้มีมากขึ้น สมมติว่าสำเนาแล้ว fragment ที่มีในระบบทั้งหมด N ชิ้น เมื่อไหร่ก็ตามที่เราจะประกอบไฟล์ต้นฉบับ เราต้องรวบรวม fragment ที่แตกต่างกันให้ได้ M ชิ้น ซึ่งต่างจาก Rateless code ที่เราไม่จำเป็นต้องทำ replication เลย เพราะว่า Rateless สามารถผลิต fragment ที่แตกต่างกันทุกครั้ง สมมติว่า Rateless ผลิต fragment มาได้ N ชิ้น เราเพียงรวบรวมมาให้ได้ M ชิ้น โดยไม่ต้องกังวลเลยว่ามันจะซ้ำกันหรือเปล่า เราก็สามารถประกอบไฟล์ ต้นฉบับได้แล้ว

Fragment Metadata

ในการพัฒนาระบบแบบ Redundancy จริงๆนั้น เราสามารถเพิ่มข้อมูลบางอย่าง (metadata) พ่วงไปกับ fragment แต่ละชิ้น เพื่อช่วยในการประกอบไฟล์ต้นฉบับ และยังช่วยในการตรวจสอบความถูกต้อง (Verification) โดยข้อมูลที่เราสามารถเพิ่มเข้าไปให้กับ fragment ได้แก่ Fragment ID, File ID, File Signature และ Timestamp เป็นต้น

Fragment ID เป็นรหัสประจำตัวของ Fragment โดย Fragment 2 ตัวใดๆ (ของไฟล์เดียวกัน) ต้องมี Fragment ID ที่ต่างกัน โดยปกติเราจะรัน Fragment ID เป็นเลขจำนวนเต็มแบบเรียงลำดับ (Sequence number) เช่น 0, 1, 2, … เป็นต้น หรืออาจจะใช้ Hash function เพื่อ สร้าง signature ไว้เป็นรหัสประจำตัวของ fragment ID และยังมีประโยชน์ต่อการตรวจสอบความถูกต้องในการอัพโหลดหรือดาวน์โหลด fragment อีกด้วย
File ID เป็นรหัสประจำตัวของไฟล์ต้นฉบับของ fragment เราอาจจะใช้ hash function เพื่อช่วยในการสร้าง ID ของ file ก็ได้ หรือใช้หลักการอื่นๆอย่างเช่น หลักการสร้าง Key ที่ใช้ใน Freenet (อ่านเพิ่มใน [3]) เป็นต้น
File Signature เป็นลายเซ็น (signature) ของไฟล์ต้นฉบับของ fragment เราจะใช้ลายเซ็นนี้ตรวจสอบความถูกต้องในการประกอบไฟล์ต้นฉบับ ซึ่งเราสามารถใช้ hash function ในการสร้าง File signature ก็ได้ หรือเราสามารถใช้ File ID เป็น File Signature เพื่อลดขนาดของ metadata
Timestamp เป็นการระบุวันเวลาของไฟล์ อาจจะมีประโยชน์ในการตรวจสอบ version ของไฟล์

เราไม่จำเป็นต้องใช้ Metadata เหล่านี้ครบทุกตัว มันขึ้นอยู่กับความต้องการของระบบ และเราสามารถเพิ่ม metadata ตามความต้องการได้ (เช่น index หรือ description ของไฟล์ที่จะช่วยในการค้นหาไฟล์โดยอิงจาก keyword) แต่ metadata ที่ผมยกตัวอย่างมานี้ จะมีเพิ่มความสะดวกในการค้นหา fragment และช่วยตรวจสอบความถูกต้องในการประกอบไฟล์ต้นฉบับ เช่น หากเราต้องการค้นหา fragment ของไฟล์ที่ชื่อ A เราก็เพียงแต่ค้นหา fragment ที่มี File ID เหมือนกับ File ID ของ A และเลือกเฉพาะ fragment ที่มี fragment ID ไม่เหมือนกับ fragment ที่รวบรวมมาได้แล้ว เป็นต้น และข้อมูลอย่าง File Signature เป็นสิ่งสำคัญที่ใช้ในการตรวจสอบความถูกต้องในการประกอบไฟล์ และจริงๆเราไม่จำเป็นต้องเก็บ File Signature เข้าไปใน metadata เลย แต่ผู้ใช้จำเป็นต้องทราบ File Signature เอง (เช่น BitTorrent จะเก็บ file signature และ fragment signature ไว้ในไฟล์นามสกุล torrent) เมื่อเราประกอบไฟล์เรียบร้อย เราก็เพียงนำ signature ของไฟล์ที่ประกอบได้ไปเทียบกับ signature ของไฟล์ต้นฉบับที่เราทราบอยู่แล้ว ถ้า signature ตรงกันก็แปลว่าเราประกอบไฟล์ได้สมบูรณ์

โปรดติตตามตอนต่อไป

โอเคครับ ภาค 1 ของ Redundancy นี้ผมต้องการปูพื้นฐานเท่านั้นครับ สำหรับภาค 2 ผมจะกล่าวถึงกลยุทธ์หรือ Strategy ของการทำ Redundancy เพราะการทำ Redundancy มันก็มีราคาของมันอยู่ ผมหมายความว่า การทำ Redundancy ไม่ใช่ว่าเราจะผลิต fragment ของไฟล์หรือสำเนาไฟล์มากมายเท่าไหร่ก็ได้ตามใจชอบ เพราะการทำ redundancy ย่อมต้องใช้ bandwidth ของเครือข่ายในการกระจายไฟล์และต้องใช้พื้นที่จัดเก็บข้อมูลหรือ storage สำหรับจัดเก็บfragment ถ้าหากเราทำ redundancy อย่างไม่ยั้งคิด เราก็ย่อมต้องบริโภค bandwidth ของเครือข่ายและพื้นที่จัดเก็บข้อมูลอย่างฟุ่มเฟือยไปด้วยครับ โอเคครับ ไว้ติดตามภาค 2 แล้วกัน