ผ่านไป 50 ปี Two-Phase Locking ยังเป็นทางเลือกที่ดีที่สุดหรือไม่?

 (concurrencyfreaks.blogspot.com)
1 คะแนน โดย GN⁺ 2023-10-01 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • Two-Phase Locking (2PL) ที่เผยแพร่ในปี 1976 ให้ Opacity ซึ่งเป็นคุณสมบัติที่เข้มกว่าความสามารถในการจัดลำดับแบบอนุกรม แต่แม้จะผ่านมาราว 50 ปีแล้ว ก็ยังมีข้อจำกัดด้านการขยายตัวของการอ่านและการรับประกันความคืบหน้า
  • ด้วยกฎง่าย ๆ ในการได้มาและปล่อยล็อก ทำให้จัดการทรานแซกชันที่ครอบคลุมหลายเรคคอร์ดพร้อมมอบ ระดับการแยกที่เข้มงวด จึงยังถูกใช้อย่างแพร่หลายในฐานข้อมูลทรานแซกชันเชิงพาณิชย์และโครงสร้างข้อมูลแบบ concurrent
  • 2PL แบบดั้งเดิมอาจทำให้แม้แต่การอ่านด้วยกันเองก็ชนกันเพราะใช้ล็อกแบบ mutual exclusion และแม้ใช้ reader-writer lock ก็ยังเกิด การแข่งขันของ read-indicator ในจุดที่มีการอ่านหนาแน่น เช่น รากของ binary search tree
  • 2PLSF กระจายตัวบ่งชี้ของ reader แต่ละรายไปตาม cache line เพื่อลดการแข่งขันในการได้ read lock และใช้ fetch_and_add() ของ atomic counter ส่วนกลางเฉพาะกับทรานแซกชันที่เกิดการชนกันเท่านั้น
  • รูปแบบดัดแปลงของ 2PL เช่น No-Wait, Deadlock-detection, Wait-Or-Die ยังทิ้งปัญหา live-lock หรือ scalability ไว้ ส่วน 2PLSF เป็นรูปแบบปรับปรุงที่มุ่งทั้งการขยายตัวของการอ่านและ ทรานแซกชันแบบ starvation-free

เหตุผลที่ 2PL ยังสำคัญ

  • Two-Phase Locking (2PL) เป็นหนึ่งในกลไกควบคุม concurrency แบบทั่วไปชุดแรก ๆ ที่ให้ความสามารถในการจัดลำดับแบบอนุกรม (Serializability) และในทางปฏิบัติยังให้ระดับการแยกที่เข้มกว่าอย่าง Opacity
  • 2PL ถูกเผยแพร่ในปี 1976 ผ่าน บทความของ Jim Gray และผู้ร่วมงาน และเป็นไปได้ว่าแนวคิดนี้มีมาก่อนหน้านั้น จึงถือเป็นเทคนิคที่มีอายุเกือบ 50 ปี
  • การควบคุม concurrency แบบทั่วไปหมายถึงอัลกอริทึมที่ทำให้ทรานแซกชันซึ่งมีความหมายแบบ all-or-nothing ทำงานกับรายการข้อมูลหลายรายการ เช่น อ็อบเจ็กต์ เรคคอร์ด หรือทูเพิลได้
  • จุดแข็งของ 2PL อยู่ที่ความเรียบง่ายและการแยกที่เข้มงวด
    • ก่อนอ่านหรือเขียนเรคคอร์ด จะต้องได้ล็อกที่ปกป้องเรคคอร์ดนั้นก่อน
    • คงล็อกที่ได้มาไว้จนกว่าทรานแซกชันจะจบ เพื่อสร้างมุมมองที่สอดคล้องกัน

