Reasons for Replication (เหตุผลที่ต้องมีการทำซ้ำ)

มีสาเหตุหลักๆอยู่สองอย่างคือ 1. ความเชื่อถือได้ (reliability) 2. ประสิทธิภาพ (performance)

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

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

Replication as Scaling Technique

อย่างที่ได้ว่าไว้ในขั้นต้นว่าการทำขยายตัวของระบบ นำไปสู่การขยายตัวของ storage ซึ่งจะเป็นจำต้องอยู่ใกล้กับ process การทำงานให้มากที่สุดเพราะจะช่วยลดในเรื่องของ access time ดังนั้นปัญหาที่ตามมาก็คือ การ synchronize data ระหว่าง replica ด้วยกันจะทำอย่างไรให้สูญเสีย performance น้อยที่สุด ซึ่งตรงนี้มันเป็น trade-off ระหว่าง performance และ data consistency ดังนั้นถ้าเราลดเรื่องของ consistency ลงมา นั่นก็คือข้อมูลในสอง replica จะไม่ตรงกัน เราก็จะสามารถเพิ่ม performance ของระบบได้ซึ่งการลด consistency นั้นขึ้นอยู่กับลักษณะของระบบที่ทำงานอยู่

ความยากของการ synchronize นั่นสังเกตได้จากความเป็นจริงที่ว่าเราจะต้อง synchronize ทุกๆ replica ซึ่งหมายถึงว่าทุกๆ replica จะต้องทำความเข้าใจกันว่าจะมีการ update แบบ local เมื่อใด เช่นถ้าหาก replica ใช้ลักษณะการตัดสินใจแบบ Lamport timestamp หรือใช้ coordinator จัดการ การ sync กันแต่ละทีจะต้องทำการส่ง message เป็นจำนวนมากทำให้เสียเวลา (ลด performance)

Replica Placement

เมื่อมีการใช้ replica ในระบบแล้ว ปัญหาทีจะตามมาก้คือเราจะวาง replica อย่างไร  ซึ่งแบ่งได้อีกเป็นสองปัญหาย่อยคือ 1. การวาง server replica 2. การวาง content นั่นคือตำแหน่งที่ดีที่สุดในการวาง server อยู่ที่ใด กับเราจะเอา content ไปวางไว้ที่ server ใดบ้าง

Content Replica

เราสามารถแบ่งลักษณะของ content replica ได้เป็นสามแบบคือ 1. permanent 2. server-initiated 3. client-initiated

Permanent Replica

ลักษณะของ shared-nothing architecture นั่นคือระบบไม่ได้แชร์ทรัพยากรใดๆ ร่วมกันเลยไม่ว่าจะเป็น data หรือ memory เช่น web server ที่กระจายตัวอยู่ตาม internet ที่มีข้อมูลเหมือนกัน แต่ว่าไม่ได้ใช้ข้อมูลจากที่เดียวกัน

Server-Initiated Replica

เป็นการสร้าง replica จาก owner ของระบบเองเช่น ในกรณีที่ web server รับโหลดมากๆ ทำให้ต้องมีการตั้ง web server เพิ่มซึ่งการติดตั้งนี้มาจาก owner โดยตรง  โดยอาจจะนำ web server นี้ไปวางในตำแหน่งที่ใกล้กับ request ที่เข้ามา โดยปัญหาคือเมื่อไหร่ถึงจะต้องทำการ สร้างหรือทำลาย server ทิ้ง

Client-Initiated Replica

เป็นลักษณะของ cache เช่นการเล่นเว็บ ก็จะมีการเก็บ cache ของข้อมูล static ต่างๆไว้ภายในเครื่องของผู้ใช้งานเอง โดยปริมาณและระยะเวลาในการเก็บก็จะมีมากน้อยแตกต่างกันออกไปตามความต้องการของผู้ใช้งาน โดยยิ่งถ้ามีการเก็บข้อมูลไว้นาน การเปลี่ยนแปลงที่เกิดขึ้นในฝั่ง server เราก็ไม่อาจจะรับรู้ได้ โดยปกติก็จะเป็นการเก็บ cache ภายในเครื่องของผู้ใช้ หรือเครื่องที่ถูกแชร์โดย client หลายๆเครื่องเช่น proxy

Update Propagation (Content Distribution)

การจัดการ replica นอกจาก placement แล้ว การ update ข้อมูลไปยัง replica ก็เป็นอีกปัญหาหนึ่ง

State Vs. Operation

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

การส่ง notification เราเรียกว่า invalidation protocol โดยการทำงานของ protocol นี้จะมีการส่ง notification ไปบอกว่าข้อมูลชุดนี้ invalid ไม่สามารถใช้งานได้แล้ว และเมื่อมีความต้องการที่จะ update ชุดข้อมูลที่ invalid replica จะต้องทำการ update ข้อมูลชุดนั้นเสียก่อน จึงจะสามารถทำงานได้  ข้อดีคือไม่เปลือง bandwidth ซึ่งทำงานได้ดีเมื่อมีการอัพเดทข้อมูลบ่อยๆ

การส่งชุดข้อมูลไปอัพเดทข้อมูลทั้งหมดก็เป็นอีกทางเลือกนึงที่เหมาะสำหรับระบบที่มีอัตรส่วน read-to-write สูง เพราะว่าโอกาสที่ข้อมูลที่ถูก updated แล้ว จะถูกอ่านก่อนการเขียนมีมากกว่า

