高性能訪客記錄系統如何設計？

需求要點

每個用戶都有自己的個人空間，當有其他用戶來訪問的時候，需要添加訪客記錄，並且更新為最新的訪客，這裡設計到一個坑，如果存在這個用戶的訪問記錄需要更新用戶的最後訪問時間。那這個需求在技術維度來說，有什麼特點嗎？

先想10秒鐘，再接著往下看！！！有什麼設計要點呢？

• 用戶的訪客記錄一定要緩存，要不然怎麼抗住大並發呢?
• 由於最新的訪客記錄變化非常快，要有一種能快速添加新數據，刪除老數據的數據結構。

緩存的篇章今日暫且不說，說一下以上的第二點，也就引出了今日數據結構主角：鏈表。

鏈表

鏈表百科：鏈表是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表屬於線性結構。

鏈表分類

1. 單鏈表：鏈表中的元素的指向只能指向鏈表中的下一個元素或者為空，元素之間不能相互指向。也就是一種線性鏈表。

public class Node<T>

{

//當前節點的數據元素

public T Data { get; set; }

//當前節點的下一個元素

public Node<T> NextNode { get; set; }

}

2. 雙向鏈表：每個鏈表元素既有指向下一個元素的指針，又有指向前一個元素的指針，其中每個結點都有兩種指針。

public class Node<T>

{

//當前節點的前一個節點

public Node<T> PreNode { get; set; }

//當前節點的數據元素

public T Data { get; set; }

//當前節點的下一個元素

public Node<T> NextNode { get; set; }

}

3. 循環鏈表：指的是在單向鏈表和雙向鏈表的基礎上，將兩種鏈表的最後一個結點指向第一個結點從而實現循環。

特性

1.元素的數量可以隨時擴充。由於鏈表在物理的存儲單元上是非連續的，這就早就了它天生的優勢，我的節點可以在任意符合要求的地方分配內存。

2. 添加元素：

單鏈表：

當在一個位置N之後插入新元素的時候，單鏈表首先把當前位置N的元素的Next指針指向新的元素，然後新的元素的Next指針指向N+1位置的元素。當然如果是在首位置插入新元素，只需要把新元素的Next指針指向鏈表的首元素即可，同理，如果要在單鏈表尾部插入新元素，只需要把單鏈表的尾部元素的Next指針指向新元素。至於循環單鏈表，無所謂首元素和尾元素之分。

雙向鏈表：

在位置N之後添加新元素和單鏈表原理類似，原理也是修改元素的指針指向。但是這裡有一個不同，雙向鏈表要修改前後元素(N位置和N+1位置)和新元素三個Node的指針，所以略微麻煩一點。

3. 刪除元素：

單鏈表：

當要刪除位置N的元素的時候，只需要把N-1位置元素的Next指針指向N+1即可。

雙向鏈表：

當要刪除位置N的元素的時候，需要修改N-1位置元素的Next指針指向N+1元素，同時還要修改N+1位置元素的Pre指針指向N-1元素。

4. 查找元素：

由於鏈表的元素在內存中並非連續，所以不能像數組那樣擁有O（1）的查找時間複雜度，只能是通過首元素去遍歷鏈表，所以時間複雜度為O（n）

程序設計

給你10秒回到X總的需求中來。通過對鏈表的介紹，我們該選擇哪種鏈表呢？這裡我先說一下我的思路，如有錯誤請指正：

1.當一個訪客進入個人空間的首頁時，大多數情況下，訪客記錄只需要緩存前100條或者200條即可，也就是說這個場景是存在熱點數據的，80%（甚至更高）的請求命中在最近100條訪客數據上，很少人會去查看很久以前的記錄。所以基於佔用內存空間上的考慮，我決定緩存最近的100條訪客數據。

2. 假設我用鏈表緩存了前100條數據，其中在非首位置有一條訪客A的記錄，此時A又訪問的這個用戶空間，我需要把A的記錄移到首位置，這個過程經歷了刪除A數據，在首位置添加A數據。假如A開始的位置是N，我在刪除N位置數據的時候，需要查找N-1的位置元素修改其指針指向，如果是單鏈表由於當前位置N的元素中沒有N-1位置元素的信息，所有需要重新遍歷鏈表。如果是雙向鏈表呢，位置N的元素中保存了位置N-1的元素，所以沒有必要在重新遍歷鏈表了，這也是雙向鏈表對比單鏈表的優勢，雖然內存佔用上多了一個指針的內存大小，但是在實際的應用場景中更為常用。所以我選擇雙向鏈表。刪除操作和添加操作時間複雜度都是O（1）.

3.對同一個空間的訪問，必然存在鎖和多線程的問題。所以我在選擇框架的時候優先選擇了基於Actor模型的框架。避免了在同一個用戶空間上加鎖的操作。

4.由於基於Actor模型的框架，所以我沒有採用類似Redis這樣的進程外緩存，而是採用了進程內緩存，畢竟網路傳輸的速度再快也比內存操作要慢的多。應用層的Actor服務天然支持分散式。如果對actor 不太了解的同學可以度娘一下。

優化