การแยกที่เกิดจากกฎง่าย ๆ

  • ใน 2PL จะได้ล็อกในแต่ละครั้งที่เข้าถึงระหว่างทรานแซกชัน และปล่อยล็อกทั้งหมดเมื่อทรานแซกชันสิ้นสุด ซึ่งเป็นจุดที่รู้แล้วว่าจะไม่มีการเข้าถึงเพิ่มเติม
  • ณ จุดสิ้นสุด จะถือครองล็อกของข้อมูลที่เข้าถึงทั้งหมดอยู่ จึงเกิด จุดทำให้เป็นเส้นตรง (linearization point) สำหรับทรานแซกชันนั้น
  • เมื่อ 50 ปีก่อน นักวิจัยฐานข้อมูลจำนวนมากมองว่าสามารถปล่อยล็อกทันทีหลังเข้าถึงเรคคอร์ดเสร็จได้ แต่การควบคุม concurrency แบบนั้นไม่สามารถจัดลำดับแบบอนุกรมได้
  • ฐานข้อมูลทรานแซกชันเชิงพาณิชย์ที่เป็นที่รู้จักใช้ 2PL หรือ T/O ร่วมกับ MVCC
  • ในสายโครงสร้างข้อมูลแบบ concurrent นั้น linearizability แทบเป็นมาตรฐาน และหากต้องเขียนลงหลายโหนดอย่างสอดคล้องกัน โดยทั่วไปก็ต้องใช้แนวทางคล้าย 2PL สำหรับการเข้าถึงแบบเขียน
    • ข้อยกเว้นคือโครงสร้างข้อมูลแบบ lock-free แต่มีการเน้นว่าการทำ lock-free ให้ถูกต้องนั้นยาก

คอขวดของ 2PL: การขยายตัวของการอ่านและ live-lock

  • จุดอ่อนใหญ่ของ 2PL คือ การขยายตัวของการอ่านไม่เพียงพอ และ การรับประกันความคืบหน้าแบบ live-lock
  • 2PL แบบคลาสสิกออกแบบบนพื้นฐานของล็อกแบบ mutual exclusion ดังนั้นแม้สองเธรดจะอ่านเรคคอร์ดเดียวกันเท่านั้นก็ยังชนกัน และหนึ่งหรือทั้งสองฝ่ายอาจต้อง abort แล้วเริ่มใหม่
  • หากเปลี่ยนเป็น reader-writer lock จะลดการชนกันระหว่างการอ่านด้วยกัน แต่ต้นทุนของล็อกและการใช้หน่วยความจำจะเพิ่มขึ้น
    • ล็อกแบบ mutual exclusion สามารถใช้ 1 บิต แทนสถานะล็อก/ปลดล็อกได้
    • reader-writer lock ต้องมี counter สำหรับนับจำนวน reader ที่ถือครองล็อกในโหมดอ่านอยู่ในปัจจุบัน นอกเหนือจากบิตนี้
    • ตัวอย่างเช่น counter 7 บิตสามารถแทนเธรดได้สูงสุด 128 เธรด และแต่ละล็อกอาจใช้พื้นที่ 1 ไบต์
    • หากฐานข้อมูลมีเรคคอร์ดหลายพันล้านรายการ แค่ล็อกอย่างเดียวก็ต้องใช้หลายพันล้านไบต์
  • ปัญหาที่ใหญ่กว่าคือการแข่งขันบน counter
    • ใน workload แบบ read-non-disjoint การอ่านจำนวนมากจะกระจุกตัวอยู่ที่ข้อมูลเดียวกัน
    • โหนดรากของ binary search tree เป็นตัวอย่างสำคัญที่ทุก operation ต้องอ่านก่อนลงไปยังโหนดลูก
    • ใน 2PL ทุกครั้งที่เข้าถึงรากต้องได้ล็อก และแม้ใช้ reader-writer lock ก็จะเกิดการแข่งขันรุนแรงที่ล็อกของโหนดราก

