วิธีการทำ Distributed Locking (2016)

 (martin.kleppmann.com)
4 คะแนน โดย GN⁺ 2024-10-21 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • Redlock ที่อิงกับ Redis มีเป้าหมายเพื่อทำ distributed lock ที่ทนต่อความล้มเหลว แต่ยังไม่ปลอดภัยพอสำหรับงานที่ความถูกต้องมีเดิมพัน และซับซ้อนเกินไปสำหรับการใช้เพื่อเพิ่มประสิทธิภาพ
  • ต้องแยกเป้าหมายของ distributed lock ก่อนว่าเพื่อ ประสิทธิภาพ ในการลดงานซ้ำ หรือเพื่อ ความถูกต้อง ในการปกป้องสถานะที่ใช้ร่วมกัน โดยเกณฑ์ตัดสินคือเมื่อเกิดความล้มเหลวจะเป็นเพียงต้นทุนที่เพิ่มขึ้น หรือเป็นความเสียหายของข้อมูล
  • ต่อให้มีบริการล็อกที่สมบูรณ์แบบ ก็ยังอาจเกิดการเขียนข้อมูลเก่าหลัง lease หมดอายุได้จาก GC pause นาน ๆ, การหยุดชั่วคราวของโปรเซส, หรือความหน่วงเครือข่าย จึงต้องมี fencing token
  • Redlock ไม่สามารถสร้างโทเค็นที่เพิ่มขึ้นแบบ monotonic ได้ทุกครั้งที่ได้ล็อก และการหมดอายุของคีย์ใน Redis ก็พึ่งพานาฬิการะบบที่อิง gettimeofday ทำให้ความปลอดภัยพังได้เมื่อเกิด การกระโดดของเวลา หรือความหน่วง
  • สำหรับล็อกที่ต้องการความถูกต้อง ควรใช้ consensus system อย่าง ZooKeeper ร่วมกับการตรวจสอบ fencing token และควรจำกัดการใช้ Redis single-node lock ไว้กับงานเชิงประมาณหรือไม่ใช่งานสำคัญ

จุดตั้งต้นของการพิจารณา Redlock

  • Redlock เป็นอัลกอริทึมสำหรับทำ distributed lock บน Redis หรือพูดให้แม่นยำกว่าคือ lease
  • มี implementation อิสระอยู่แล้วมากกว่า 10 ตัว และไม่อาจรู้ได้ว่าใครบ้างกำลังพึ่งพาอัลกอริทึมนี้อยู่ จึงควรค่าแก่การทบทวนแบบสาธารณะ
  • ตัว Redis เองเหมาะกับการแชร์ข้อมูลชั่วคราว แบบคร่าว ๆ และเปลี่ยนแปลงเร็วระหว่างเซิร์ฟเวอร์
    • เช่น ตัวนับจำนวนคำขอต่อ IP address, ชุดของ IP ที่ไม่ซ้ำกันต่อ user ID
  • จุดที่น่ากังวลคือแนวโน้มที่ Redis ถูกนำไปใช้มากขึ้นกับงานจัดการข้อมูลที่คาดหวัง consistency และ durability ที่แข็งแรงกว่า ซึ่ง distributed lock ก็เป็นหนึ่งในนั้น

เป้าหมายของล็อก: ประสิทธิภาพหรือความถูกต้อง

  • ใน distributed application ล็อกคือกลไกที่ทำให้เมื่อหลายโหนดพยายามทำงานเดียวกัน จะมีเพียงหนึ่งตัวที่ทำในเวลาเดียวกัน
  • เหตุผลในการใช้ล็อกแบ่งได้ใหญ่ ๆ เป็นสองแบบ
    • ประสิทธิภาพ: เป็นการ optimize เพื่อไม่ให้คำนวณราคาแพงซ้ำสองรอบ ต่อให้พลาดก็อาจแค่เสียค่า AWS เพิ่มเล็กน้อย หรือส่งอีเมลแจ้งเตือนซ้ำ
    • ความถูกต้อง: เป็นกลไกป้องกันไม่ให้โปรเซสพร้อมกันหลายตัวทำให้สถานะเดียวกันเสียหาย และถ้าล้มเหลวอาจเกิดปัญหาร้ายแรง เช่น ไฟล์เสียหาย, ข้อมูลสูญหาย, ความไม่สอดคล้องถาวร, หรือให้ยาผิด
  • สำหรับล็อกที่ใช้เพื่อประสิทธิภาพ ต้นทุนและความซับซ้อนของ Redlock ที่ต้องใช้ Redis 5 เซิร์ฟเวอร์และตรวจแบบเสียงข้างมากนั้นไม่จำเป็น
    • ใช้ Redis instance เดียวร่วมกับ asynchronous replication เมื่อจำเป็นจะเหมาะกว่า
    • ในกรณีนี้อาจเสียล็อกบางส่วนจากไฟดับหรือปัญหาที่โหนด Redis ได้ แต่ถ้าเป็น optimization ที่ไม่สำคัญมาก ก็เป็นความล้มเหลวที่ยอมรับได้
  • Redlock ดูเหมือนจะเหมาะกับล็อกที่เน้นความถูกต้องเพราะมี 5 replicas และใช้เสียงข้างมาก แต่ในความเป็นจริงกลับไม่เหมาะกับเป้าหมายนั้น