1. 閱讀到這裡你是否感覺哪裡有問題呢？是的，就是鏈表元素的查找，由於只能是遍歷，所有鏈表查找元素的時間複雜度為O（n），那有沒有辦法優化呢？那就是我們以後要講的另外一種數據結構了。

2.空間的訪客記錄是以時間為維度的倒序排列，所以業務以及DB時間列的設計類型推薦為UTC時間戳long類型，畢竟long類型在多數語言中比datetime類型佔用內存要小很多。

3.無論是否使用緩存，用戶的訪問記錄都是需要DB來持久化的，當有大量的請求的時候，我們可以利用某種機制來批量持久化到DB，而不是一個請求就訪問資料庫一次。

4.當對空間的訪客記錄實時性要求不是很高的時候，我們可以每10秒或者5秒更新緩存，也就是批量更新緩存，這比單條加鎖更新緩存效果更好。

把用戶訪問記錄優化到極致

但是，在用戶訪問記錄的緩存中怎麼來判斷是否有當前用戶的記錄呢？鏈表雖然是我們這個業務場景最主要的數據結構，但並不是當前這個問題最好的解決方案，所以我們需要一種能快速訪問元素的數據結構來解決這個問題？那就是今天我們要談一談的——散列表。

散列表

散列表（Hash table，也叫哈希表），是根據關鍵碼值(Key value)而直接進行訪問的數據結構。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數叫做散列函數，存放記錄的數組叫做散列表。

散列表其實可以約等於我們常說的Key-Value形式。散列表用的是數組支持按照下標隨機訪問數據的特性，所以散列表其實就是數組的一種擴展，由數組演化而來。可以說，如果沒有數組，就沒有散列表。為什麼要用數組呢？因為數組按照下標來訪問元素的時間複雜度為O（1），不明白的同學可以參考菜菜以前的關於數組的文章。

既然要按照數組的下標來訪問元素，必然也必須考慮怎麼樣才能把Key轉化為下標。這就是接下來要談一談的散列函數。

散列函數

散列函數通俗來講就是把一個Key轉化為數組下標的黑盒。散列函數在散列表中起著非常關鍵的作用。散列函數，顧名思義，它是一個函數。我們可以把它定義成hash(key)，其中 key 表示元素的鍵值，hash(key) 的值表示經過散列函數計算得到的散列值。

那一個散列函數有哪些要求呢？

• 散列函數計算得到的值是一個非負整數值；
• 如果 key1 = key2，那hash(key1) == hash(key2) ；
• 如果 key1 ≠ key2，那hash(key1) ≠ hash(key2) 。

簡單說一下以上三點，第一點：因為散列值其實就是數組的下標，所以必須是非負整數（>=0），第二點：同一個key計算的散列值必須相同。重點說一下第三點，其實第三點只是理論上的，我們想像著不同的Key得到的散列值應該不同，但是事實上，這一點很難做到。我們可以反證一下，如果這個公式成立，我計算無限個Key的散列值，那散列表底層的數組必須做到無限大才行。像業界比較著名的MD5、SHA等哈希演算法，也無法完全避免這樣的衝突。當然如果底層的數組越小，這種衝突的幾率就越大。

所以一個完美的散列函數其實是不存在的，即便存在，付出的時間成本，人力成本可能超乎想像。

散列衝突

既然再好的散列函數都無法避免散列衝突，那我們就必須尋找其他途徑來解決這個問題。

1. 定址

如果遇到衝突的時候怎麼辦呢？方法之一是在衝突的位置開始找數組中空餘的空間，找到空餘的空間然後插入。就像你去商店買東西，發現東西賣光了，怎麼辦呢？找下一家有東西賣的商家買唄。不管採用哪種探測方法，當散列表中空閑位置不多的時候，散列衝突的概率就會大大提高。為了儘可能保證散列表的操作效率，一般情況下，我們會儘可能保證散列表中有一定比例的空閑槽位。我們用裝載因子（load factor）來表示空位的多少。

散列表的裝載因子 = 填入表中的元素個數 / 散列表的長度

裝載因子越大，說明空閑位置越少，衝突越多，散列表的性能會下降。假設散列函數為 f=(key%1000)。如下圖所示：

2. 鏈地址法（拉鏈法）

拉鏈法屬於一種最常用的解決散列值衝突的方式。基本思想是數組的每個元素指向一個鏈表，當散列值衝突的時候，在鏈表的末尾增加新元素。查找的時候同理，根據散列值定位到數組位置之後，然後沿著鏈表查找元素。如果散列函數設計的非常糟糕的話，相同的散列值非常多的話，散列表元素的查找會退化成鏈表查找，時間複雜度退化成O（n）。

3. 再散列法

這種方式本質上是計算多次散列值，那就必然需要多個散列函數，在產生衝突時再使用另一個散列函數計算散列值，直到衝突不再發生，這種方法不易產生「聚集」，但增加了計算時間。

4. 建立一個公共溢出區

至於這種方案網路上介紹的比較少，一般應用的也比較少。可以這樣理解：散列值衝突的元素放到另外的容器中，當然容器的選擇有可能是數組，有可能是鏈表甚至隊列都可以。但是無論是什麼，想要保證散列表的優點還是需要慎重考慮這個容器的選擇。

