業(yè)務(wù)模型
讀、寫(xiě)、刪的比例大致是7:3:1，至少要支持500w條緩存，平均每條緩存6k，要求設計一套性能比較好的緩存算法。
算法分析
不考慮MemCached，Velocity等現成的key-value緩存方案，也不考慮脫離.net gc自己管理內存,不考慮隨機讀取數據及順序讀取數據的場(chǎng)景，目前想到的有如下幾種LRU方案
算法
分析
SortedDictionary
.net自帶的，內部用二叉搜索樹(shù)（應該不是普通樹(shù)，至少是做過(guò)優(yōu)化的樹(shù)）實(shí)現的，檢索為O(log n)，比普通的Dictionay（O(1)）慢一點(diǎn)。
插入和刪除都是O(log n)，而且插入和刪除，會(huì )實(shí)時(shí)排序。
但是.net 2.0的這個(gè)類(lèi)沒(méi)有First屬性
Dictionary + PriorityQueue
Dictionay可以保證檢索是O(1)；
優(yōu)先隊列可以保證插入和刪除都為O(log n)；
但是優(yōu)先隊列刪除指定的項不支持（至少我找到的優(yōu)先隊列不支持），所以在刪除緩存的時(shí)候不知道咋實(shí)現
Dictionay + Binary heap
二叉堆也是優(yōu)先隊列，分析應該同上，我沒(méi)有詳細評估。
b樹(shù)
查找，刪除，插入效率都很好，數據庫都用它，但實(shí)現復雜，寫(xiě)一個(gè)沒(méi)有BUG的B樹(shù)幾乎不可能。有人提到stl:map是自頂向下的紅黑樹(shù)，查找，刪除，插入都是O(log n)，但咱不懂c++，沒(méi)做詳細測試。
Dictionay + List
Dict用來(lái)檢索；
List用來(lái)排序；
檢索、添加、刪除都沒(méi)問(wèn)題，只有在清空的時(shí)候需要執行List的排序方法，這時(shí)候緩存條目比較多的話(huà)，可能比較慢。
Dictionay + LinkedList
Dict用來(lái)檢索；
LinkedList的添加和刪除都是O(1)，添加緩存時(shí)在鏈表頭加節點(diǎn)，獲取緩存時(shí)把特定節點(diǎn)移動(dòng)（先刪除特定節點(diǎn)(O(n))，再到頭部添加節點(diǎn)(O(1))）到頭，緩存滿(mǎn)地時(shí)候截斷掉尾部的一些節點(diǎn)。
目前幾種方案在多線(xiàn)程下應該都需要加鎖，不太好設計無(wú)鎖的方案，下面這個(gè)鏈接是一個(gè)支持多線(xiàn)程的方案，但原理至今沒(méi)搞特明白
A High Performance Multi-Threaded LRU Cache
http://www.codeproject.com/KB/recipes/LRUCache.aspx用普通鏈表簡(jiǎn)單實(shí)現LRU緩存
以下是最后一種方案的簡(jiǎn)單實(shí)現，大家討論下這個(gè)方案值不值得優(yōu)化，或者其它的哪個(gè)方案比較合適
public class LRUCacheHelper<K, V> {
readonly Dictionary<K, V> _dict;
readonly LinkedList<K> _queue = new LinkedList<K>();
readonly object _syncRoot = new object();
private readonly int _max;
public LRUCacheHelper(int capacity, int max) {
_dict = new Dictionary<K, V>(capacity);
_max = max;
}
public void Add(K key, V value) {
lock (_syncRoot) {
checkAndTruncate();
_queue.AddFirst(key); //O(1)
_dict[key] = value; //O(1)
}
}
private void checkAndTruncate() {
lock (_syncRoot) {
int count = _dict.Count; //O(1)
if (count >= _max) {
int needRemoveCount = count / 10;
for (int i = 0; i < needRemoveCount; i++) {
_dict.Remove(_queue.Last.Value); //O(1)
_queue.RemoveLast(); //O(1)
}
}
}
}
public void Delete(K key) {
lock (_syncRoot) {
_dict.Remove(key); //(1)
_queue.Remove(key); // O(n)
}
}
public V Get(K key) {
lock (_syncRoot) {
V ret;
_dict.TryGetValue(key, out ret); //O(1)
_queue.Remove(key); //O(n)
_queue.AddFirst(key); //(1)
return ret;
}
}
}
用雙頭鏈表代替普通鏈表
突然想起來(lái)了，可以把鏈表?yè)Q成雙頭鏈表，然后在字典里保存鏈表節點(diǎn)，在Get方法的時(shí)候直接從字典里獲取到要移動(dòng)的節點(diǎn)，然后把這個(gè)節點(diǎn)的上一個(gè)節點(diǎn)的Next指針指向給下一個(gè)節點(diǎn)，下一個(gè)節點(diǎn)的Previous指針指向上一個(gè)節點(diǎn)，這樣就把移動(dòng)節點(diǎn)的操作簡(jiǎn)化成O(1)了，提高了緩存讀取的效率。
_dict.TryGetValue(key, out ret); //O(1)
ret.Next.Previous = ret.Previous //O(1)
ret. Previous.Next. = ret.Next //O(1)
_queue.AddFirst(key); //O(1)
我改進(jìn)后的鏈表就差不多滿(mǎn)足需求了，
操作
基本操作
復雜度
讀取
Dict.Get
Queue.Move
O 1
O 1
刪除
Dict.Remove
Queue.Remove
O 1
O 1
增加
Dict.Add
Queue.AddFirst
O 1
O 1
截斷
Dict.Remove
Queue.RemoveLast
O k
O k
K表示截斷緩存元素的個(gè)數
其中截斷的時(shí)候可以指定當緩存滿(mǎn)的時(shí)候截斷百分之多少的最少使用的緩存項。
其它的就是多線(xiàn)程的時(shí)候鎖再看看怎么優(yōu)化，字典有線(xiàn)程安全的版本，就把.net 3.0的讀寫(xiě)鎖扣出來(lái)再把普通的泛型字典保證成ThreadSafelyDictionay就行了，性能應該挺好的。
鏈表的話(huà)不太好用讀寫(xiě)鎖來(lái)做線(xiàn)程同步，大不了用互斥鎖，但得考慮下鎖的粒度，Move,AddFirst,RemoveLast的時(shí)候只操作一兩個(gè)節點(diǎn)，是不是想辦法只lock這幾個(gè)節點(diǎn)就行了，Truncate的時(shí)候因為要批量操作很多節點(diǎn)，所以要上個(gè)大多鏈表鎖，但這時(shí)候怎么讓其它操作停止得考慮考慮，類(lèi)似數據庫的表鎖和行鎖。
實(shí)現代碼
public class DoubleLinkedListNode<T> {
public T Value { get; set; }
public DoubleLinkedListNode<T> Next { get; set; }
public DoubleLinkedListNode<T> Prior { get; set; }
public DoubleLinkedListNode(T t) { Value = t; }
public DoubleLinkedListNode() { }
public void RemoveSelf() {
Prior.Next = Next;
Next.Prior = Prior;
}
}
public class DoubleLinkedList<T> {
protected DoubleLinkedListNode<T> m_Head;
private DoubleLinkedListNode<T> m_Tail;
public DoubleLinkedList() {
m_Head = new DoubleLinkedListNode<T>();
m_Tail = m_Head;
}
public DoubleLinkedList(T t)
: this() {
m_Head.Next = new DoubleLinkedListNode<T>(t);
m_Tail = m_Head.Next;
m_Tail.Prior = m_Head;
}
public DoubleLinkedListNode<T> Tail {
get { return m_Tail; }
}
public DoubleLinkedListNode<T> AddHead(T t) {
DoubleLinkedListNode<T> insertNode = new DoubleLinkedListNode<T>(t);
DoubleLinkedListNode<T> currentNode = m_Head;
insertNode.Prior = null;
insertNode.Next = currentNode;
currentNode.Prior = insertNode;
m_Head = insertNode;
return insertNode;
}
public void RemoveTail() {
m_Tail = m_Tail.Prior;
m_Tail.Next = null;
return;
}
}
public class LRUCacheHelper<K, V> {
class DictItem {
public DoubleLinkedListNode<K> Node { get; set; }
public V Value { get; set; }
}
readonly Dictionary<K, DictItem> _dict;
readonly DoubleLinkedList<K> _queue = new DoubleLinkedList<K>();
readonly object _syncRoot = new object();
private readonly int _max;
public LRUCacheHelper(int capacity, int max) {
_dict = new Dictionary<K, DictItem>(capacity);
_max = max;
}
public void Add(K key, V value) {
lock (this)
{
checkAndTruncate();
DoubleLinkedListNode<K> v = _queue.AddHead(key); //O(1)
_dict[key] = new DictItem() { Node = v, Value = value }; //O(1)
}
}
private void checkAndTruncate() {
int count = _dict.Count; //O(1)
if (count >= _max) {
int needRemoveCount = count / 10;
for (int i = 0; i < needRemoveCount; i++) {
_dict.Remove(_queue.Tail.Value); //O(1)
_queue.RemoveTail(); //O(1)
}
}
}
public void Delete(K key) {
lock (this) {
_dict[key].Node.RemoveSelf();
_dict.Remove(key); //(1)
}
}
public V Get(K key) {
lock (this) {
DictItem ret;
if (_dict.TryGetValue(key, out ret)) {
ret.Node.RemoveSelf();
_queue.AddHead(key);
return ret.Value;
}
return default(V);
}
}
}
性能測試
用雙頭鏈表測試了一下，感覺(jué)性能還可以接受，每秒鐘讀取可達80多w，每秒鐘寫(xiě)操作越20多w。
程序初始化200w條緩存，然后不斷的加，每加到500w，截斷掉10分之一，然后繼續加。
測試模型中每秒鐘的讀和寫(xiě)的比例是7:3，以下是依次在3個(gè)時(shí)間點(diǎn)截取的性能計數器圖。
圖1
圖2
圖3
內存最高會(huì )達到1g，cpu也平均百分之90以上，但測試到后期會(huì )發(fā)現每隔一段時(shí)間，就會(huì )有一兩秒，吞吐量為0，如最后一張截圖，后來(lái)觀(guān)察發(fā)現，停頓的那一兩秒是二代內存在回收，等不停頓的時(shí)候# gen 2 collections就會(huì )加1，這個(gè)原因應該是鏈表引起的，對鏈表中節點(diǎn)的添加和刪除是很耗費GC的，因為會(huì )頻繁的創(chuàng )建和銷(xiāo)毀對象。
后續改進(jìn)
1、 用游標鏈表來(lái)代替普通的雙頭鏈表，程序起來(lái)就收工分配固定大小的數組，然后用數組的索引來(lái)做鏈表，省得每次添加和刪除節點(diǎn)都要GC的參與，這相當于手工管理內存了，但目前我還沒(méi)找到c#合適的實(shí)現。
2、 有人說(shuō)鏈表不適合用在多線(xiàn)程環(huán)境中，因為對鏈表的每個(gè)操作都要加互斥鎖，連讀寫(xiě)鎖都用不上，我目前的實(shí)現是直接用互斥鎖做的線(xiàn)程同步，每秒的吞吐量七八十萬(wàn)，感覺(jué)lock也不是瓶頸，如果要改進(jìn)的話(huà)可以把Dictionary用ThreadSafelyDictionary來(lái)代替，然后鏈表還用互斥鎖（剛開(kāi)始設想的鏈表操作只鎖要操作的幾個(gè)節點(diǎn)以降低并發(fā)沖突的想法應該不可取，不嚴謹）。
3、 還有一個(gè)地方就是把鎖細分以下，鏈表還用鏈表，但每個(gè)鏈表的節點(diǎn)是個(gè)HashSet，對HashSet的操作如果只有讀，寫(xiě)，刪，沒(méi)有遍歷的話(huà)應該不需要做線(xiàn)程同步（我感覺(jué)不用，因為Set就是一個(gè)集合，一個(gè)線(xiàn)程往里插入，一個(gè)線(xiàn)程往里刪除，一個(gè)線(xiàn)程讀取應該沒(méi)問(wèn)題，頂多讀進(jìn)來(lái)的數據可能馬上就刪除了，而整個(gè)Set的結構不會(huì )破壞）。然后新增數據的時(shí)候往鏈表頭頂Set里插入，讀取某個(gè)數據的時(shí)候把它所在的節點(diǎn)的Set里刪除該數據，然后再鏈表頭的Set里插入一個(gè)數據，這樣反復操作后，鏈表的最后一個(gè)節點(diǎn)的Set里的數據都是舊數據了，可以安全的刪除了，當然這個(gè)刪除的時(shí)候應該是要鎖整個(gè)鏈表的。每個(gè)Set應該有個(gè)大小上限，比如20w，但set不能安全的遍歷，就不能得到當前大小，所以添加、刪除Set的數據的時(shí)候應該用Interlocked.Decrement()和 Interlocked.Increment()維護一個(gè)Count，一遍一個(gè)Set滿(mǎn)的時(shí)候，再到鏈表的頭新增一個(gè)Set節點(diǎn)。
性能測試腳本
class Program {
private static PerformanceCounter _addCounter;
private static PerformanceCounter _getCounter;
static void Main(string[] args) {
SetupCategory();
_addCounter = new PerformanceCounter("wawasoft.lrucache", "add/sec", false);
_getCounter = new PerformanceCounter("wawasoft.lrucache", "get/sec", false);
_addCounter.RawValue = 0;
_getCounter.RawValue = 0;
Random rnd = new Random();
const int max = 500 * 10000;
LRUCacheHelper<int, int> cache = new LRUCacheHelper<int, int>(200 * 10000, max);
for (int i = 10000*100000 - 1; i >= 0; i--)
{
if(i % 10 > 7)
{
ThreadPool.QueueUserWorkItem(
delegate
{
cache.Add(rnd.Next(0, 10000), 0);
_addCounter.Increment();
});
}
else
{
ThreadPool.QueueUserWorkItem(
delegate
{
int pop = cache.Get(i);
_getCounter.Increment();
});
}
}
Console.ReadKey();
}
private static void SetupCategory() {
if (!PerformanceCounterCategory.Exists("wawasoft.lrucache")) {
CounterCreationDataCollection CCDC = new CounterCreationDataCollection();
CounterCreationData addcounter = new CounterCreationData();
addcounter.CounterType = PerformanceCounterType.RateOfCountsPerSecond32;
addcounter.CounterName = "add/sec";
CCDC.Add(addcounter);
CounterCreationData getcounter = new CounterCreationData();
getcounter.CounterType = PerformanceCounterType.RateOfCountsPerSecond32;
getcounter.CounterName = "get/sec";
CCDC.Add(getcounter);
PerformanceCounterCategory.Create("wawasoft.lrucache","lrucache",CCDC);
}
}
}
參考鏈接
不分先后，都是隨時(shí)從網(wǎng)上找的，大多看不懂
潛心學(xué)習數據結構-C#語(yǔ)言描述系列文章
http://space.cnblogs.com/group/topic/6922/《C++數據結構原理與經(jīng)典問(wèn)題求解》
http://www.huachu.com.cn/itbook/bookinfodetail.asp?lbbh=10087298&sort=ml數據結構(C#)：循環(huán)鏈表
http://www.cnblogs.com/zxjay/archive/2008/12/07/1349688.html表的游標實(shí)現
http://www.comp.nus.edu.sg/~xujia/mirror/algorithm.myrice.com/datastructure/basic/list/chapter3_3.htm我所理解的鏈表1
http://www.diybl.com/course/3_program/c/csuanfa/2007213/21570.htmlcursor implementation of linked list
http://wiki.answers.com/Q/Explain_the_Cursor_implementation_of_linked_listSorting Algorithms In C#
http://www.codeproject.com/KB/recipes/cssorters.aspxThe C5 Generic Collection Library
http://www.itu.dk/research/c5/當弱引用對象成為集合元素時(shí)
http://www.agiledon.com/post/Coding/Weakreference-Collection-CSharp.htmlQuickSort in Functional C#
http://blogs.objectsharp.com/cs/blogs/jlee/archive/2008/05/23/quicksort-in-functional-c.aspxLRU頁(yè)面置換算法模擬
http://dev.csdn.net/article/73207.shtm
