{"id":1440,"date":"2012-03-11T17:12:40","date_gmt":"2012-03-11T09:12:40","guid":{"rendered":"http:\/\/doophp.sinaapp.com\/?p=1440"},"modified":"2012-03-12T10:13:24","modified_gmt":"2012-03-12T02:13:24","slug":"cache-strategy","status":"publish","type":"post","link":"https:\/\/blog.vimge.com\/archives\/architecture\/cache-strategy.html","title":{"rendered":"\u5e38\u89c1\u7f13\u5b58\u7b97\u6cd5\u548c\u7f13\u5b58\u7b56\u7565"},"content":{"rendered":"
\u7f13\u5b58\u7b97\u6cd5\uff1a<\/strong>\u7f13\u5b58\u6cd5\u901a\u8fc7\u8bbe\u8ba1\u826f\u597d\u7684\u6570\u636e\u5206\u5757\u3001\u9884\u53d6\u3001\u987a\u5e8f\u9884\u53d6\u3001\u7f13\u5b58\u66ff\u6362\u7b49\u7b97\u6cd5\u6765\u63d0\u9ad8\u5bf9\u7f13\u5b58\u5185\u5bb9\u7684\u547d\u4e2d\u7387\u3002\u7f13\u5b58\u7b97\u6cd5\u53ef\u4ee5\u5206\u4e3a\u57fa\u4e8e\u8bbf\u95ee\u65f6\u95f4\u7684\u7b56\u7565\u3001\u57fa\u4e8e\u8bbf\u95ee\u9891\u7387\u7684\u7b56\u7565\u3001\u8bbf\u95ee\u65f6\u95f4\u4e0e\u9891\u7387\u517c\u987e\u7b56\u7565\u3001\u65f6\u95f4\u8ddd\u79bb\u5206\u5e03\u7b56\u7565\u7b49\u7c7b\u578b\u3002<\/p>\n \u7f13\u5b58\u7b56\u7565\uff1a<\/strong>\u7f13\u5b58\u7b56\u7565\u4e3b\u8981\u4e09\u65b9\u9762:<\/p>\n \u5bf9\u4e8e\u7b2c\u4e8c\u65b9\u9762,\u5927\u90e8\u5206\u7f13\u5b58\u7b97\u6cd5\u4f7f\u7528\u9884\u53d6\u7b56\u7565\u6765\u63d0\u524d\u5c06\u90e8\u5206\u78c1\u76d8\u6570\u636e\u653e\u5165\u7f13\u5b58,\u4ee5\u8fdb\u4e00\u6b65\u51cf\u5c11\u78c1\u76d8I\/O,\u52a0\u5927\u7f13\u5b58\u547d\u4e2d\u7387\u3002\u901a\u8fc7\u8bb0\u5f55\u3001\u5206\u6790\u4ee5\u5f80\u7684\u6570\u636e\u8bf7\u6c42\u6a21\u5f0f\u6765\u9884\u6d4b\u5c06\u6765\u53ef\u80fd\u88ab\u8bf7\u6c42\u5230\u7684\u6570\u636e\u6bb5,\u5c06\u8bbf\u95ee\u53ef\u80fd\u6027\u5927\u7684\u6570\u636e\u6bb5\u653e\u5165\u7f13\u5b58\u3002<\/p>\n \u7f13\u5b58\u7b56\u7565\u7684\u6570\u636e\u5757\u5206\u5272\uff1a<\/p>\n \u9996\u90e8\u7f13\u5b58\u548c\u5206\u5757\u7f13\u5b58\u7b56\u7565\u666e\u904d\u5e94\u7528\u4e8eVoD\u5f71\u7247\u6587\u4ef6\u3002\u9996\u90e8\u7f13\u5b58\u5c06\u5f71\u7247\u6587\u4ef6\u5f00\u59cb\u7684\u4e00\u90e8\u5206\u653e\u5165\u7f13\u5b58\u4ee5\u51cf\u5c0f\u70b9\u64ad\u7528\u6237\u7684\u542f\u52a8\u5ef6\u8fdf,\u5bf9\u4e8e\u5f71\u7247\u6587\u4ef6\u5176\u4ed6\u90e8\u5206\u7684\u8bbf\u95ee\u9700\u8981\u76f4\u63a5\u8bfb\u53d6\u78c1\u76d8\u3002<\/p>\n \u5206\u5757\u7f13\u5b58\u901a\u8fc7\u5c06\u5f71\u7247\u6587\u4ef6\u5207\u5206\u6210\u5c0f\u5757,\u4ee5\u5757\u4e3a\u5355\u4f4d\u8fdb\u884c\u7f13\u5b58\u64cd\u4f5c\u3002\u5206\u5757\u7f13\u5b58\u5206\u4e3a\u5b9a\u957f\u5206\u5757\u4e0e\u53d8\u957f\u5206\u5757\u3002\u5b9a\u957f\u5206\u5757\u5c06\u6587\u4ef6\u5207\u5206\u4e3a\u5927\u5c0f\u76f8\u540c\u7684\u5757,\u53d8\u957f\u5206\u5757,\u53d8\u957f\u7b97\u6cd5\u662f\u57fa\u4e8e\u5f71\u7247\u6587\u4ef6\u8d8a\u9760\u540e\u7684\u90e8\u5206\u88ab\u8bbf\u95ee\u7684\u6982\u7387\u8d8a\u4f4e\u7684\u63a8\u65ad,\u5c06\u6587\u4ef6\u6309\u7167\u9996\u5c3e\u4f4d\u7f6e\u5206\u5757,\u5404\u5757\u5927\u5c0f\u6309\u6307\u6570\u9012\u589e\u3002<\/p>\n \u4f46\u4ee5\u4e0a\u5b9a\u957f\u4e0e\u53d8\u957f\u5206\u5757\u5747\u5ffd\u7565\u4e86\u4e24\u70b9:<\/p>\n \u9700\u8bbe\u8ba1\u826f\u597d\u7684\u7b97\u6cd5\u81ea\u9002\u5e94\u5f71\u7247\u70ed\u70b9\u7684\u4e0d\u540c\u4f4d\u7f6e\u4e0e\u53d8\u5316\u3002<\/p>\n \u7f13\u5b58\u7b56\u7565\u7684\u5206\u7c7b\uff1a<\/strong><\/p>\n \u7531\u4e8e\u4e0d\u540c\u7cfb\u7edf\u7684\u6570\u636e\u8bbf\u95ee\u6a21\u5f0f\u4e0d\u5c3d\u76f8\u540c,\u540c\u4e00\u79cd\u7f13\u5b58\u7b56\u96be\u4ee5\u5728\u5404\u79cd\u6570\u636e\u8bbf\u95ee\u6a21\u5f0f\u4e0b\u5747\u53d6\u5f97\u6ee1\u610f\u6027\u80fd,\u7814\u7a76\u4eba\u5458\u63d0\u51fa\u4e0d\u540c\u7f13\u5b58\u7b56\u7565\u4ee5\u9002\u5e94\u4e0d\u540c\u9700\u6c42\u3002<\/p>\n \u7f13\u5b58\u7b56\u7565\u53ef\u5206\u4e3a\u4ee5\u4e0b\u51e0\u7c7b:<\/strong><\/p>\n\n
\n
\n
\nLRU-2[2, 3]\u7b97\u6cd5\u8bb0\u5f55\u4e0b\u6bcf\u4e2a\u7f13\u5b58\u9875\u9762\u6700\u540e\u4e24\u6b21\u88ab\u8bbf\u95ee\u7684\u65f6\u95f4\u3002\u66ff\u6362\u9875\u9762\u65f6\u66ff\u6362\u6389\u5012\u6570\u7b2c\u4e8c\u6b21\u8bbf\u95ee\u65f6\u95f4\u8ddd\u73b0\u5728\u6700\u4e45\u7684\u4e00\u9879\u3002\u5728IRM (IndependentReferenceModel)\u8bbf\u95ee\u6a21\u5f0f\u4e0b,LRU-2\u6709\u7740\u6700\u597d\u7684\u9884\u671f\u547d\u4e2d\u7387,\u7531\u4e8eLRU-2\u7b97\u6cd5\u8981\u7ef4\u62a4\u4e00\u4e2a\u4f18\u5148\u7ea7\u961f\u5217,\u6240\u4ee5\u8be5\u7b97\u6cd5\u590d\u6742\u5ea6\u4e3alogN(N\u4e3a\u7f13\u5b58\u961f\u5217\u4e2d\u7f13\u5b58\u9879\u7684\u6570\u91cf)\u3002
\n2Q[4](2 Queues)\u4f7f\u7528LRU\u961f\u5217\u66ff\u6362\u4e86LRU-2\u4e2d\u7684\u4f18\u5148\u7ea7\u961f\u5217,\u5c06\u7b97\u6cd5\u65f6\u95f4\u590d\u6742\u5ea6\u7531logN\u964d\u4e3a\u5e38\u6570,\u4e14\u7ef4\u62a4\u7f13\u5b58\u9879\u7684\u5404\u4fe1\u606f\u6240\u9700\u7a7a\u95f4\u6bd4LRU-2\u5c0f\u3002
\nLIRS[5](Low Inter-ReferenceRecency Set)\u7ef4\u62a4\u4e00\u4e2a\u53d8\u957f\u7684LRU\u961f\u5217,\u8be5\u961f\u5217\u7684LRU\u7aef\u4e3a\u6700\u8fd1\u81f3\u5c11\u88ab\u8bbf\u95ee\u8fc72\u6b21\u7684\u7b2cLlirs\u9879(Llirs\u4e3a\u7b97\u6cd5\u53c2\u6570)\u3002LIRS\u7b97\u6cd5\u5728IRM\u8bbf\u95ee\u6a21\u5f0f\u4e0b\u53ef\u4ee5\u83b7\u5f97\u5f88\u9ad8\u7684\u547d\u4e2d\u7387,\u4f46\u5bf9\u4e8eSDD\u8bbf\u95ee\u6a21\u5f0f\u6548\u7387\u660e\u663e\u4e0b\u964d\u3002
\n\u5bf9\u4e8eVoD\u7cfb\u7edf,\u57fa\u4e8e\u8bbf\u95ee\u9891\u7387\u7684\u7b56\u7565\u53ef\u4ee5\u6355\u6349\u5230\u70ed\u70b9\u5f71\u7247\u7247\u6bb5,\u4f7f\u5f97\u5bf9\u70ed\u70b9\u7247\u6bb5\u7684\u5927\u91cf\u8bf7\u6c42\u514d\u4e8e\u8fdb\u884c\u7f13\u6162\u7684\u78c1\u76d8I\/O\u3002\u4f46\u5f71\u7247\u70ed\u70b9\u4f1a\u968f\u65f6\u95f4\u4e0d\u65ad\u53d8\u5316,\u4e14\u6b64\u7c7b\u7b56\u7565\u65e0\u6cd5\u5229\u7528VoD\u7684\u987a\u5e8f\u8bbf\u95ee\u6a21\u5f0f,\u6240\u4ee5\u7eaf\u7cb9\u4ee5\u8bbf\u95ee\u9891\u7387\u4e3a\u5ea6\u91cf\u6765\u8fdb\u884c\u66ff\u6362\u64cd\u4f5c\u4e0d\u9002\u5408VoD\u7cfb\u7edf\u3002<\/li>\n
\nLRFU[7](LeastRecently FrequentlyUsed)\u4e3a\u6bcf\u4e00\u4e2a\u7f13\u5b58\u9879\u7ef4\u62a4\u4e00\u4e2a\u6743\u503cC(x),\u5176\u521d\u59cb\u503c\u4e3a0, C(x)\u6309\u4ee5\u4e0b\u516c\u5f0f\u53d8\u5316\u3002
\n\u5728t\u65f6\u523b, C(x) =1+2-\u03bbC(x): x\u88ab\u8bbf\u95ee\u52302-\u03bbC(x)\u3000: x\u672a\u88ab\u8bbf\u95ee\u8fdb\u884c\u66ff\u6362\u64cd\u4f5c\u65f6,C(x)\u503c\u6700\u5c0f\u7684\u4e00\u9879\u88ab\u5220\u9664\u3002\u5f53\u65f6, LRFU\u7b97\u6cd5\u884c\u4e3a\u7c7b\u4f3c\u4e8eLFU;\u800c\u5f53\u65f6,\u8be5\u7b97\u6cd5\u884c\u4e3a\u903c\u8fd1LRU\u7b97\u6cd5\u3002\u8be5\u7b97\u6cd5\u901a\u8fc7\u9009\u7528\u5408\u9002\u7684\u03bb\u503c\u6765\u83b7\u5f97\u65f6\u95f4\u4e0e\u9891\u7387\u56e0\u7d20\u7684\u5e73\u8861\u3002
\nLRFU\u867d\u7136\u901a\u8fc7\u4e00\u4e2a\u503c\u6765\u517c\u987e\u8bbf\u95ee\u65f6\u95f4\u4e0e\u9891\u7387\u56e0\u7d20,\u4f46\u7531\u4e8e\u503c\u56fa\u5b9a,\u5f53\u8bbf\u95ee\u6a21\u5f0f\u53d8\u5316\u65f6,\u8be5\u7b97\u6cd5\u65e0\u6cd5\u505a\u51fa\u76f8\u5e94\u7684\u8c03\u6574\u800c\u9020\u6210\u6027\u80fd\u4e0b\u964d\u3002ALRFU[8](Adaptive LRFU)\u5728\u6b64\u65b9\u9762\u5bf9LRFU\u8fdb\u884c\u4e86\u6539\u8fdb\u3002\u901a\u8fc7\u5bf9\u6570\u636e\u8bbf\u95ee\u6a21\u5f0f\u7684\u5386\u53f2\u8fdb\u884c\u76d1\u63a7,ALRFU\u52a8\u6001\u8c03\u6574\u503c\u6765\u9002\u5e94\u6570\u636e\u8bbf\u95ee\u6a21\u5f0f\u7684\u6539\u53d8,\u8868\u73b0\u51fa\u6bd4LRFU\u66f4\u597d\u7684\u9002\u5e94\u6027\u3002<\/li>\n
\n\u4f46A&L\u7b97\u6cd5\u901a\u8fc7\u76f4\u63a5\u8ba1\u7b97\u7f13\u5b58\u533a\u6bb5\u751f\u6210\u4ee5\u6765\u7684\u603b\u7684\u8bbf\u95ee\u6570\u91cf\u3001\u9891\u7387\u6765\u751f\u6210\u7f13\u5b58\u6743\u503c,\u6ca1\u6709\u8003\u8651VoD\u5f71\u7247\u7684\u8bbf\u95ee\u70ed\u70b9\u4f1a\u968f\u65f6\u95f4\u4e0d\u65ad\u53d8\u5316\u3002\u5f53\u67d0\u4e9b\u7f13\u5b58\u533a\u6bb5\u5386\u53f2\u8bbf\u95ee\u9891\u7387\u8f83\u9ad8\u4f46\u6700\u8fd1\u8bbf\u95ee\u9891\u7387\u4e0b\u964d\u65f6,\u4ecd\u4fdd\u6301\u8f83\u5927\u6743\u503c,\u5f71\u54cd\u65b0\u7684\u70ed\u70b9\u7247\u6bb5\u7684\u7f13\u5b58,\u65e0\u6cd5\u9002\u5e94\u5f71\u7247\u70ed\u70b9\u7684\u52a8\u6001\u53d8\u5316\u3002
\nIBM\u63d0\u51fa\u7684SARC[10]\u662f\u9488\u5bf9\u4e8e\u5927\u578b\u670d\u52a1\u5668\u7684\u7f13\u5b58\u7b97\u6cd5,\u53ef\u5728\u968f\u673a\u8bbf\u95ee\u4e0e\u987a\u5e8f\u8bbf\u95ee\u7684\u6570\u636e\u8bbf\u95ee\u6a21\u5f0f\u4e0b\u505a\u51fa\u52a8\u6001\u9002\u5e94\u3002SARC\u901a\u8fc7\u5c06\u968f\u673a\u8bbf\u95ee\u4e0e\u987a\u5e8f\u8bbf\u95ee\u5206\u4e3a\u4e24\u4e2a\u961f\u5217\u5206\u522b\u7ba1\u7406\u6765\u5b9e\u73b0\u5bf9\u4e24\u79cd\u4e0d\u540c\u8bbf\u95ee\u6a21\u5f0f\u7684\u9002\u5e94\u3002\u5e76\u901a\u8fc7\u5206\u6790\u7f13\u5b58\u5927\u5c0f-\u547d\u4e2d\u7387\u7684\u4eff\u771f\u8bd5\u9a8c\u6570\u636e\u66f2\u7ebf,\u5f97\u51fa\u5bf9\u968f\u673a\u961f\u5217\u4e0e\u987a\u5e8f\u961f\u5217\u9879\u5206\u522b\u8fdb\u884c\u66ff\u6362\u7684\u4ee3\u4ef7\u51fd\u6570\u3002\u5f53\u8fdb\u884c\u7f13\u5b58\u66ff\u6362\u65f6,\u901a\u8fc7\u4e24\u961f\u5217\u7684\u4ee3\u4ef7\u51fd\u6570\u6765\u5bf9\u4ee3\u4ef7\u5c0f\u7684\u961f\u5217\u8fdb\u884c\u66ff\u6362\u3002<\/li>\n<\/ul>\n