lease อย่างเดียวไม่สามารถปกป้อง resource ได้อย่างปลอดภัย

  • ล็อกใน distributed system ต่างจาก mutex ในแอปพลิเคชัน multithread เพราะโหนดและเครือข่ายอาจล้มเหลวแยกจากกันได้ จึงซับซ้อนกว่า
  • ลำดับงานทั่วไปในการอัปเดตไฟล์บน shared storage คือ ได้ล็อก, อ่านไฟล์, แก้ไข, เขียนกลับ, แล้วปล่อยล็อก
    • ล็อกมีไว้เพื่อป้องกันไม่ให้สอง client ทำ read-modify-write พร้อมกันแล้วเกิด lost update
  • ถ้า client หยุดค้างนานขณะถือครองล็อก lease อาจหมดอายุได้
    • GC อาจเข้ามาทำให้ client หยุดไปนาน
    • lease เป็นการออกแบบที่ดีเพื่อไม่ให้ client ที่ crash ไปจับล็อกค้างตลอด แต่ถ้าช่วงหยุดยาวกว่าเวลาหมดอายุ client อาจยังไม่รู้ว่า lease หมดแล้ว และไปทำการเขียนที่อันตราย
  • ปัญหานี้ไม่ใช่แค่กรณีในทางทฤษฎี เพราะ HBase ก็เคยมีปัญหาคล้ายกัน
    • เคยมีกรณีที่ GC แบบ “stop-the-world” หยุดนานเป็นนาที
    • แม้แต่ GC แบบ “concurrent” อย่าง CMS ของ HotSpot JVM ก็ยังต้องหยุดแอปพลิเคชันเป็นครั้งคราว
  • วิธีเช็กว่า lease หมดอายุหรือไม่ก่อนเขียนก็ไม่ช่วยแก้ปัญหา
    • GC อาจหยุดเธรดที่กำลังทำงานได้ทุกจุด รวมถึงระหว่างการเช็กรอบสุดท้ายกับการเขียนจริง

การหยุดของโปรเซสและความหน่วงเครือข่ายคือ threat model ปกติ

  • ต่อให้ใช้ runtime ที่ไม่มี GC pause ยาว ๆ โปรเซสก็ยังหยุดได้จากหลายสาเหตุ
    • อาจอ่าน address ที่ไม่อยู่ใน memory แล้วเกิด page fault
    • ถ้าดิสก์เป็น EBS การอ่านตัวแปรอาจกลายเป็น synchronous request ผ่านเครือข่าย Amazon
    • การแย่ง CPU, ความล่าช้าจาก scheduler, หรือ SIGSTOP ที่ส่งมาผิดพลาด ก็ทำให้โปรเซสหยุดได้
  • ความหน่วงเครือข่ายก็สร้างปัญหาแบบเดียวกัน
    • แอปพลิเคชันอาจส่งคำขอเขียนไปแล้ว แต่ packet ล่าช้าจนไปถึง storage server หลัง lease หมดอายุ
    • ใน incident หนึ่งของ GitHub มี packet เครือข่ายล่าช้าถึงประมาณ 90 วินาที
  • เครือข่ายแบบ packet อย่าง Ethernet และ IP สามารถหน่วง packet แบบตามอำเภอใจได้ และในโลกจริงก็เกิดขึ้นจริง
  • ดังนั้นแม้ในเครือข่ายที่ดูแลดี ก็ไม่ควรตั้งสมมติฐานเรื่องเวลา และโค้ดแบบอิง lease อย่างเดียวก็ไม่ปลอดภัยโดยพื้นฐาน ไม่ว่าจะใช้บริการล็อกแบบใดก็ตาม

ต้องใช้ fencing token เพื่อกันการเขียนข้อมูลเก่า

  • วิธีแก้คือใส่ fencing token ไปกับทุกคำขอเขียนไปยัง storage
  • fencing token เป็นตัวเลขที่เพิ่มขึ้นทุกครั้งที่ client ได้ล็อก
    • เช่น client 1 ได้ lease พร้อม token 33 แล้วหยุดไปนานจน lease หมดอายุ
    • client 2 ได้ lease ใหม่พร้อม token 34 แล้วส่งคำขอเขียนไปยัง storage
    • ต่อมา client 1 ตื่นขึ้นและส่งคำขอเขียนด้วย token 33 ซึ่ง storage จะปฏิเสธ เพราะเคยประมวลผล token 34 ที่มากกว่าไปแล้ว
  • เพื่อให้ปลอดภัย storage server ต้องตรวจสอบโทเค็นอย่างจริงจัง และปฏิเสธการเขียนที่ค่า token ถอยหลัง
  • หากบริการล็อกสามารถสร้างโทเค็นที่เพิ่มขึ้นแบบ monotonic อย่างเคร่งครัด ก็ทำให้ล็อกปลอดภัยได้
    • ถ้าใช้ ZooKeeper เป็นบริการล็อก ก็ใช้ zxid หรือหมายเลขเวอร์ชันของ znode เป็น fencing token ได้
  • ปัญหาใหญ่ของ Redlock คือ ไม่มีความสามารถในการสร้าง fencing token
    • ค่าสุ่มเฉพาะของ Redlock ไม่ได้ให้คุณสมบัติการเพิ่มขึ้นแบบ monotonic ที่ต้องการ
    • ตัวนับบน Redis node เดียวไม่พอ เพราะโหนดนั้นล้มเหลวได้
    • ตัวนับจากหลายโหนดอาจไม่สอดคล้องกัน
    • แม้แต่การสร้าง fencing token เองก็อาจต้องใช้อัลกอริทึม consensus