แนวทางเดิมและ read-indicator ที่ขยายตัวได้

  • TLRW เป็นแนวทางที่ Dave Dice และ Nir Shavit เสนอใน SPAA 2010 ใช้ reader-writer lock เพื่อเพิ่มประสิทธิภาพเหนือ mutual exclusion lock แต่ยังไม่เร็วเท่าการควบคุม concurrency แบบ optimistic
  • หากนำการใช้งานที่แต่ละการเข้าถึงแบบอ่านต้องแข่งขันบนตัวแปรเดียวของ reader-writer lock คล้าย TLRW ไปใช้กับ Rank-based Relaxed AVL binary search tree การขยายตัวจะราบไปแทบทั้งหมด ไม่ว่าจะเป็นทรานแซกชันแบบเขียนหรือแบบอ่านเป็นหลัก
  • การแข่งขันของ read-indicator สามารถบรรเทาได้ด้วย read-indicator ที่ขยายตัวได้
    • วิธีที่นิยมคือ reader-writer lock ที่ reader แต่ละรายทำเครื่องหมายการมาถึงและการออกจากล็อกไว้บน cache line แยกกัน
    • การได้ read lock จะไม่เกิดการแข่งขัน
    • เธรดที่ต้องการได้ write lock ต้องสแกน cache line ทั้งหมดเพื่อตรวจสอบว่าอนุญาตหรือไม่ ทำให้ต้นทุนในการได้ write lock สูงขึ้น
  • NUMA Aware reader-writer locks กล่าวถึงอัลกอริทึม reader-writer lock ที่ใช้เทคนิคนี้
    • ในบรรดาอัลกอริทึม reader-writer lock สามแบบ มีสองแบบที่ขยายตัวได้สูง แต่ไม่ใช่ starvation-free

การออกแบบ reader-writer lock ของ 2PLSF

  • Two-Phase Locking Starvation-Free (2PLSF) คือการควบคุม concurrency ที่ใช้งานด้วย reader-writer lock ซึ่งขยายตัวได้ดีในการได้ read lock และมีคุณสมบัติเพิ่มเติม
  • reader-writer lock ของ 2PLSF จอง 1 บิตต่อเธรดสำหรับ read-lock
    • บิตเหล่านี้ถูกวางไว้ใน cache line ของตัวเอง
    • ถูกวางร่วมกับบิต read-indicator ของล็อกที่อยู่ใกล้เคียง
  • เช่นเดียวกับบทความ NUMA-aware reader-writer lock ต้นทุนถูกย้ายไปอยู่ที่การได้ write lock
    • write lock ต้องสแกน cache line หลายชุด
    • ไม่ใช่วิธีแก้ปัญหาแบบวิเศษ แต่เป็น trade-off
  • เหตุผลที่ trade-off นี้มีประโยชน์คือ workload ส่วนใหญ่ออกไปทาง read-heavy และแม้แต่ workload ที่ write-intensive ก็ยังใช้เวลามากกับการเข้าถึงแบบอ่าน เช่น ขั้นตอนค้นหาเรคคอร์ด
  • เมื่อใช้ reader-writer lock ที่ปรับปรุงแล้ว 2PL จะขยายตัวได้แม้ใน workload แบบ read-non-disjoint แต่ปัญหา live-lock ต้องแก้แยกต่างหาก

ปัญหาการรับประกันความคืบหน้าที่ยังเหลือในรูปแบบดัดแปลงของ 2PL

  • 2PL แบบคลาสสิกมีรูปแบบดัดแปลงหลัก ๆ ตามวิธีจัดการการแข่งขัน เช่น No-Wait, Deadlock-detection และ Wait-Or-Die

  • No-Wait

    • เมื่อเกิดการชนกัน จะ abort ทรานแซกชันของตัวเองหรือของอีกฝ่ายแล้วลองใหม่
    • การลองใหม่อาจทำทันที หรือทำภายหลังด้วยวิธี exponential backoff
    • หากทรานแซกชันที่ต้องการแก้ไข B หลัง A และทรานแซกชันที่ต้องการแก้ไข A หลัง B ชนกันต่อเนื่อง ทั้งสองอาจวน abort-restart โดยไม่มีใคร commit ได้ จึงมี live-lock progress

  • Deadlock-detection

    • รักษารายชื่อเธรดที่รออยู่บนล็อก และตรวจจับวงจรหรือ deadlock
    • ใน reader-writer lock reader แต่ละรายต้องมีรายการของตัวเอง และยังต้องมี mutual exclusion lock เพื่อปกป้องแต่ละรายการด้วย
    • เมื่อต้องจับล็อกในโหมด read-lock ต้องสแกนรายการของ reader ทั้งหมด จึงมีต้นทุนสูง
    • ในทางทฤษฎีอาจทำให้เป็น starvation-free ได้ แต่จะต้องใช้ starvation-free lock และขัดกับเป้าหมายตรงที่ไม่มี reader-writer lock แบบ starvation-free ที่ขยายตัวได้สูงและเผยแพร่ต่อสาธารณะ
    • หากมีรายการต่อ reader การใช้หน่วยความจำก็อาจสูงขึ้นด้วย

  • Wait-Or-Die

    • กำหนดลำดับให้ทุกทรานแซกชัน และเมื่อเกิดการชนกันของล็อก จะเปรียบเทียบ timestamp ของทรานแซกชันกับ timestamp ของเจ้าของล็อกเพื่อตัดสินใจว่าจะรอหรือ abort
    • ใน mutual exclusion lock สามารถเก็บเจ้าของไว้ภายในล็อกด้วยตัวระบุเธรดแบบไม่ซ้ำกัน จึงทำงานได้ดี
    • หากจะใช้วิธีเดียวกันกับ reader-writer lock ต้องมี thread-id ต่อ reader
    • หากรองรับ 256 เธรด จะต้องใช้ 8 บิต × 256 = 256 ไบต์ ต่อ reader-writer lock

