โมเดลแคชสองคัชที่กล่าวถึงในบทความนี้หมายถึงโมเดลแคชของข้อมูลในหน่วยความจำ
ไม่ว่าภาษาใดคุณอาจต้องใส่ข้อมูลบางอย่างในหน่วยความจำเพื่อหลีกเลี่ยงการดำเนินการซ้ำและการอ่าน สถานการณ์ที่พบบ่อยที่สุดคือตัวเลือก jQuery การเลือกองค์ประกอบ DOM บางอย่างใช้เวลานานมาก เราหวังว่าจะแคชข้อมูลเหล่านี้โดยไม่ต้องเดินทางทรี DOM อีกครั้งทุกครั้งที่เราโทร
บันทึกไว้ แต่ต้องมีปริมาณ! คุณไม่สามารถใส่ข้อมูลประวัติทั้งหมดไว้ในหน่วยความจำได้ ท้ายที่สุดความจุหน่วยความจำในปัจจุบันยังคงน่าสงสาร แม้ว่าหน่วยความจำจะมีขนาดใหญ่พอหน่วยความจำที่จัดสรรโดยแต่ละเธรดในทางทฤษฎียังคงมี จำกัด
ดังนั้นคำถามคือเราจะแคชข้อมูลที่มีประโยชน์อย่างแท้จริงได้อย่างมีประสิทธิภาพได้อย่างไร สิ่งนี้เกี่ยวข้องกับอัลกอริทึมการกำจัดและข้อมูลขยะจะต้องถูกกำจัดเพื่อรักษาข้อมูลที่เป็นประโยชน์
มีแนวคิดทั่วไปหลายประการ:
FIFO: มันเป็นคิวครั้งแรกในครั้งแรกข้อมูลแคชตัวแรกและถูกกำจัดก่อน รุ่นนี้ใช้ภายในกรอบ JQuery ที่มีชื่อเสียง
LRU: โครงสร้างรายการที่เชื่อมโยงสองครั้งทุกครั้งที่มีการจัดเก็บข้อมูลใหม่จะถูกวางไว้โดยตรงในส่วนหัวของรายการที่เชื่อมโยง ข้อมูลที่เข้าถึงได้ในแต่ละครั้งจะถูกถ่ายโอนไปยังส่วนหัวของรายการที่เชื่อมโยง ด้วยวิธีนี้ข้อมูลในตอนท้ายของรายการที่เชื่อมโยงเป็นสิ่งที่ไม่ได้ใช้เมื่อเร็ว ๆ นี้และจะถูกกำจัด
สองคิว: FIFO+ LRU FIFO ส่วนใหญ่เก็บข้อมูลที่เก็บไว้เป็นครั้งแรกและ LRU เก็บข้อมูลฮอตสปอตที่ใช้อย่างน้อยสองครั้ง อัลกอริทึมนี้มีอัตราการเข้าชมสูงการปรับตัวที่แข็งแกร่งและความซับซ้อนต่ำ
มีอัลกอริทึมการกำจัดอื่น ๆ อีกมากมาย แต่มีเพียงสองประเภทเท่านั้นที่ใช้ในทางปฏิบัติมากขึ้น เนื่องจากอัลกอริทึมของพวกเขาไม่ซับซ้อนใช้งานง่ายประสิทธิภาพการดำเนินการที่สูงและอัตราการตีแคชเป็นที่ยอมรับในโอกาสส่วนใหญ่ ท้ายที่สุดอัลกอริทึมแคชก็ต้องใช้การบริโภค CPU ถ้ามันซับซ้อนเกินไปแม้ว่าอัตราการเข้าชมจะดีขึ้น แต่ก็ไม่คุ้มกับการสูญเสีย แค่คิดว่าถ้าคุณดึงข้อมูลจากแคชมันต้องใช้เวลามากกว่าการดึงข้อมูลจากตำแหน่งเดิม การใช้แคชคืออะไร?
ฉันจะไม่พูดถึงทฤษฎีเฉพาะ มีบางอย่างออนไลน์ แต่ฉันไม่เข้าใจมากนัก วันนี้ฉันจะแบ่งปันโมเดลแคชสองรุ่น JavaScript กับคุณ
มาพูดถึงวิธีการใช้ก่อนมันง่ายมาก
วิธีการใช้งานพื้นฐานมีดังนี้:
[/รหัส]
var tq = inittwoqueues (10);
tq.set ("คีย์", "ค่า");
tq.get ("คีย์");
[/รหัส]
เมื่อเริ่มต้นเพียงแค่ระบุความจุแคช ควรสังเกตว่าเนื่องจาก FIFO+LRU ถูกนำไปใช้ภายในความจุจริงเป็นสองเท่าของความสามารถที่ระบุ ตัวอย่างข้างต้นระบุ 10 (คู่คีย์-ค่า) ซึ่งสามารถเก็บได้จริง 20
ขนาดความจุจะต้องกำหนดตามสถานการณ์แอปพลิเคชันจริง หากมีขนาดเล็กเกินไปอัตราการเข้าชมต่ำประสิทธิภาพต่ำและรุนแรงมากและคุณต้องวัดด้วยตัวเอง
ในระหว่างกระบวนการพัฒนาเพื่อตรวจสอบเอฟเฟกต์แคชแคชพูลสามารถเริ่มต้นเป็นเวอร์ชันการพัฒนา:
การคัดลอกรหัสมีดังนี้:
var tq = inittwoqueues (10, true);
tq.hitratio ();
เพียงเพิ่มพารามิเตอร์ไปยังจุดสิ้นสุดและเป็นจริง แคชพูลที่เริ่มต้นด้วยวิธีนี้จะนับอัตราการเข้าชมโดยอัตโนมัติและอัตราการเข้าชมสามารถทำได้ผ่านวิธี Hitratio หากไม่มีการเพิ่มพารามิเตอร์นี้อัตราการเข้าชมที่ได้จากวิธี Hitratio จะเป็น 0 เสมอ
อัตราการเข้าชมทางสถิติจะใช้ทรัพยากรอย่างแน่นอนดังนั้นจึงไม่แนะนำให้เปิดในสภาพแวดล้อมการผลิต
ถึงเวลาแบ่งปันรหัส:
การคัดลอกรหัสมีดังนี้:
(ฟังก์ชั่น (การส่งออก) {
-
* คลาสบริสุทธิ์สำหรับมรดก
* @Constructor
-
ฟังก์ชั่น fn () {}
fn.prototype = elimination.prototype;
-
* คลาสแม่ของอัลกอริทึมการกำจัดแคชตามรายการที่เชื่อมโยง
* @param maxlength cache ความจุ
* @Constructor
-
การกำจัดฟังก์ชั่น (maxlength) {
this.container = {};
this.length = 0;
this.maxLength = MaxLength || 30;
this.linkhead = this.buildNode ("", "");
this.linkhead.head = true;
this.linkTail = this.buildNode ("", "");
this.linktail.tail = true;
this.linkhead.next = this.linktail;
this.linktail.prev = this.linkhead;
-
Elimination.prototype.get = function (key) {
โยนข้อผิดพลาดใหม่ ("วิธีนี้จะต้องแทนที่!");
-
Elimination.prototype.set = function (คีย์, ค่า) {
โยนข้อผิดพลาดใหม่ ("วิธีนี้จะต้องแทนที่!");
-
-
* สร้างโหนดในรายการที่เชื่อมโยง
* ข้อมูล @param ข้อมูลที่มีอยู่ในโหนดนั่นคือค่าข้อมูลแคช
* @param key ตัวระบุที่ไม่ซ้ำกันของโหนดนั่นคือคีย์แคช
* @returns {{}}
-
Elimination.prototype.buildNode = function (data, key) {
var node = {};
node.data = ข้อมูล;
node.key = key;
Node.use = 0;
ส่งคืนโหนด;
-
-
* โหนดปรากฏขึ้นจากส่วนหัวของรายการที่เชื่อมโยง
* @returns {*}
-
Elimination.prototype.shift = function () {
var node = null;
if (! this.linkhead.next.tail) {
node = this.linkhead.next;
this.linkhead.next = node.next;
node.next.prev = this.linkhead;
ลบสิ่งนี้ container [node.key];
this.length-;
-
ส่งคืนโหนด;
-
-
* แทรกโหนดจากส่วนหัวของรายการที่เชื่อมโยง
* @param โหนดโหนดวัตถุ
* @returns {*}
-
Elimination.prototype.unshift = ฟังก์ชั่น (โหนด) {
node.next = this.linkhead.next;
this.linkhead.next.prev = node;
this.linkhead.next = node;
node.prev = this.linkhead;
this.container [node.key] = node;
this.length ++;
ส่งคืนโหนด;
-
-
* แทรกโหนดจากส่วนท้ายของรายการที่เชื่อมโยง
* @param โหนดโหนดวัตถุ
* @returns {*}
-
Elimination.prototype.append = function (node) {
this.linktail.prev.next = node;
node.prev = this.linktail.prev;
node.next = this.linktail;
this.linktail.prev = node;
this.container [node.key] = node;
this.length ++;
ส่งคืนโหนด;
-
-
* โหนดปรากฏขึ้นจากส่วนท้ายของรายการที่เชื่อมโยง
* @returns {*}
-
Elimination.prototype.pop = function () {
var node = null;
if (! this.linktail.prev.head) {
node = this.linktail.prev;
node.prev.next = this.linktail;
this.linktail.prev = node.prev;
ลบสิ่งนี้ container [node.key];
this.length-;
-
ส่งคืนโหนด;
-
-
* ลบโหนดที่ระบุออกจากรายการที่เชื่อมโยง
* @param โหนดโหนดวัตถุ
* @returns {*}
-
Elimination.prototype.remove = ฟังก์ชั่น (โหนด) {
node.prev.next = node.next;
node.next.prev = node.prev;
ลบสิ่งนี้ container [node.key];
this.length-;
ส่งคืนโหนด;
-
-
* การประมวลผลที่จำเป็นต้องทำเมื่อมีการเข้าถึงโหนดคือการย้ายโหนดไปยังส่วนหัวของรายการที่เชื่อมโยง
* @param Node
-
Elimination.prototype.use = function (Node) {
สิ่งนี้ลบ (โหนด);
this.unshift (โหนด);
-
-
* การใช้อัลกอริทึมการกำจัดแคช LRU
* @Constructor
-
ฟังก์ชั่น lru () {
กำจัด. appply (นี่, ข้อโต้แย้ง);
-
lru.prototype = new fn ();
lru.prototype.get = function (คีย์) {
var node = undefined;
node = this.container [key];
ถ้า (โหนด) {
สิ่งนี้ใช้ (โหนด);
-
ส่งคืนโหนด;
-
lru.prototype.set = function (คีย์, ค่า) {
var node = this.buildNode (value, key);
if (this.length === this.maxLength) {
this.pop ();
-
this.unshift (โหนด);
-
-
* การใช้อัลกอริทึมการกำจัดแคช FIFO
* @Constructor
-
ฟังก์ชั่น fifo () {
กำจัด. appply (นี่, ข้อโต้แย้ง);
-
fifo.prototype = new fn ();
fifo.prototype.get = function (คีย์) {
var node = undefined;
node = this.container [key];
ส่งคืนโหนด;
-
fifo.prototype.set = function (คีย์, ค่า) {
var node = this.buildNode (value, key);
if (this.length === this.maxLength) {
this.shift ();
-
this.append (โหนด);
-
-
* การห่อหุ้มอัลกอริทึมของ LRU และ FIFO ได้กลายเป็นอัลกอริทึมการกำจัดแคช Twoque
* @param maxlength
* @Constructor
-
ฟังก์ชั่นเอเจนต์ (maxlength) {
this.getCount = 0;
this.hitCount = 0;
this.lir = ใหม่ FIFO (maxlength);
this.hir = ใหม่ lru (maxlength);
-
agent.prototype.get = function (คีย์) {
var node = undefined;
node = this.lir.get (คีย์);
ถ้า (โหนด) {
Node.use ++;
if (node.use> = 2) {
this.lir.remove (โหนด);
this.hir.set (node.key, node.data);
-
}อื่น{
node = this.hir.get (คีย์);
-
ส่งคืนโหนด;
-
agent.prototype.getx = function (คีย์) {
var node = undefined;
this.getCount ++;
node = this.get (key);
ถ้า (โหนด) {
this.hitcount ++;
-
ส่งคืนโหนด;
-
agent.prototype.set = function (คีย์, ค่า) {
var node = null;
node = this.lir.container [key] || this.hir.container [คีย์];
ถ้า (โหนด) {
node.data = ค่า;
}อื่น{
this.lir.set (คีย์, ค่า);
-
-
-
* รับอัตราการเข้าชม
* @returns {*}
-
agent.prototype.hitratio = function () {
var ret = this.getCount;
ถ้า (ret) {
ret = this.hitcount / this.getCount;
-
ผลตอบแทนผลตอบแทน;
-
-
* อินเทอร์เฟซภายนอก
* @param maxlength cache ความจุ
* @param dev ไม่ว่าจะเป็นสภาพแวดล้อมการพัฒนาสภาพแวดล้อมการพัฒนาจะนับอัตราการเข้าชมมิฉะนั้นจะไม่
* @returns {{get, set: function, hitratio: function}}
-
exports.inittwoqueues = function (maxlength, dev) {
var api = ตัวแทนใหม่ (maxlength);
กลับ {
Get: (function () {
ถ้า (dev) {
ฟังก์ชั่นส่งคืน (คีย์) {
var ret = api.getx (คีย์);
return ret && ret.data;
-
}อื่น{
ฟังก์ชั่นส่งคืน (คีย์) {
var ret = api.get (คีย์);
return ret && ret.data;
-
-
-
SET: function () {
api.set.apply (API, อาร์กิวเมนต์);
-
hitratio: function () {
return api.hitratio.apply (API, อาร์กิวเมนต์);
-
-
-
}(นี้));
ในที่สุดฉันอยากจะเตือนคุณอีกครั้งว่าอัลกอริทึมแคชจะต้องรวมกับสถานการณ์แอปพลิเคชันจริง หากไม่มีอัลกอริทึมสากลสิ่งที่ดีที่สุดก็คือสิ่งที่ดีที่สุด!