Redlock พึ่งพาสมมติฐานเรื่องเวลาเพื่อความปลอดภัย

  • ใน distributed algorithm โมเดลที่ใช้งานได้จริงคือ asynchronous model พร้อม unreliable failure detector
    • โปรเซสอาจหยุดได้นานเท่าใดก็ได้
    • packet อาจถูกหน่วงในเครือข่ายได้นานเท่าใดก็ได้
    • นาฬิกาอาจผิดพลาดได้อย่างไม่มีข้อจำกัด
    • ถึงอย่างนั้นอัลกอริทึมก็ยังควรตัดสินใจได้อย่างถูกต้อง
  • นาฬิกาควรถูกใช้แค่เพื่อสร้าง timeout เพื่อไม่ให้รอไปตลอดเมื่อโหนดล่ม
    • timeout ไม่จำเป็นต้องแม่น และเมื่อ request timeout ก็ไม่ได้แปลว่าอีกโหนดล่มแน่ ๆ
    • อาจเป็นเพราะความหน่วงเครือข่ายหรือความผิดพลาดของนาฬิกาในเครื่องก็ได้
  • Redis ใช้ gettimeofday ไม่ใช่ monotonic clock ในการตัดสินว่าคีย์หมดอายุเมื่อใด
    • gettimeofday ทำให้เวลาในระบบกระโดดแบบไม่ต่อเนื่องได้
    • หาก NTP ปรับนาฬิกาหรือผู้ดูแลเปลี่ยนเวลาเอง การหมดอายุของคีย์ Redis อาจเร็วหรือช้ากว่าที่คาดมาก
  • อัลกอริทึมใน asynchronous model โดยทั่วไปควรรักษา safety ไว้ได้โดยไม่พึ่งสมมติฐานด้านเวลา และ failure detector อย่าง timeout ควรกระทบเพียง liveness
    • ถ้า timing เพี้ยน ประสิทธิภาพอาจแย่ลงได้ แต่ไม่ควรตัดสินใจผิด
  • Redlock ต่างออกไป เพราะความปลอดภัยของมันขึ้นกับสมมติฐานด้าน timing หลายข้อ
    • ทุก Redis node ต้องเก็บคีย์ไว้นานประมาณที่ถูกต้อง
    • ความหน่วงเครือข่ายต้องน้อยกว่าเวลาหมดอายุมากพอ
    • การหยุดของโปรเซสต้องสั้นกว่าเวลาหมดอายุมาก

กรณีที่ Redlock พังเมื่อ timing แย่

  • ถ้ามี Redis 5 โหนด A, B, C, D, E และ client 1, 2 เมื่อเวลาของโหนดหนึ่งกระโดดไปข้างหน้า client ทั้งสองอาจเชื่อว่าตัวเองถือล็อกอยู่
    • client 1 ได้ล็อกจาก A, B, C แต่มีปัญหาเครือข่ายจนไปไม่ถึง D, E
    • นาฬิกาของ C กระโดดไปข้างหน้า ทำให้ล็อกหมดอายุ
    • client 2 ได้ล็อกจาก C, D, E แต่มีปัญหาเครือข่ายจนไปไม่ถึง A, B
    • ผลคือทั้ง client 1 และ 2 ต่างสรุปว่าตัวเองเป็นผู้ถือล็อก
  • ปัญหาคล้ายกันเกิดได้หาก C crash ก่อน persist ล็อกลงดิสก์ แล้วรีสตาร์ตทันที
    • เอกสารของ Redlock แนะนำให้หน่วงการรีสตาร์ตโหนดที่ crash ไว้อย่างน้อยนานกว่า TTL ของล็อกที่ยาวที่สุด
    • แต่การหน่วงรีสตาร์ตนี้ก็ยังพึ่งการวัดเวลาที่แม่นพอสมควร และถ้านาฬิกากระโดดก็ล้มเหลวได้
  • การหยุดของโปรเซสฝั่ง client ก็ทำให้ Redlock พังได้
    • client 1 ขอรับล็อกจาก A, B, C, D, E
    • ขณะ response กำลังเดินทาง client 1 เข้า stop-the-world GC
    • ล็อกใน Redis ทุกโหนดหมดอายุ
    • client 2 ได้ล็อกจาก A, B, C, D, E
    • client 1 จบ GC แล้วรับ success response ที่ค้างอยู่ใน kernel network buffer
    • ทั้งสอง client ต่างเชื่อว่าตัวเองถือล็อกอยู่
  • ที่ Redis เขียนด้วย C และไม่มี GC ไม่ได้ช่วยอะไร
    • ปัญหาเกิดในระบบที่ ฝั่ง client อาจเจอ GC pause ได้
    • เพื่อให้ปลอดภัย ต้องมีวิธีอย่าง fencing token เพื่อกันงานของ client 1 หลังจาก client 2 ได้ล็อกแล้ว
  • ความหน่วงเครือข่ายยาว ๆ ก็ให้ผลเหมือนโปรเซสหยุด
    • หากตั้ง TCP user timeout ให้สั้นกว่า Redis TTL มาก packet ที่ล่าช้าอาจถูกเพิกเฉยได้ แต่ต้องดู implementation ของ TCP โดยละเอียดจึงจะมั่นใจ
    • แม้กรณีนี้ก็ยังย้อนกลับไปสู่ปัญหาเรื่องความแม่นของการวัดเวลาอยู่ดี