การส่งคำสั่ง (update operation) ไปยัง replica ก็เป็นวิธีที่ประหยัด bandwidth ซึ่งเรียกว่า active replication แต่อย่างไรก็ตามวิธีนี้จะต้องใช้ processing power เยอะกกว่าปกติ ในกรณีที่คำสั่งมีความซับซ้อนมาก

Pull Vs. Push Protocol

อีกปัจจัยหนึ่งที่ต้องดูนอกจากวิธีการส่งอัพเดทก็คือ การส่งด้วยการ push หรือ pull การส่งแบบ push เป็น server-based approach ซึ่งการอัพเดทนั้นจะส่งไปยัง replica โดยที่ replica เหล่านั้นไม่จำเป็นต้องร้องขอการอัพเดท ซึ่งการ push นี้นิยมใช้กับ permanent และ server-initiated replica หรืออาจจะใช้กับ client-initiated ก็ได้หากต้องการ consistency ระหว่างข้อมุลด้วยกัน ซึ่ง protocol แบบ push จะทำให้ข้อมูลตรงกันในทันที

การ Pull คือการดึงอัพเดทจาก server ซึ่งนิยมใช้กับ client มากกว่าเช่น cache ซึ่งการทำงานแบบ pull นี้เหมาะกับ read-to-update ratio ที่ต่ำ(พวก static data) ข้อเสียของ pull คือหาก cache miss แล้วจะเสียเวลาในการดึงข้อมูลทำให้ response time สูงขึ้น

Unicasting Vs. Multicasting

การส่งแบบ unicast คือส่ง message n message ไปยัง n server

ส่วน multicast คือส่ง 1 message ไปยัง n server

การส่งแบบ multicast ประหยัด bandwidth กว่าถ้าหากอยู่ใน local area เดียวกันซึ่งการส่งแบบ multicast นี้นิยมใช้กับ push protocol  ส่วนการ poll นั้นนิยมใช้ unicast มากกว่า

Consistency Protocols

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

Primary-based Protocols

Remote-Write Protocols

เป็น protocol แบบ primary ที่ง่ายที่สุด โดยการ write จะถูก forward ไปยัง server ที่กำหนดไว้ (Primary Server) และ Primary server จะทำการ update backup server ที่เหลือ เมื่อ update เสร็จแล้วก็จะส่ง acknowledge กลับมายัง Primary server และเมื่อทุกๆ backup server ทำการอัพเดทเสร็จ Primary server จะทำการ ack กลับไปยัง process ที่ส่งคำสั่ง write มา ส่วนการ read สามารถอ่านได้ที่ server ที่ใกล้ที่สุดได้เลย

ปัญหาที่อาจจะเกิดขึ้นได้นั่นคือ process ที่ทำการ write จะต้องรอเป็นระยะเวลาหนึ่งก่อนที่จะทำงานต่อไปได้ (block) วิธีแก้ไขคือให้ process ทำงานแบบ non block โดยเมื่อ primary server แก้ไขข้อมูลของมันเองแล้ว จะส่ง ack กลับมายัง process เพื่อทำงานต่อไป

Local-write Protocols

เป็นลักษณะอีกแบบหนึ่งโดยจะทำการย้าย primary server มายัง backup server ที่ใกล้กับ process ที่สุดแทน โดยจะต้องเป็นการทำงานแบบ non blocking

ข้อดีคือการ write สามารถทำได้ง่ายกว่าและทำได้ใกล้ตัวมันเอง โดย protocol นี้สามารถนำไปประยุกต์ใช้กับ application บนมือถือได้ โดย application สามารถทำงานได้ถึงแม้ว่าจะ disconnected จาก data store โดยก่อนที่จะ disconnected application จะย้าย primary มาอยู่ที่มือถือเสียก่อน โดยที่ process อื่นๆจะไม่สามารถ update ข้อมูลลงไปใน data store ได้ และเมื่อมีการเชื่อมต่ออีกครั้งจะทำการ update ไปยัง backup ทำให้ data store  มี consistency อีกครั้ง และทุก process กลับมา update ได้เหมือนเดิม

Replicated-write Protocols

การอัพเดทจะถูกส่งไปยังทุกๆ replica เหมือนกับการส่งไปแค่ที่เดียว

Active Replication

ในแต่ละ replica จะมี process ที่ทำการ update operation

ปัญหาของ active replication คือ operation จะต้องทำงานเป็น sequence เดียวกันในทุกๆ replica ดังนั้นจึงต้องมีกระบวนการ totally-ordered multicast โดยอาจจะใช้ lamport’s logical clock ก็ได้ หรืออาจจะมี central coordinator ทำหน้าทีเป็น sequencer คอยจัดลำดับ โดยจะต้องส่ง operation มาที่ coordinator ก่อน

Replicated-write Quorum-based Protocols

ช่วยทำให้เกิดความเป็น atomic กันระหว่าง replica หลายๆตัว โดยจะใช้หลักการ Vote ของแต่ละ replica

ลักษณะการทำงานของโปรโตคอลนี้ จะมี  Vr (read quorum) ละ Vw (write quorum) และ V คือจำนวนโหวด(เครื่อง)ทั้งหมด

โดยมีข้อกำหนดในการทำงานดังนี้

1. Vr + Vw > V
2. Vw > V/2

ความหมายของข้อแรกคือเป็นการป้องกัน ไม่ให้มีการ read และ write โดย 2 concurrent transaction ส่วนข้อที่สองคือจะไม่มี 2 concurrent transaction พยามยามที่จะเขียนพร้อมๆกัน