寫在後面

1. 這裡需要再強調一次，散列表底層依賴的是數組按照下標訪問的特性（時間複雜度為O(1）），而且一般散列表為了避免大量衝突都有裝載因子的定義，這就涉及到了數組擴容的特性：需要為新數組開闢空間，並且需要把元素copy到新數組。如果我們知道數據的存儲量或者數據的大概存儲量，在初始化散列表的時候，可以盡量一次性分配足夠大的空間。避免之後的數組擴容弊端。事實證明，在內存比較緊張的時候，優先考慮這種一次性分配的方案也要比其他方案好的多。

2. 散列表的定址方案中，有一種特殊情況：如果我尋找到數組的末尾仍然無空閑位置，怎麼辦呢？這讓我想到了循環鏈表，數組也一樣，可以組裝一個循環數組。末尾如果無空位，就可以繼續在數組首位繼續搜索。

3. 關於散列表元素的刪除，我覺得有必要說一說。首先基於拉鏈方式的散列表由於元素在鏈表中，所有刪除一個元素的時間複雜度和鏈表是一樣的，後續的查找也沒有任何問題。但是定址方式的散列表就不同了，我們假設一下把位置N元素刪除，那N之後相同散列值的元素就搜索不出來了，因為N位置已經是空位置了。散列表的搜索方式決定了空位置之後的元素就斷片了....這也是為什麼基於拉鏈方式的散列表更常用的原因之一吧。

4. 在工業級的散列函數中，元素的散列值做到盡量平均分布是其中的要求之一，這不僅僅是為了空間的充分利用，也是為了防止大量的hashCode落在同一個位置，設想在拉鏈方式的極端情況下，查找一個元素的時間複雜度退化成在鏈表中查找元素的時間複雜度O（n），這就導致了散列表最大特性的丟失。

5. 拉鏈方式實現的鏈表中，其實我更傾向於使用雙向鏈表，這樣在刪除一個元素的時候，雙向鏈表的優勢可以同時發揮出來，這樣可以把散列表刪除元素的時間複雜度降低為O（1）。

6. 在散列表中，由於元素的位置是散列函數來決定的，所有遍歷一個散列表的時候，元素的順序並非是添加元素先後的順序，這一點需要我們在具體業務應用中要注意。

Net Core c# 代碼

有幾個地方需要再強調一下：

1. 在當前項目中用的分散式框架為基於Actor模型的Orleans，所以我每個用戶的訪問記錄不必擔心多線程問題；

2. 我沒用使用hashtable這個數據容器，是因為hashtable太容易發生裝箱拆箱的問題；

3. 使用雙向鏈表是因為查找到了當前元素，相當於也查找到了上個元素和下個元素，當前元素的刪除操作時間複雜度可以為O(1)。

class UserViewInfo
{
//用戶ID
public int UserId { get; set; }
//訪問時間，utc時間戳
public int Time { get; set; }
//用戶姓名
public string UserName { get; set; }
}
class UserSpace
{
//緩存的最大數量
const int CacheLimit = 1000;
//這裡用雙向鏈表來緩存用戶空間的訪問記錄
LinkedList<UserViewInfo> cacheUserViewInfo = new LinkedList<UserViewInfo>();
//這裡用哈希表的變種Dictionary來存儲訪問記錄，實現快速訪問，同時設置容量大於緩存的數量限制，減小哈希衝突
Dictionary<int, UserViewInfo> dicUserView = new Dictionary<int, UserViewInfo>(1250);
//添加用戶的訪問記錄
public void AddUserView(UserViewInfo uv)
{
//首先查找緩存列表中是否存在，利用hashtable來實現快速查找
if (dicUserView.TryGetValue(uv.UserId, out UserViewInfo currentUserView))
{
//如果存在，則把該用戶訪問記錄從緩存當前位置移除，添加到頭位置
cacheUserViewInfo.Remove(currentUserView);
cacheUserViewInfo.AddFirst(currentUserView);
}
else
{
//如果不存在，則添加到緩存頭部 並添加到哈希表中
cacheUserViewInfo.AddFirst(uv);
dicUserView.Add(uv.UserId, uv);
}
//這裡每次都判斷一下緩存是否超過限制
if (cacheUserViewInfo.Count > CacheLimit)
{
//移除緩存最後一個元素，並從hashtable中刪除,理論上來說，dictionary的內部會兩個指針指向首元素和尾元素，所以查找這兩個元素的時間複雜度為O（1）
var lastItem = cacheUserViewInfo.Last.Value;
dicUserView.Remove(lastItem.UserId);
cacheUserViewInfo.RemoveLast();
}
}
}

作者：菜菜，一個奔走在通往互聯網更高之路的工程師，熱衷於互聯網技術。目前就職於某互聯網教育公司，應用服務端主要負責人。擁有10年+互聯網開發經驗，熱衷於高性能、高並發、分散式技術領域的研究，主要工作語言為C#和Golang 。

聲明：本文為作者投稿，版權歸其個人所有，責編郭芮。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！