สมมติฐานแบบ synchronous system ที่ Redlock ต้องการ

  • Redlock จะทำงานถูกต้องได้เฉพาะใน synchronous system model ที่มีคุณสมบัติดังนี้
    • มีการรับประกันขอบเขตบนของความหน่วงเครือข่าย
    • เวลาที่โปรเซสหยุดมีขีดจำกัด
    • ความคลาดเคลื่อนของนาฬิกามีขีดจำกัด
  • synchronous model ไม่ได้แปลว่านาฬิกาซิงก์ตรงกันเป๊ะ แต่หมายถึงมีขอบเขตบนคงที่ที่รู้ล่วงหน้าสำหรับ network delay, pause และ clock drift
  • Redlock สมมติว่า delay, pause และ drift ทั้งหมดเล็กเมื่อเทียบกับ TTL ของล็อก
    • ถ้าปัญหา timing ใหญ่ขึ้นมาระดับเดียวกับ TTL อัลกอริทึมก็จะล้มเหลว
  • ในสภาพแวดล้อมดาต้าเซ็นเตอร์ทั่วไป สมมติฐานเรื่องเวลาแบบนี้อาจเป็นจริงเกือบตลอดเวลา ซึ่งเรียกว่า partially synchronous system
  • แต่ถ้าความถูกต้องต้องพึ่งล็อก คำว่า “เกือบตลอดเวลา” ยังไม่เพียงพอ
    • ทันทีที่สมมติฐานเรื่อง timing พัง Redlock อาจละเมิด safety เช่น ให้ lease แก่ client อีกตัวก่อนที่ lease ของ client เดิมจะหมด
    • กรณี packet delay 90 วินาทีของ GitHub เป็นหลักฐานว่าการสมมติ synchronous system model ในสภาพแวดล้อมจริงเป็นเรื่องยาก
  • Raft, Viewstamped Replication, Zab และ Paxos อยู่ในกลุ่มอัลกอริทึม consensus ที่ออกแบบมาสำหรับ partially synchronous system model หรือ asynchronous model ที่มี failure detector
    • อัลกอริทึมเหล่านี้จำเป็นต้องทิ้งสมมติฐานด้านเวลา และระวังไม่สมมติว่าเครือข่าย, โปรเซส และนาฬิกาใน distributed system เชื่อถือได้มากกว่าความจริง