คอขวดของ atomic counter ส่วนกลางและความแตกต่างของ 2PLSF

  • อุปสรรคที่ใหญ่กว่าของ Wait-Or-Die คือทุกทรานแซกชันต้องมี transaction ID ที่ไม่ซ้ำกัน
    • ตัวอย่างเช่น สามารถรับหมายเลขจากตัวแปร atomic ส่วนกลางด้วย fetch_and_add() เพื่อสร้างลำดับได้
  • ใน CPU สมัยใหม่ส่วนใหญ่ เป็นเรื่องยากที่จะทำ fetch_and_add() ได้เกิน 40 ล้านครั้งต่อวินาทีบนตัวแปร atomic ที่มีการแข่งขัน
    • อาจดูมากเมื่อเทียบกับธุรกรรมของ Visa ราว 660 ล้านรายการต่อวัน
    • แต่อาจไม่มากพอสำหรับ in-memory DBMS หรือโครงสร้างข้อมูลแบบ concurrent
    • บนเครื่องทดสอบเครื่องหนึ่ง ทำได้ยากที่จะเกิน 20 ล้าน fetch_and_add() ต่อวินาที
  • fetch_and_add() นี้จำเป็นสำหรับทุกทรานแซกชัน รวมถึงทรานแซกชันแบบอ่าน ไม่ใช่เฉพาะทรานแซกชันแบบเขียน จึงจำกัดการขยายตัว
  • TL2 ทำการอ่านแบบ optimistic โดยที่ทรานแซกชันแบบอ่านไม่ต้องทำ atomic fetch_and_add()
    • เมื่อพิจารณาทรานแซกชันแบบอ่าน อาจขยายไปถึงหลายร้อยล้าน tps ได้
    • ในทางกลับกัน 2PL ที่อิง Wait-Or-Die ไม่สามารถเกิน 40M tps/sec ได้
  • 2PLSF จะจัดลำดับเฉพาะทรานแซกชันที่เข้าไปอยู่ในการชนกัน
    • จำนวนทรานแซกชันที่ทำ fetch_and_add() บนตัวแปร atomic ส่วนกลางจึงลดลง
    • ทรานแซกชันที่ไม่เกิดการชนกันจะไม่ติดเพดาน 40M tps
    • ตัวอย่างเช่น อาจมี 200M tps ที่รันโดยไม่มีการชนกัน และมีเฉพาะ 40M tps ที่กำลังชนกันซึ่งติดข้อจำกัดของ fetch_and_add()
    • อัลกอริทึมให้ starvation-freedom

