บทความนี้ส่วนใหญ่ศึกษาเนื้อหาที่เกี่ยวข้องของปริมาณงานสูงและแคช LRU แบบเธรดที่ปลอดภัยดังนี้
ไม่กี่ปีที่ผ่านมาฉันใช้แคช LRU เพื่อค้นหา ID สำหรับคำหลัก โครงสร้างข้อมูลนั้นน่าสนใจมากเนื่องจากปริมาณงานที่ต้องการมีขนาดใหญ่พอที่จะกำจัดปัญหาประสิทธิภาพที่เกิดจาก locks จำนวนมากและคำหลัก synchronized แอปพลิเคชันถูกนำไปใช้ใน Java
ฉันคิดว่าชุดของการจัดสรรการอ้างอิงอะตอมจะรักษาคำสั่ง LRU และ LRU ในพร้อมกัน ในตอนแรกฉันห่อค่าลงในรายการ รายการมีโหนดในห่วงโซ่ LRU ของรายการเชื่อมโยงสองเท่า หางของห่วงโซ่รักษารายการที่ใช้เมื่อเร็ว ๆ นี้และโหนดหัวเก็บรายการที่อาจถูกล้างเมื่อแคชมีขนาดที่กำหนด แต่ละโหนดชี้ไปที่รายการที่ใช้ในการค้นหา
เมื่อคุณค้นหาค่าผ่านคีย์แคชก่อนอื่นต้องค้นหาแผนที่เพื่อดูว่าค่านี้มีอยู่หรือไม่ หากไม่มีอยู่มันจะขึ้นอยู่กับตัวโหลดเพื่ออ่านค่าจากแหล่งข้อมูลในวิธีการอ่านผ่านและเพิ่มในแผนที่ใน "เพิ่มถ้าหายไป" ความท้าทายในการสร้างความมั่นใจว่าปริมาณงานที่สูงคือการรักษาห่วงโซ่ LRU ได้อย่างมีประสิทธิภาพ แผนที่แฮชที่เกิดขึ้นพร้อมกันนี้ถูกแบ่งส่วนและระดับเธรดอยู่ในระดับหนึ่ง (คุณสามารถระบุระดับการเกิดขึ้นพร้อมกันเมื่อคุณสร้างแผนที่) จะไม่ได้สัมผัสกับการแข่งขันเธรดมากเกินไป แต่โซ่ LRU ไม่สามารถแบ่งออกเป็นวิธีเดียวกันได้หรือไม่? เพื่อแก้ปัญหานี้ฉันได้แนะนำคิวเสริมสำหรับการล้างการดำเนินการ
มีวิธีพื้นฐานหกวิธีในแคช สำหรับแคชฮิตการค้นหารวมถึงการดำเนินการพื้นฐานสองประการ: รับและเสนอและสำหรับการสูญเสียหยาบมีสี่วิธีพื้นฐาน: รับโหลดใส่และข้อเสนอ ในวิธีการวางเราอาจต้องติดตามการดำเนินการที่ชัดเจน เมื่อแคชกระทบเราทำการล้างโซ่ LRU ที่เรียกว่าการดำเนินการทำให้บริสุทธิ์
รับ: รายการค้นหาในแผนที่โดยคีย์
โหลด: โหลดค่าจากแหล่งข้อมูล
ใส่: สร้างรายการและแมปกับคีย์
ข้อเสนอ: ผนวกโหนดที่หางของรายการ LRU ที่อ้างถึงรายการที่เข้าถึงได้เมื่อเร็ว ๆ นี้
Evict: ลบโหนดที่หัวของรายการและรายการที่เกี่ยวข้องจากแผนที่ (หลังจากแคชถึงขนาดที่แน่นอน)
PURGE: ลบโหนดที่ไม่ได้ใช้ในรายการ LRU - เราอ้างถึงโหนดเหล่านี้เป็นหลุมและคิวการทำความสะอาดติดตามสิ่งเหล่านี้
การดำเนินการล้างและการดำเนินการทำให้บริสุทธิ์เป็นทั้งชุดข้อมูลการประมวลผลขนาดใหญ่ มาดูรายละเอียดของการดำเนินการแต่ละครั้ง
การดำเนินการรับใช้งานได้ดังนี้:
รับ (k) -> รายการค้นหาการค้นหาโดยคีย์ k ถ้าแคชตีเรามีรายการ E ข้อเสนอ E รายการ E ลองล้างรูบางค่า load ค่า v สำหรับคีย์ k สร้างรายการ e < - (k, v) ลองใส่รายการ END RETURN EV
หากมีคีย์อยู่เราจะให้โหนดใหม่ที่หางของห่วงโซ่ LRU เพื่อระบุว่านี่เป็นค่าที่ใช้เมื่อเร็ว ๆ นี้ การดำเนินการของ GET และข้อเสนอไม่ใช่การดำเนินการอะตอม (ไม่มีการล็อคที่นี่) ดังนั้นเราจึงไม่สามารถพูดได้ว่าจุดโหนดที่เสนอนี้เป็นเอนทิตีที่ใช้ล่าสุด แต่มันเป็นเอนทิตีที่ใช้ล่าสุดที่เพิ่งได้รับเมื่อเราดำเนินการพร้อมกัน เราไม่บังคับให้รับและเสนอให้ดำเนินการสั่งซื้อระหว่างเธรดเนื่องจากอาจ จำกัด ปริมาณงาน หลังจากเสนอโหนดเราพยายามดำเนินการบางอย่างเพื่อล้างและคืนค่า มาดูข้อเสนอและการดำเนินการล้างรายละเอียดด้านล่าง
หากการสูญเสียแคชเกิดขึ้นเราจะเรียกตัวโหลดเพื่อโหลดค่าสำหรับคีย์นี้สร้างเอนทิตีใหม่และใส่ลงในแผนที่และการดำเนินการใส่เป็นดังนี้:
ใส่ (e) -> e รายการที่มีอยู่ ex < - map.putifabsent (ek, e) หากไม่มีข้อเสนอรายการ e; หากขนาดถึง Evict-threshold ขับไล่รายการบางรายการกลับรายการ ELSE ELS
อย่างที่คุณเห็นอาจมีการแข่งขันเมื่อสองเธรดขึ้นไปใส่เอนทิตีลงในแผนที่ แต่อนุญาตให้ประสบความสำเร็จเพียงครั้งเดียวและจะเรียกข้อเสนอ หลังจากให้โหนดที่หางของห่วงโซ่ LRU เราต้องตรวจสอบว่าแคชมาถึงเกณฑ์ซึ่งเป็นตัวระบุที่เราใช้เพื่อเริ่มการทำงานที่ชัดเจนของแบทช์ ในสถานการณ์จำลองแอปพลิเคชันเฉพาะนี้การตั้งค่าของเกณฑ์มีขนาดเล็กกว่าความจุ การดำเนินการล้างเกิดขึ้นในชุดเล็ก ๆ มากกว่าเมื่อมีการเพิ่มเอนทิตีทุกครั้ง หลายเธรดอาจมีส่วนร่วมในการดำเนินการล้างจนกว่าความจุแคชถึงความจุ การล็อคเป็นเรื่องง่าย แต่เธรดสามารถปลอดภัย การล้างโหนดหัวของห่วงโซ่ LRU จำเป็นต้องมีการกำจัดซึ่งต้องใช้การดำเนินการอะตอมอย่างระมัดระวังเพื่อหลีกเลี่ยงการดำเนินการกำจัดแบบมัลติเธรดในแผนที่
การดำเนินการข้อเสนอนี้น่าสนใจมาก มันพยายามสร้างโหนดเสมอ แต่ไม่พยายามลบและลบโหนดที่ไม่ได้ใช้ใน LRU อีกต่อไปทันที
ข้อเสนอ (e) หากโหนดหางไม่ได้อ้างถึงรายการ e กำหนดโหนดปัจจุบัน c <-en สร้างโหนดใหม่ n (e) ผู้อ้างอิงโหนดใหม่ไปยังรายการ e หากอะตอมเปรียบเทียบและตั้งค่าโหนด EN คาดว่าจะกำหนด n เพิ่มโหนด n ไปยังรายการ LRU
ก่อนอื่นจะตรวจสอบว่าโหนดที่หางของห่วงโซ่ไม่ได้ชี้ไปที่เอนทิตีที่เข้าถึงได้ซึ่งไม่แตกต่างกันเว้นแต่เธรดทั้งหมดมักจะเข้าถึงคู่คีย์ค่าเดียวกัน มันจะสร้างโหนดใหม่ที่หางของโซ่ เมื่อเอนทิตีนี้แตกต่างกันก่อนที่จะให้โหนดใหม่มันพยายามทำการเปรียบเทียบและตั้งค่าการดำเนินงานสำหรับเอนทิตีซึ่งจะป้องกันหลายเธรดจากการทำสิ่งเดียวกัน
เธรดที่จัดสรรโหนดได้สำเร็จจะให้โหนดใหม่ในตอนท้ายของห่วงโซ่ LRU การดำเนินการนี้เหมือนกับการค้นหาใน ConcurrentLinkedQueue อัลกอริทึมการพึ่งพาอธิบายไว้ในบทความต่อไปนี้ ง่ายรวดเร็วรวดเร็วและไม่ปิดกั้นและปิดกั้นอัลกอริธึมคิวพร้อมกัน เธรดจะตรวจสอบว่าเอนทิตีเกี่ยวข้องกับโหนดอื่น ๆ มาก่อนหรือไม่ ถ้าเป็นเช่นนั้นโหนดเก่าจะไม่ถูกลบทันที แต่จะถูกทำเครื่องหมายเป็นหลุม (การอ้างอิงถึงเอนทิตีของมันจะถูกตั้งค่าให้ว่าง)
ข้างต้นเป็นคำอธิบายโดยละเอียดทั้งหมดของบทความนี้เกี่ยวกับแคช LRU ที่มีความปลอดภัยสูงและเธรดที่ปลอดภัยและฉันหวังว่ามันจะเป็นประโยชน์กับทุกคน เพื่อนที่สนใจสามารถอ้างถึงหัวข้ออื่น ๆ ที่เกี่ยวข้องในเว็บไซต์นี้ต่อไป หากมีข้อบกพร่องใด ๆ โปรดฝากข้อความไว้เพื่อชี้ให้เห็น ขอบคุณเพื่อนที่ให้การสนับสนุนเว็บไซต์นี้!