บทสรุปและทางเลือกที่แนะนำ

  • Redlock หนักและมีต้นทุนเกินจำเป็นสำหรับล็อกที่ใช้เพื่อ optimize ประสิทธิภาพ และก็ยังไม่ปลอดภัยพอสำหรับล็อกที่ความถูกต้องมีความสำคัญ
  • โดยเฉพาะมันตั้งสมมติฐานแบบ synchronous system เกี่ยวกับความหน่วงเครือข่ายและเวลาการประมวลผลอย่างมีนัยสำคัญ และเมื่อสมมติฐานนั้นพัง ก็อาจละเมิดความปลอดภัยได้
  • อีกทั้งยังไม่มีความสามารถสร้าง fencing token เพื่อป้องกันระบบจากความหน่วงเครือข่ายยาว ๆ หรือโปรเซสที่หยุดค้าง
  • หากต้องการล็อกแบบ best-effort เพื่อ optimize ประสิทธิภาพ การใช้ single-node lock algorithm ของ Redis จะเหมาะกว่า
    • ได้ล็อกด้วย conditional set-if-not-exists
    • ปล่อยล็อกด้วยการลบแบบ atomic เฉพาะเมื่อค่าตรงกัน
    • ควรระบุในโค้ดอย่างชัดเจนว่าล็อกนี้เป็นแบบประมาณและอาจล้มเหลวได้เป็นครั้งคราว
    • ไม่จำเป็นต้องตั้ง Redis cluster 5 โหนด
  • สำหรับล็อกที่ต้องการความถูกต้อง ไม่ควรใช้ Redlock แต่ควรใช้ consensus system อย่าง ZooKeeper
    • หากทำได้ สามารถใช้ Curator recipes ที่มี implementation ของล็อกให้แล้ว
    • อย่างน้อยอาจใช้ฐานข้อมูลอย่าง PostgreSQL ที่ให้ transaction guarantee ในระดับที่สมเหตุสมผล
    • และต้องบังคับให้การเข้าถึง resource ทุกอย่างภายใต้ล็อกตรวจสอบ fencing token ด้วย
  • Redis เป็นเครื่องมือที่มีประโยชน์เมื่อใช้ตรงตามวัตถุประสงค์ และเครื่องมือทุกชนิดมีข้อจำกัด จึงต้องเข้าใจข้อจำกัดนั้นและวางแผนให้เหมาะสม
  • ในอัปเดตวันที่ 9 กุมภาพันธ์ 2016 Salvatore ผู้เขียนต้นฉบับของ Redlock ได้โพสต์บทความโต้แย้ง แต่ข้อสรุปยังคงเดิม

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2024-10-21
ความคิดเห็นจาก Hacker News

  • ที่ทำงานใช้ Temporal อยู่ และเราใช้ workflow กับ signal เฉพาะเพื่อทำ distributed lock
    จนถึงตอนนี้ทำงานได้ดี และพอฝากส่วนการจัดการแบบกระจายของ lock ให้ฟีเจอร์ของ Temporal การ implement ก็เรียบง่ายพอสมควร

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

  • สำหรับ distributed lock ปกติจะใช้ PostgreSQL advisory lock
    แม้งานนั้นจะไม่เกี่ยวกับฐานข้อมูลก็ตาม แค่เริ่ม transaction แล้วจับ advisory lock ไว้ lock ก็จะคงอยู่จนกว่าแอปจะปล่อยเอง หรือ transaction จบลงเพราะ crash ฯลฯ
    จนถึงตอนนี้รู้สึกว่าค่อนข้างปลอดภัย แต่เพิ่งนึกได้ว่าไม่เคยตรวจเลยว่า connection ไปยังฐานข้อมูลยังปกติดีอยู่หรือไม่
    ถ้าเป็นงานที่เกี่ยวกับฐานข้อมูล query ก็คง fail แล้วงานก็ fail ตามไปด้วย แต่ถ้าไม่ใช่ อาจเสีย lock ไปแล้วโดยไม่รู้ตัวก็ได้
    ถ้าต้องการความถูกต้องแบบเด็ดขาดโดยไม่มี fencing token หรือ atomic operation สุดท้ายแล้วทุกงานต้องใช้ two-phase commit หรือเปล่าก็ไม่แน่ใจ

    • advisory lock มีหลุมพรางเยอะ ดู [0]
      ถ้าจะทำสิ่งที่ตั้งใจไว้ให้ถูกต้อง อาจต้องใช้ “EXCLUSIVE” หรือ “ACCESS EXCLUSIVE” หรือไม่ก็ต้องทำ two-phase commit สำหรับงานนั้น หรือทำให้เป็น idempotent
      [0] https://www.postgresql.org/docs/current/explicit-locking.htm...
    • สิ่งที่ต้องระวังเรื่อง lock เท่าที่รู้คือ lock เป็นแบบ ต่อ connection
      library ส่วนใหญ่มักใช้ connection pool ดังนั้นต้องกัน connection เฉพาะสำหรับ lock ไว้ และการตรวจ lock เป็นระยะก็ต้องทำผ่าน connection นั้นเท่านั้น

  • แนะนำให้อ่านคอมเมนต์ที่ผมเคยทิ้งไว้ในคอมเมนต์ของบล็อกนี้ และคำตอบที่เขียนไว้ในบล็อกของผมเอง
    ไล่แบบไม่เรียงลำดับนะ ผู้เขียนพลาดจุดสำคัญว่า algorithm ทำงานอย่างไร แล้วจึงปฏิเสธ algorithm ด้วยเหตุผลที่เหลือซึ่งอ่อนกว่า
    คำกล่าวที่ว่าในคอมพิวเตอร์และ API สมัยใหม่ การรอเป็นเวลาที่ถูกต้องโดยประมาณเป็นไปไม่ได้ ก็ไม่จริงเช่นกัน การ pause ของ GC มีขอบเขต และ monotonic clock ก็ใช้งานได้ จึงเป็นสมมติฐานที่ยอมรับได้
    การวิจารณ์ว่า mechanism การปล่อยอัตโนมัติเปิดเผย race condition ที่อาจเกิดขึ้นในตัวมันเอง กับการวิจารณ์ภายในเป้าหมายและ system model ของ algorithm เป็นคนละเรื่องกัน
    Redlock ถูกใช้อย่างสำเร็จใน use case จำนวนมากมาหลายปีแล้ว และถ้าตั้ง timeout ให้มากกว่าเวลาที่งานเสร็จและมากกว่า arbitrary pause ที่อาจเกิดในระบบปฏิบัติการทั่วไปอย่างมาก ก็ทำให้เกิด race condition ได้ยากมาก
    แน่นอนว่าถ้าตั้ง timeout สำหรับการปล่อยอัตโนมัติไว้สั้นเกินไป และงานอาจใช้เวลายาวเท่านั้นได้ง่าย ๆ นั่นคือข้อผิดพลาดในการออกแบบ แต่ไม่ใช่ปัญหาของ Redlock เอง

    • พูดตรง ๆ ว่าผมไม่ค่อยเข้าใจบทความบล็อกที่ตอบกลับนั้นมาตั้งแต่ก่อนแล้ว บางทีคำถามนี้อาจช่วยหาจุดร่วมได้
      ถ้า timeout ค่อนข้างสั้น (เช่น 1–2 วินาที), งานมักใช้เวลาประมาณ 90% ของ timeout นั้น และงานที่ทำระหว่างถือ RedLock lock เป็นสถานการณ์ที่ ห้ามรันพร้อมกับ ผู้ถือ lock คนอื่น โดยเด็ดขาด คุณจะใช้ RedLock ไหม?
      ผมมองว่าคำตอบที่ถูกต้องคือ “ไม่” เสมอ เพราะมีความเสี่ยงสูงมากที่ lease จะหมดอายุก่อน client ทำงานเสร็จ
      RedLock ไม่สามารถรับประกัน mutual exclusion ได้ในทุกสถานการณ์ ดังนั้นควรทำให้งานเป็น idempotent และกรณีประเภทนี้ควร implement ด้วย optimistic lock จะดีกว่า
    • ขอ link ได้ไหม?

  • กำลังกลับมาเสริมความรู้ระดับ low-level กับ algorithm อยู่ มีหนังสือดี ๆ สำหรับหัวข้อนี้ไหม? หนังสือที่ผู้เขียนเขียนผมมีแล้ว
    อยากลองสร้างอะไรเล่น ๆ แต่ resource ที่เจอมีแต่ระดับของเล่นหรือไม่ก็ซับซ้อนเกินไป

    • แนะนำ System Design Interview I, II ของ Alex Xu
      เลือกหัวข้อสักอย่างแล้วลอง implement จริงได้เลย

  • เคยเขียนบล็อกเรื่อง distributed lock โดยอ้างอิงจากเอกสารนี้: https://medium.com/sahibinden-technology/an-easy-integration...

  • คำอธิบายว่า “lock มี timeout (คือเป็น lease)” ฟังดูแปลก
    ข้อแรก ถ้า client crash ตั้งแต่แรก แม้ไม่มี timed lease, OS หรือ supervisor ก็ควรปล่อย lock ให้ และถึงทั้งคู่จะตาย connection ก็จะขาดในที่สุด แล้วระบบเครือข่ายควรตรวจพบจาก reset, timeout, ไม่มี heartbeat ฯลฯ จากนั้นทำให้ connection เป็นโมฆะและปล่อย lock
    ข้อสอง ถ้าปัญหาคือ client ถือ lock นานเกินไปโดยไม่ crash เพราะ bug ไม่ใช่ว่า supervisor บางตัวควรตรวจจับเรื่องนี้ แล้วฆ่า client ก่อนจะปล่อย lock ให้คนอื่นหรือ?
    ข้อสาม ถ้าจะมี lock ที่มี timeout เพื่อจัดการ corner case แบบนี้ ไม่ควรแจ้งโปรแกรมจริงผ่านวิธีอย่าง exception, signal, termination หรือ? และก่อนปล่อย lock ไม่ควรรอ verify ว่าโปรแกรมได้รับการแจ้งแล้วหรือ?
    แนวคิดที่ยอมให้โปรแกรมยังเดิน control flow ปกติต่อไปทั้งที่ timeout แล้ว ดูเหมือนเป็นรากของปัญหาเอง แต่ไม่เข้าใจว่าทำไมทุกคนถึงมองข้าม ผมพลาดเหตุผลที่ชัดเจนอะไรไปหรือเปล่า?

    • นี่ไม่ใช่ mutex แต่เป็น เวอร์ชัน distributed system ของมัน
      ผู้ที่ invalidate lock ทางฝั่งตัวเองคือ storage service และถ้าไม่มี guarantee เพิ่มเติมที่ Redlock ไม่ได้ให้ client จะตรวจพบปัญหาของตัวเองเองไม่ได้
    • สมมติฐานว่า server จะได้รับ RST หรือ FIN จาก client เสมอนั้นผิด
      ในบางกรณี packet เหล่านี้ถูก drop และ client บนเครื่อง remote ตายไปแล้ว แต่ server ยังมี connection ที่เปิดค้างอยู่ได้
      เสริมไว้ว่า คนที่กด downvote ไม่ใช่ผม

  • ได้ใช้งาน Deno KV ที่ Deno และ Deno Deploy โฮสต์ เพื่อทำ distributed lock
    ภายในใช้ FoundationDB ซึ่งเป็นฐานข้อมูลแบบกระจาย และอินสแตนซ์ Deno ที่รันบนอุปกรณ์โลคัลจะเชื่อมต่อกับ Deno KV เดียวกันเพื่อขอ lock
    ถ้าใช้ PostgreSQL ก็ทำงานได้ด้วย SELECT FOR UPDATE แต่ตัวฐานข้อมูลเองไม่ใช่แบบกระจาย

  • ในปี 2018 เราพิจารณา Redis สำหรับ use case ของเรา แต่สุดท้ายเลือกวิธีแก้ที่ไม่หวือหวา และมันก็ไม่เคยล้มเหลวเลยจริง ๆ
    use case คือการแจกตั๋วที่มีตัวระบุทีละใบจากชุดตั๋วที่มีจำนวนจำกัดของแคมเปญ คล้ายกับที่ Ticketmaster จัดสรรที่นั่งในสถานที่จัดแสดง
    เมื่อมีคำขอเข้ามา ต้องมอบตั๋วที่พร้อมใช้งาน แนบ metadata ของคำขอกับตั๋วที่ถูกจัดสรร แล้วตัดตั๋วนั้นออกจากเป้าหมายของคำขอถัดไป
    ในอดีตเคยมีแคมเปญที่ล้มเหลวจากการจัดสรรเกิน จัดสรรไม่ครบ และจัดสรรซ้ำ ดังนั้นความถูกต้องจึงเป็นเรื่องสำคัญที่สุด
    เราเคยลอง implementation แบบง่าย ๆ ด้วย Redis คือ acquire lock, ตรวจสอบ lock, ทำงาน, release lock แต่ตอนนั้นภาระด้านปฏิบัติการสำหรับเราสูงมาก และโชคดีที่ไม่ได้ไปทางนั้น
    ตัวเลือกสุดท้ายคือ Postgres “distributed lock” ของเราใกล้เคียงกับคำสั่ง UPDATE แบบผสมที่ใช้ความสามารถเฉพาะของ Postgres โดยเปลี่ยนคำขอให้เป็นการดำเนินการแบบเซตชนิดหนึ่ง แล้วให้ฐานข้อมูลส่งคืนเรคอร์ดที่สำเร็จหรือเครื่องหมายว่าล้มเหลว ธุรกรรมแบบ ACID เป็นฝ่ายชนะ
    หลังจากแก้เรื่องความถูกต้องแล้ว เราจึงดูเรื่องสเกลและประสิทธิภาพ เราไม่ต้องการคำขอนับล้านต่อวินาที แต่ก็มีเกณฑ์สำหรับช่วงที่พุ่งสูงฉับพลัน
    เราปรับแต่งอินสแตนซ์ฐานข้อมูลอ่าน/เขียนในคลัสเตอร์ วางแคมเปญที่ใหญ่กว่าหรือมีดีมานด์สูงกว่าไว้บนระบบที่กำหนดอย่างมีกลยุทธ์ และปรับแต่งต่อเนื่อง 2 ปี แต่ไม่มีแคมเปญแจกตั๋วล้มเหลวเลยแม้แต่ครั้งเดียว
    ผมไม่ใช่ผู้เชี่ยวชาญด้านเทคนิค distributed lock แค่โฟกัสที่ปัญหาที่ต้องแก้ ลองสองสามอย่าง แล้วพบวิธีที่เหมาะสมเท่านั้น

    • ถ้าสูงสุด ธุรกรรม atomic สั้น ๆ 50,000 รายการต่อวินาที ใช้แค่ Postgres ก็พอ อันนี้ถูกต้อง
      ธุรกรรม UPDATE ใช้เวลาเพียงไม่กี่ไมโครวินาที จึงสามารถทำให้ปัญหาเป็นแบบรวมศูนย์ได้ และนั่นง่ายกว่า เร็วกว่า และปลอดภัยกว่า
      แต่ตามที่บทความอธิบาย นี่ไม่ใช่ปัญหาแบบกระจาย
      lock ในระบบกระจายต่างจาก mutex ในแอปแบบหลายเธรด และซับซ้อนกว่า เพราะหลายโหนดกับเครือข่ายอาจล้มเหลวอย่างอิสระได้หลากหลายรูปแบบ
      distributed lock จำเป็นเมื่อธุรกรรมอาจใช้เวลาตั้งแต่ไม่กี่วินาทีจนถึงหลายชั่วโมง และเครื่องที่เกี่ยวข้องอาจล้มเหลวขณะถือ lock อยู่
    • จุดสำคัญที่กรณีนี้แสดงให้เห็นคือ สิ่งที่ต้องการไม่ใช่ lock แต่คือ ข้อจำกัด
      ในกรณีนี้ข้อจำกัดคือ “อย่าขายตั๋วเกิน N ใบ” และสำหรับปริมาณทราฟฟิกจริงส่วนใหญ่ของปัญหาแบบนี้ สามารถแก้ได้ด้วยพฤติกรรมธุรกรรมของฐานข้อมูลเชิงสัมพันธ์แบบดั้งเดิม โดยปล่อยให้ฐานข้อมูลจัดการ lock ภายในเอง
      อยากให้เหล่านักพัฒนาไม่รีบกระโจนไปที่ “จะสร้าง distributed lock” เร็วเกินไป แทบจะมีคำตอบที่ดีกว่าเสมอ แต่คำตอบนั้นแตกต่างกันไปในแต่ละแอปพลิเคชัน
    • สุดท้ายคำตอบก็คือ ตรงข้ามกับที่คิด ส่วนใหญ่แล้ว ไม่จำเป็นต้องมี distributed lock :)
    • นี่ดูเหมือนปัญหาที่ parallelize ได้ง่ายจนน่าอาย เพราะ shard ไปยังอินสแตนซ์ต่าง ๆ ตามแต่ละคอนเสิร์ตได้
      อาจเป็นงานที่เหมาะกับของใหม่อย่าง SQLite ของ Cloudflare ก็ได้
    • นี่เป็นวิธีที่ดีที่สุด และจริง ๆ แล้วเป็นวิธีเดียวที่สมเหตุสมผลในการเข้าหาปัญหา
      ที่แรกที่ผมอ่านเรื่องนี้คือที่นี่: https://code.flickr.net/2010/02/08/ticket-servers-distribute...

  • วิศวกรจำนวนมากไม่ได้ใส่ใจกับ ปัญหาความถูกต้อง อย่างจริงจังจนกว่าจะสายเกินไป คล้ายกับเรื่องความปลอดภัย
    แม้จะใส่ใจ ก็มีหลายกรณีที่ไม่ได้ตรวจสอบว่าสิ่งที่ตัวเองทำนั้นถูกต้องหรือไม่
    ตัวอย่างเช่น ในสายงานของผม microservices, actors, processes ส่งข้อความหากันผ่านเครือข่าย แต่กว่า 95% ของ implementation ที่ผมเห็นมี edge case ที่ข้อความอาจหายหรือถูกประมวลผลผิดลำดับได้
    แต่แรงจูงใจไม่ได้ถูกจัดให้สอดคล้องพอที่จะไปแก้ปัญหานี้ โครงสร้างค่าตอบแทนของผู้บริหารและวิศวกรไม่ตรงกับผลลัพธ์ที่ดีที่สุดต่อทั้งลูกค้าและผู้ถือหุ้น

    • ไมโครเซอร์วิส เองก็มักเป็นอาการของปัญหานี้
      ผู้คนอยากใส่ boundary ของเครือข่ายคั่นระหว่างการเรียกฟังก์ชันโดยไม่มีเหตุผลมากนัก จากนั้นก็สร้าง HTTP server และ client รวมถึงการ serialize/deserialize JSON อย่างไม่รู้จบเพื่อการเรียกฟังก์ชันนั้น ถ้าโชคดีก็ใช้ gRPC แล้วพยายาม implement สิ่งอย่าง distributed transaction ข้าม boundary เครือข่ายนั้นขึ้นมาใหม่
      สุดท้ายก็มีแต่งานยุ่ง ๆ ในการจัดการ “ปฏิสัมพันธ์ชวนขนลุกที่เกิดขึ้นจากระยะไกล” ซึ่งหลีกเลี่ยงไม่ได้
    • หากจะแก้ ต้องเริ่มจากการวัดและมอนิเตอร์ก่อน จากนั้นตั้ง service level objectives ที่สะท้อนประสบการณ์ลูกค้า
      ทีมผลิตภัณฑ์และทีมวิศวกรรมต้องเห็นพ้องกันเรื่องนี้ และถ้าละเมิด SLO ก็ต้องย้ายโฟกัสไปที่เสถียรภาพของระบบ
      การโน้มน้าวทุกคนเป็นเรื่องยาก จึงต้องมีภาวะผู้นำที่ดี
      เมื่อบั๊กเริ่มโผล่ ฟีเจอร์ใหม่ช้าหรือแทบไม่มี และลูกค้าเริ่มจากไป เหตุผลที่ต้องทำให้คุณภาพเป็นส่วนหนึ่งของกระบวนการจะชัดเจนมาก
      ผู้นำที่มีวุฒิภาวะจะขยับนำหน้าขั้นนั้นให้เร็วที่สุดเท่าที่ทำได้
    • ปัญหาประเภทนั้นอาจทำให้ผู้บริสุทธิ์ถูกส่งเข้าคุกหรือถึงตายได้
      [0] https://en.wikipedia.org/wiki/British_Post_Office_scandal
    • ผมคิดว่ามีการจัดแรงจูงใจให้สอดคล้องกันอยู่บ้าง edge case แบบนี้จัดการยาก จึงมีแนวโน้มว่านักพัฒนาต้องรับ support ticket จำนวนมาก ซึ่งไม่ดีต่อใครเลย
      แต่ผมก็ยังไม่ค่อยเห็นวิธีโน้มน้าวผู้จัดการของเมื่อวานให้ยอมให้เวลาสร้างมันให้ถูกต้อง

  • แบบนี้ทำให้งานซับซ้อนเกินไป
    ถ้ามีสิ่งที่บทความเรียกว่า fencing token ก็ไม่จำเป็นต้องมี lock
    token ไม่จำเป็นต้องเพิ่มขึ้นแบบ monotonic ด้วยซ้ำ แค่เป็นค่าที่ไม่ซ้ำกันแบบ passive ที่ client กับ storage มีร่วมกันก็พอ
    ถ้าเรียกว่า version token จะเป็นค่าที่เพิ่มขึ้นแบบ monotonic ก็ได้ หรือ UUID ที่มักสร้างง่ายกว่าก็ใช้ได้เช่นกัน ในเชิงเทคนิค hash ของข้อมูลทั้งหมดใน storage ก็เป็นไปได้ แต่ไม่ค่อยใช้ได้จริง
    ลำดับการทำงานเป็นแบบนี้: client ดึง version token ปัจจุบันกับข้อมูลที่จะแก้ไขมาจาก storage พร้อมกัน และ storage อ่านข้อมูลกับ token แบบ atomic เพื่อรับประกันว่า token นั้นเป็นของข้อมูลเวอร์ชันดังกล่าว
    จากนั้น client ส่ง version token กลับไปพร้อมกับการเปลี่ยนแปลง และ storage จะยอมรับการเปลี่ยนแปลงเฉพาะเมื่อ token ปัจจุบันตรงกับ token ที่ส่งมาเท่านั้น พร้อมทั้งสร้าง version token ใหม่แบบ atomic
    อาจนำ lock มาใช้ด้วยเหตุผลอื่นได้ แต่ในระบบกระจายตัว มันควรเป็นอิสระจากความถูกต้องสมบูรณ์ของ storage
    ผมไม่ค่อยชอบคำว่า “lock” ด้วย เพราะมันเป็นสิ่งชั่วคราวและไม่ได้รับประกัน คำว่า lease หรือการจองอาจสื่อความหมายได้ดีกว่า

    • สิ่งที่อธิบายอยู่คือ compare-and-swap (CAS) และเป็นทางออกที่ดี
      เป็นวิธีผลักความซับซ้อนไปไว้ฝั่งฐานข้อมูล แต่ต้องจำไว้ว่าตรงนี้พูดถึง distributed lock
      ถ้าเป็นฐานข้อมูลเดียว เรื่องจะเรียบง่ายจนกว่าฐานข้อมูลจะ crash แล้วไม่รู้ว่า CAS write ใดถูกนำไปใช้จริงหรือไม่
      ในระบบขนาดใหญ่ที่ต้องการ high availability และการสำรองข้ามหลาย data center วิธีนี้ก็อาจพังได้จากสถานการณ์รอบ ๆ node failure จึงค่อนข้างซับซ้อน
      โดยทั่วไปจะใช้ transaction log แบบ Paxos อย่าคิดว่าระบบกระจายตัวมีทางออกง่าย ๆ มันน่าปวดหัวเสมอ
    • ตีความปัญหาผิด และกำลังเสนอทางออกให้กับอีกปัญหาหนึ่ง
    • สิ่งนี้รู้จักกันในชื่อ optimistic locking แต่ผมคงไม่เรียกว่าเป็นกลไก distributed lock
    • คำอธิบายนี้พลาดเหตุผลแรกในบทความที่ใช้ lock
      จากมุมมองด้านประสิทธิภาพ การจับ lock ช่วยหลีกเลี่ยงการทำงานเดียวกันซ้ำโดยไม่จำเป็นได้ เช่น การคำนวณที่มีต้นทุนสูง
      ถ้า lock ล้มเหลวแล้วสอง node ทำงานเดียวกัน แต่ผลลัพธ์เป็นแค่ต้นทุนเพิ่มขึ้นเล็กน้อยหรือการแจ้งเตือนอีเมลซ้ำแบบเดียวกัน ก็อาจเป็นเรื่องเล็กน้อย
      แต่ผมมองว่าการที่หลาย node ทำงานเดียวกันนั้นแย่กว่าที่เขียนในตัวอย่างมาก เพราะมันอาจขัดขวางการประมวลผลแบบกระจายตัวที่ขยายได้เอง
    • ถ้าไม่ใช้ token ที่เพิ่มขึ้นแบบ monotonic จะไม่นำไปสู่ สถานะไม่สอดคล้องกัน หรือ?
      สมมติว่าระบบ storage มีสอง node และมี process แบบ read-modify-write สองตัวกำลังทำงานอยู่ process 1 และ 2 ต่างก็ได้ token แรกเป็น abc
      process 1 commit ทำให้ token เปลี่ยนเป็น cde และการเปลี่ยนแปลงถูก stream ไปยัง node 2 แต่เพราะ network latency จึงไปถึง node 2 ช้า
      ระหว่างนั้น process 2 commit ไปยัง node 2 ด้วย token abc node 2 ยังไม่ได้รับ message จาก node 1 จึงยอมรับการเปลี่ยนแปลง และระบบก็เข้าสู่สถานะไม่สอดคล้องกัน
      ถ้ามี fencing token ที่เพิ่มขึ้นแบบ monotonic เรื่องแบบนี้จะไม่เกิดขึ้น เพราะข้อกำหนดนั้นบังคับให้ node ต่าง ๆ ต้องตกลงกันเรื่องลำดับงานทั้งหมดก่อนจะให้ token