แหล่งข้อมูลและการประเมินสุดท้าย

  • แม้จะไม่ได้ลงรายละเอียดอัลกอริทึม 2PLSF เอง แต่ถูกประเมินว่าค่อนข้างเรียบง่ายสำหรับอัลกอริทึมแบบ starvation-free
  • มีบทความและซอร์สโค้ดเป็นเอกสารอ้างอิง
  • 2PLSF ยังเชื่อมโยงกับ บทความ ACM และสรุปว่าเป็นอัลกอริทึมที่สร้างโดย Pedro Ramalhete, Andreia, Pascal Felber
  • เป้าหมายของ 2PLSF ใกล้เคียงกับคุณสมบัติที่ 2PL ควรมีมาตั้งแต่ต้น
    • ขยายตัวได้ดีแม้ในสถานการณ์ read-non-disjoint ที่การอ่านทับซ้อนกัน
    • ให้ ทรานแซกชันแบบ starvation-free ซึ่งเป็นรูปแบบสูงสุดของ blocking progress
    • สามารถขยายตัวได้แม้ในบางสถานการณ์ที่มีการชนกัน
  • 2PLSF ไม่สมบูรณ์แบบ แต่ถูกประเมินว่าดีกว่า TL2 ในด้านการแก้การชนกัน และความต่างจาก 2PL แบบเดิมถูกเปรียบว่าเหมือนความต่างระหว่างอีเต้อกับเครื่องเจาะคอนกรีต

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

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

 
GN⁺ 2023-10-01
ความคิดเห็นจาก Hacker News
  • ผมยังเป็นมือใหม่กับหัวข้อนี้ แต่ก็สนใจ และอยากให้มี โซลูชันด้าน consistency ที่นำไปใช้งานได้ง่าย
    ผมสงสัยว่าในสถาปัตยกรรมไมโครเซอร์วิสแบบกระจาย แนวปฏิบัติที่ดีที่สุดของอุตสาหกรรมคืออะไร หากต้องการซิงก์หรือทำให้ data store หลายตัวคง “สอดคล้องกัน”
    เมื่อไม่กี่วันก่อนผมลองแก้ปัญหาความไม่สอดคล้องด้วย “settled timestamp” ซึ่งค่อนข้างคล้ายวิธี multi-version ที่ถือว่าเป็นการบันทึก/คอมมิตที่ถูกต้องเมื่อเวลาผ่านไปโดยไม่มีรายงานข้อผิดพลาด เหมือนกับว่าเฟสที่สองของ two-phase commit คือเวลา
    วิธีนี้คือคอยเฝ้าดูนาฬิกาของเซิร์ฟเวอร์อื่น ๆ และถ้าไม่อัปเดตก็จะไม่เชื่อถือ settled timestamp ของเซิร์ฟเวอร์นั้น จุดประสงค์คือขยาย consistency ไปยังเซิร์ฟเวอร์จำนวนมากได้ เพราะไม่ต้องรอคำตอบทุกครั้งที่มีการอัปเดต แค่รอช่วง timestamp ถัดไปก็พอ
    ผมเขียนโค้ด Python แบบ multi-thread/multi-processing เพื่อทดสอบ ความไม่กำหนดแน่นอน ด้วย 10 เธรดที่ส่งอัปเดตแบบสุ่มไปมาหากัน: https://replit.com/@Chronological/InconsistencySimulation#ma...
    ในการจำลองนี้ การอ่านคือค่าต่ำสุดของ timestamp ทั้งหมดที่ทุกเซิร์ฟเวอร์รายงาน และเมื่อถามค่า counter จากแต่ละเธรดหลังผ่านไป 10 วินาที บางครั้งทุกเธรดก็ให้ค่าเดียวกัน แต่ค่อนข้างบ่อยที่เกิดสถานะ split-brain
    ผมทราบว่าในระบบกระจาย wall clock timestamp ไม่เหมาะสำหรับการกำหนดลำดับ และควรใช้ logical clock หรือ vector clock
    ถ้าทำให้การจำลองรายงานตัวเลขเดียวกันได้ไม่ว่าเวลาใดก็คงดี Bloomlang พยายามแก้ปัญหาใน eventual consistency ที่ค่าที่มาถึงช้าส่งผลต่อผลลัพธ์ ทำให้ไม่สามารถ linearizable ได้
    โดยเฉพาะผมสนใจการ scale โดยยังรักษา consistency ไว้ แต่ดูเหมือนเป็นปัญหาที่ค่อนข้างยาก
    • แนวปฏิบัติที่ดีที่สุดของอุตสาหกรรมคืออย่าใช้ สถาปัตยกรรมไมโครเซอร์วิสแบบกระจาย
    • แนวคิดหลักของระบบกระจายคือการมี central write-order journal ที่แต่ละ node เล่นซ้ำ
      หลายระบบเขียนลง central journal ตามลำดับ และ journal รับคำขอเหมือน key-value store จากนั้น journal นั้นถูก replicate ไปยังทุก node และ node ต่าง ๆ อ่าน journal เพื่อทำตรรกะซับซ้อนตามที่ร้องขอ
    • ควรประเมินใหม่ว่าจำเป็นต้องมีทั้ง (a) data store แบบกระจาย และ (b) consistency แบบ synchronous จริงหรือไม่ ถ้ายอมตัดทิ้งอย่างใดอย่างหนึ่ง ก็จะง่ายขึ้นมาก
    • ผมคิดว่าภายใน 5 ปี TigerBeetle DB จะกลายเป็นมาตรฐานอุตสาหกรรมสำหรับฐานข้อมูลแบบกระจายที่ consistent, throughput สูง และทนต่อความล้มเหลว
    • ลองดู Raft protocol โดยทั่วไปมาตรฐานคือไม่พยายามรวมเข้าด้วยกันโดยตรงในชั้นโปรโตคอล แต่ใช้ consistent store อย่าง etcd ที่ implement Raft สำหรับการประสานงาน/ข้อมูลที่ต้อง serializable
      Kubernetes ใช้ etcd ดังนั้นในฐานะ key-value store ที่มี strong consistency จึง scale ได้ค่อนข้างดี
      คุณพูดว่า “หลาย data store” ผมจึงสมมติว่ามีข้อมูลหลากชนิด และตัวเลือกอย่าง CockroachDB ไม่น่าจะใช่
      ถ้าเป็นมือใหม่ การทำเองนั้นเสี่ยง https://aphyr.com/ เป็นเหมือนมาตรฐานอ้างอิงด้านการทดสอบ และยอดเยี่ยมสำหรับการศึกษา สามารถใช้ Jepsen ทดสอบระบบกระจายได้ แต่ใช้ data store ที่ Kyle แสดงให้เห็นว่าแข็งแกร่งแล้วน่าจะดีกว่า
  • ผมสงสัยว่าแนวทางใหม่นี้เทียบกับ Serializable Snapshot Isolation (SSI) อย่างไร: https://wiki.postgresql.org/wiki/SSI
    ผมไม่ได้คุ้นเคยกับเทคนิคเหล่านี้มากนัก แต่ตอนเรียนฐานข้อมูล SSI ถูกนำเสนอว่าเป็น two-phase locking ที่ “ดีกว่า” ในอนาคต เลยสงสัยว่า SSI ต่างจาก 2PLSF อย่างไร และทำไมถึงไม่ได้ถูกกล่าวถึงที่นี่
    • ผมกำลังสร้าง memory model สำหรับแพลตฟอร์มใหม่ และแทบทั้งหมดออกแบบรอบ ๆ copy-on-write, snapshot และ SSI
      แต่สำหรับผลกระทบแบบกระจาย ก็ยังต้องใช้ lock, two-phase transaction ฯลฯ อยู่ โดยส่วนตัวผมมองว่าเป็นฟีเจอร์ที่เสริมกันมากกว่าจะเป็นสิ่งทดแทนกัน
  • อัลกอริทึมการล็อกนั้นยอดเยี่ยม แต่ก่อนนำไปใช้ สิ่งสำคัญคือต้องถอยออกมาคิดก่อนว่าเราจำเป็นต้องให้เธรดจำนวนมากแย่งทรัพยากรเดียวกันจริง ๆ หรือไม่
    ถ้าเป็นโครงสร้างข้อมูลในหน่วยความจำก็เป็นเรื่องธรรมชาติ แต่ถ้าจัดการกับฐานข้อมูลภายนอกหรือทรัพยากรภายนอกที่ใช้ร่วมกันอื่น ๆ อาจมีวิธีที่ดีกว่า
    บ่อยครั้งเราสามารถ batch คำขอ เพื่อเข้าถึงทรัพยากรภายนอกด้วย concurrency ที่ต่ำลงและ payload ที่ใหญ่ขึ้น หากทรัพยากรนั้นจัดการ batch ได้ดี concurrency และ lock ที่ต้องใช้ก็จะลดลงมาก
    เช่นถ้าใช้ Postgres จำนวน connection จะลดลง และอาจไม่ต้องเพิ่ม PgBouncer ที่ทำให้ความซับซ้อนสูงขึ้น
    อย่างไรก็ตาม การ batch คำขอมักไม่ค่อยเข้ากับภาษาโปรแกรมส่วนใหญ่ ภาษาอย่าง Go ที่มี channel หรือ Elixir ที่มี process ซึ่งเหมาะกับ concurrency สูงอาจทำได้ดี แต่ในภาษาที่จัดการทุกอย่างด้วย thread อาจกลายเป็นเรื่องเจ็บปวด
  • บทความวิจัย 2PLSF ที่ผู้เขียนอ้างว่า 2PL ควรเป็นแบบนี้ตั้งแต่แรก: https://zenodo.org/record/7886718
  • จำเป็นมากที่ต้องมีนโยบายใหม่บังคับให้ทุกลิงก์ที่ขึ้นบน HN เป็น ลิงก์ HTTPS
    • ทำไมต้องเป็นแบบนั้น? มีเว็บเก่า ๆ ที่มีประโยชน์จำนวนมากซึ่งยังทำงานได้ดีผ่าน HTTP ถ้าหมายถึงกรณีที่เว็บรองรับ HTTPS แต่มีคนโพสต์ลิงก์ HTTP อันนั้นผมเห็นด้วย
    • ผมสงสัยว่าถ้าเข้า ลิงก์ HTTP แทน HTTPS ในเว็บที่โต้ตอบแบบอ่านอย่างเดียวล้วน ๆ จะเกิดผลอะไร เป็นปัญหาด้านความปลอดภัย หรือปัญหาด้านความเป็นส่วนตัว?
    • ใช้ Firefox ใน โหมด HTTPS-Only ก็ได้: https://support.mozilla.org/en-US/kb/https-only-prefs
      สำหรับเว็บที่อัปเกรดเป็น HTTPS ไม่ได้ จะมีคำเตือนขึ้น และเว็บที่รองรับทั้งสองแบบจะพาไปยังเวอร์ชัน HTTPS ทันที
    • หลังอ่านบทความเกี่ยวกับอัลกอริทึม concurrency แล้ว สิ่งที่นึกขึ้นมาได้คือข้อสังเกตที่ไม่เกี่ยวข้องนี้หรือ?
      และถ้าลิงก์ HTTP นั้นเกี่ยวกับอัลกอริทึม concurrency ที่ดี ผมก็ยังจะอ่านอยู่ดี
    • ยังมี เว็บไซต์ที่รองรับเฉพาะ HTTP เหลืออยู่บางแห่ง
  • ใน Wait-Or-Die จำเป็นต้องใช้ fetch_and_add จริง ๆ เพื่อให้ได้ transaction ID หรือ? ผมยังสงสัยด้วยซ้ำว่าจำเป็นต้องมี transaction ID ตั้งแต่แรกหรือไม่

