การแย่งแคช (cache stampede) เป็น ความล้มเหลวแบบต่อเนื่องประเภทหนึ่งที่สามารถเกิดขึ้นได้เมื่อระบบประมวลผลแบบขนาน ขนาดใหญ่ที่มีกลไก การแคชอยู่ภายใต้ภาระงานที่สูงมาก พฤติกรรมนี้บางครั้งเรียกว่าdog- piling ^{[ 1 ] [ 2 ]}

เพื่อให้เข้าใจว่าปรากฏการณ์ cache stampede เกิดขึ้นได้อย่างไร ลองพิจารณาเว็บเซิร์ฟเวอร์ที่ใช้memcachedในการแคชหน้าเว็บที่แสดงผลแล้วเป็นระยะเวลาหนึ่ง เพื่อลดภาระของระบบ ภายใต้ภาระงานสูงเป็นพิเศษสำหรับ URL เดียว ระบบจะยังคงตอบสนองได้ตราบใดที่ทรัพยากรนั้นยังคงอยู่ในแคช โดยคำขอต่างๆ จะถูกจัดการโดยการเข้าถึงสำเนาที่แคชไว้ ซึ่งจะช่วยลดการประมวลผลการแสดงผลที่ใช้ทรัพยากรมาก

ในสภาวะที่ภาระงานต่ำ การพลาดแคชจะส่งผลให้มีการคำนวณการแสดงผลใหม่เพียงครั้งเดียว ระบบจะยังคงทำงานต่อไปได้ตามปกติ โดยภาระงานเฉลี่ยจะอยู่ในระดับต่ำมากเนื่องจากอัตราการเข้าถึงแคชสูง

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

เพื่อให้เห็นภาพชัดเจนขึ้น สมมติว่าหน้าเว็บที่กำลังพิจารณาใช้เวลาแสดงผล 3 วินาที และเรามีปริมาณการใช้งาน 10 คำขอต่อวินาที เมื่อแคชของหน้าเว็บหมดอายุลง เราจะมีกระบวนการทำงานพร้อมกัน 30 กระบวนการที่คำนวณการแสดงผลหน้าเว็บใหม่และอัปเดตแคชด้วยหน้าเว็บที่แสดงผลแล้ว

ด้านล่างนี้คือรูปแบบการใช้งานแคชทั่วไปสำหรับรายการที่ต้องได้รับการอัปเดตทุกๆหน่วยเวลา ttl :

ฟังก์ชัน fetch( key , ttl ) { ค่า ← cache_read( key ) ถ้า (! ค่า ) { ค่า ← recompute_value() } cache_write( key , value , ttl ) } ค่าส่งคืน } 

หากฟังก์ชันrecompute_value()ใช้เวลานานและมีการเข้าถึงคีย์บ่อยครั้ง กระบวนการจำนวนมากจะเรียกใช้recompute_value() พร้อมกัน เมื่อค่าในแคชหมดอายุ

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

มีการเสนอแนวทางหลายประการเพื่อลดปัญหาการแย่งชิงแคช (หรือที่เรียกว่าการป้องกันการทับถม) ซึ่งสามารถแบ่งออกได้เป็น 3 ประเภทหลักๆ

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

ในกรณีที่ล็อก ไม่ สำเร็จ มีตัวเลือกการใช้งานที่แตกต่างกันดังนี้:

• รอจนกว่าค่าจะถูกคำนวณใหม่เสร็จ
• ส่งคืนค่า "ไม่พบ" และให้ไคลเอนต์จัดการกับการไม่มีค่าดังกล่าวอย่างเหมาะสม
• เก็บรายการที่ล้าสมัยไว้ในแคชเพื่อใช้ในระหว่างที่กำลังคำนวณค่าใหม่

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

วิธีแก้ปัญหานี้จะย้ายการคำนวณค่าแคชใหม่จากกระบวนการที่ต้องการใช้ไปยังกระบวนการภายนอก การคำนวณใหม่ของกระบวนการภายนอกสามารถเริ่มต้นได้หลายวิธี:

• เมื่อค่าในแคชใกล้หมดอายุ
• เป็นระยะๆ
• เมื่อกระบวนการที่ต้องการค่าดังกล่าวพบกับแคชพลาด

แนวทางนี้ต้องการส่วนประกอบที่เคลื่อนไหวได้เพิ่มขึ้นอีกหนึ่งส่วน นั่นคือกระบวนการภายนอก ซึ่งจำเป็นต้องได้รับการบำรุงรักษาและตรวจสอบ นอกจากนี้ วิธีแก้ปัญหานี้ยังต้องการการแยก/การทำซ้ำโค้ดที่ไม่เป็นธรรมชาติ และเหมาะสำหรับคีย์แคชแบบคงที่เป็นส่วนใหญ่ (เช่น ไม่ได้สร้างขึ้นแบบไดนามิก ดังเช่นในกรณีของคีย์ที่จัดทำดัชนีโดย ID)

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

การใช้งานต่อไปนี้ซึ่งอิงตามการแจกแจงแบบเอกซ์โปเนนเชียลได้รับการพิสูจน์แล้วว่าเหมาะสมที่สุดในแง่ของประสิทธิภาพในการป้องกันการเหยียบกันตายและการคำนวณใหม่ในช่วงต้นสามารถเกิดขึ้นได้^{[ 3 ]}

ฟังก์ชัน x-fetch( key , ttl , beta =1) { value , delta , expiry ← cache_read( key ) if (! value || (time() - delta * beta * log(rand(0,1))) ≥ expiry ) { start ← time() value ← recompute_value() delta ← time() – start cache_write( key , ( value , delta ), ttl ) } ค่าส่งคืน } 

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

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

• การลดการแตกตื่นของแคชให้เหลือน้อยที่สุด , Joshua Thijssen, 2010
• ปัญหาและวิธีแก้ปัญหาสำหรับการใช้งานแคชในภาษา Perl ทั่วไป , Jonathan Swartz, 2008