เป้าหมายฟังดูเหมือนการกำหนดลำดับที่แม้จะเป็นลำดับตามอำเภอใจแต่สอดคล้องกันระหว่างทรานแซกชันที่กำลังทำงานอยู่ เพื่อให้เมื่่อเกิดการชนกัน แต่ละฝ่ายตกลงกันได้ว่าใครจะรอและใครจะถูกฆ่า ถ้าอย่างนั้นใช้ thread ID ไม่ได้หรือ?
เลขสุ่มก็น่าจะใช้ได้เหมือนกัน ถ้าถือว่าการเสมอกันคือ “ตาย” กรณีแย่ที่สุดก็แค่ทรานแซกชันทั้งสองฝั่งถูกยุติโดยไม่จำเป็น แล้วลองใหม่ด้วยเลขสุ่มใหม่
แม้ไม่ได้กล่าวไว้ แต่ดูเหมือนต้องการให้ทรานแซกชันที่เก่ากว่ามีลำดับความสำคัญ เพื่อไม่ให้ทรานแซกชันที่รันนานอดอยากเพราะทรานแซกชันสั้น ๆ ตัวอย่างเช่น ถ้าทรานแซกชันยาวหนึ่งรายการชนกับทรานแซกชันสั้นโดยเฉลี่ยสามรายการ และผู้ชนะในการชนแต่ละครั้งแทบจะเป็นแบบสุ่ม โอกาสที่ทรานแซกชันยาวจะชนะทั้งสามครั้งแล้ว commit ได้มีเพียง 1/8 เท่านั้น
แต่เพื่อป้องกัน starvation ก็ไม่จำเป็นต้องให้ทรานแซกชันที่เก่ากว่ามีลำดับความสำคัญทุกครั้ง แค่ในกรณีส่วนใหญ่ก็พอ โดยเฉพาะเมื่อเก่ากว่าแค่นิดเดียว
ดังนั้นสิ่งที่คล้าย timestamp หรือ cycle counter อาจทำงานได้ดี แม้จะมี clock skew ระหว่างเธรดหรือความไม่แม่นยำอื่น ๆ ก็ตาม การเสมอกันอาจตัดสินด้วย thread ID หรือจะให้ทั้งสองฝั่งยุติไปเลยก็ได้

  • แทนที่จะใช้ thread ID ผมคงใช้ ULID: https://github.com/ulid/spec
    เหมาะกับกรณีแบบนี้และอีกหลายกรณี
  • เป็น paper ที่ยอดเยี่ยมซึ่งให้กรอบในการเปรียบเทียบวิธีแบบสองเฟสกับ Paxos: https://lamport.azurewebsites.net/video/consensus-on-transac...
    • ชื่อคล้ายกัน แต่ two-phase locking ต่างจาก two-phase commit
      two-phase commit เป็นสิ่งที่นำไปเปรียบเทียบกับ Paxos ได้ และทั้งคู่จัดอยู่ในหมวด consensus protocol
      ส่วน two-phase locking เป็นกลไกควบคุม concurrency
  • มันจะดำเนินต่อไปตลอด และไม่มีวันสมบูรณ์แบบ
    ปัญหาคือเมื่อข้อความ lock แรกหายไป คุณจะรู้ได้อย่างไรว่าสิ่งที่หายไปไม่ใช่ข้อความตอบกลับ
    ถ้าเป็นกรณีง่าย ๆ ก็แค่ดำเนินต่อเหมือน GitHub หรือ Dropbox แล้วค่อยจัดการ conflict ทีหลัง แต่ถ้าเป็นฐานข้อมูลก็ขอให้โชคดี และถ้าเป็นธนาคารก็ยิ่งกว่านั้น
  • ผมไม่ค่อยเข้าใจรูปสุดท้ายของ relaxed AVL tree เท่าไร ที่ขอบขวาสุดซึ่งเป็น การค้นหา 100% อัลกอริทึม TL2 น่าจะ scale แบบเชิงเส้นตามจำนวนเธรด
    ใน read-only transaction นั้น TL2 แค่ sample global version แล้วตรวจสอบว่าสำหรับการอ่านทั้งหมด local version ไม่เกิน version ที่ sample ไว้ก็พอ
    ถ้าอย่างนั้นก็ยากจะเข้าใจว่าทำไมกราฟถึงต่ำกว่าเชิงเส้น และทำไม TL2 ถึงไม่เร็วเท่า STM implementation อื่น ๆ
    • ผมไม่เห็นกราฟแบบนั้นของ TL2 เห็นแต่กราฟ TLRW แทน ซึ่ง TLRW ใช้ reader lock จึงมีข้อจำกัดด้าน scalability
  • แก้ได้ง่าย ๆ ด้วยการเพิ่มคิวแบบสุ่ม
    ตัวอย่างเช่น สมมติว่าปกติมีงาน 1000 งาน และมี hardware thread 10–100 เธรด
    สร้างรายการที่เรียงลำดับของงาน 1000 งานหนึ่งรายการ แล้วทำสำเนาให้แต่ละเธรด จากนั้นสุ่มลำดับของสำเนาในแต่ละครั้ง
    จากนั้นแต่ละเธรดก็อ่านรายการของตัวเองและรันงาน แล้ว subscribe ไปยังรายการหนึ่งที่ implement เป็นคิวแบบหลายเธรดที่ไม่บล็อก
    กรณีแย่ที่สุดคืออาจมีบางเธรดทำงานบางงานซ้ำ ๆ
    ด้วยวิธีนี้ atomic operation อาจ scale ได้มากถึง 1000 เท่า