程序猿修仙之路--數(shù)據(jù)結(jié)構(gòu)之設(shè)計(jì)高性能訪客記錄系統(tǒng)

cdn.xitu.io/2019/3/3/16941a949afab1ea?w=710&h=772&f=png&s=121666">

準(zhǔn)備加班中ing.....

需求要點(diǎn)

每個(gè)用戶都有自己的個(gè)人空間，當(dāng)有其他用戶來(lái)訪問(wèn)的時(shí)候，需要添加訪客記錄，并且更新為最新的訪客，這里設(shè)計(jì)到一個(gè)坑，如果存在這個(gè)用戶的訪問(wèn)記錄需要更新用戶的最后訪問(wèn)時(shí)間。那這個(gè)需求在技術(shù)維度來(lái)說(shuō)，有什么特點(diǎn)嗎？
先想10秒鐘，在接著往下看?。?！

有什么設(shè)計(jì)要點(diǎn)呢？

1. 用戶的訪客記錄一定要緩存，要不然怎么抗住大并發(fā)呢?
2. 由于最新的訪客記錄變化非?？欤幸环N能快速添加新數(shù)據(jù)，刪除老數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。

緩存的篇章今日暫且不說(shuō)，說(shuō)一下以上的第二點(diǎn)，也就引出了今日數(shù)據(jù)結(jié)構(gòu)主角：鏈表

鏈表百科：鏈表是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表屬于線性結(jié)構(gòu)。

鏈表分類

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

   public class Node<T>
   {
       //當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)元素
       public T Data { get; set; }
       //當(dāng)前節(jié)點(diǎn)的下一個(gè)元素
       public Node<T> NextNode { get; set; }
   }

2. 雙向鏈表：每個(gè)鏈表元素既有指向下一個(gè)元素的指針，又有指向前一個(gè)元素的指針，其中每個(gè)結(jié)點(diǎn)都有兩種指針。
   

   public class Node<T>
   {
       //當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
       public Node<T> PreNode { get; set; }
       //當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)元素
       public T Data { get; set; }
       //當(dāng)前節(jié)點(diǎn)的下一個(gè)元素
       public Node<T> NextNode { get; set; }
   }

3. 循環(huán)鏈表：指的是在單向鏈表和雙向鏈表的基礎(chǔ)上，將兩種鏈表的最后一個(gè)結(jié)點(diǎn)指向第一個(gè)結(jié)點(diǎn)從而實(shí)現(xiàn)循環(huán)。
   
   

特性

1. 元素的數(shù)量可以隨時(shí)擴(kuò)充。由于鏈表在物理的存儲(chǔ)單元上是非連續(xù)的，這就早就了它天生的優(yōu)勢(shì)，我的節(jié)點(diǎn)可以在任意符合要求的地方分配內(nèi)存。
2. 添加元素：
   單鏈表：當(dāng)在一個(gè)位置N之后插入新元素的時(shí)候，單鏈表首先把當(dāng)前位置N的元素的Next指針指向新的元素，然后新的元素的Next指針指向N+1位置的元素。當(dāng)然如果是在首位置插入新元素，只需要把新元素的Next指針指向鏈表的首元素即可，同理，如果要在單鏈表尾部插入新元素，只需要把單鏈表的尾部元素的Next指針指向新元素。至于循環(huán)單鏈表，無(wú)所謂首元素和尾元素之分。
   
   雙向鏈表：
   在位置N之后添加新元素和單鏈表原理類似，原理也是修改元素的指針指向。但是這里有一個(gè)不同，雙向鏈表要修改前后元素(N位置和N+1位置)和新元素三個(gè)Node的指針，所以略微麻煩一點(diǎn)。
   
3. 刪除元素：
   單鏈表：當(dāng)要?jiǎng)h除位置N的元素的時(shí)候，只需要把N-1位置元素的Next指針指向N+1即可。
   
   雙向鏈表：當(dāng)要?jiǎng)h除位置N的元素的時(shí)候，需要修改N-1位置元素的Next指針指向N+1元素，同時(shí)還要修改N+1位置元素的Pre指針指向N-1元素。
   
4. 查找元素：
   由于鏈表的元素在內(nèi)存中并非連續(xù)，所以不能像數(shù)組那樣擁有O（1）的查找時(shí)間復(fù)雜度，只能是通過(guò)首元素去遍歷鏈表，所以時(shí)間復(fù)雜度為O（n）

程序設(shè)計(jì)

給你10秒回到X總的需求中來(lái)。通過(guò)對(duì)鏈表的介紹，我們?cè)撨x擇哪種鏈表呢？這里我先說(shuō)一下我的思路，如有錯(cuò)誤請(qǐng)指正：

1. 當(dāng)一個(gè)訪客進(jìn)入個(gè)人空間的首頁(yè)時(shí)，大多數(shù)情況下，訪客記錄只需要緩存前100條或者200條即可，也就是說(shuō)這個(gè)場(chǎng)景是存在熱點(diǎn)數(shù)據(jù)的，80%（甚至更高）的請(qǐng)求命中在最近100條訪客數(shù)據(jù)上，很少人會(huì)去查看很久以前的記錄。所以基于占用內(nèi)存空間上的考慮，我決定緩存最近的100條訪客數(shù)據(jù)。
2. 假設(shè)我用鏈表緩存了前100條數(shù)據(jù)，其中在非首位置有一條訪客A的記錄，此時(shí)A又訪問(wèn)的這個(gè)用戶空間，我需要把A的記錄移到首位置，這個(gè)過(guò)程經(jīng)歷了刪除A數(shù)據(jù)，在首位置添加A數(shù)據(jù)。假如A開(kāi)始的位置是N，我在刪除N位置數(shù)據(jù)的時(shí)候，需要查找N-1的位置元素修改其指針指向，如果是單鏈表由于當(dāng)前位置N的元素中沒(méi)有N-1位置元素的信息，所有需要重新遍歷鏈表。如果是雙向鏈表呢，位置N的元素中保存了位置N-1的元素，所以沒(méi)有必要在重新遍歷鏈表了，這也是雙向鏈表對(duì)比單鏈表的優(yōu)勢(shì)，雖然內(nèi)存占用上多了一個(gè)指針的內(nèi)存大小，但是在實(shí)際的應(yīng)用場(chǎng)景中更為常用。所以我選擇雙向鏈表。刪除操作和添加操作時(shí)間復(fù)雜度都是O（1）.
3. 對(duì)同一個(gè)空間的訪問(wèn)，必然存在鎖和多線程的問(wèn)題。所以我在選擇框架的時(shí)候優(yōu)先選擇了基于Actor模型的框架。避免了在同一個(gè)用戶空間上加鎖的操作。
4. 由于基于Actor模型的框架，所以我沒(méi)有采用類似Redis這樣的進(jìn)程外緩存，而是采用了進(jìn)程內(nèi)緩存，畢竟網(wǎng)絡(luò)傳輸?shù)乃俣仍倏煲脖葍?nèi)存操作要慢的多。應(yīng)用層的Actor服務(wù)天然支持分布式。如果對(duì)actor 不太了解的同學(xué)可以度娘一下。

優(yōu)化

1. 閱讀到這里你是否感覺(jué)哪里有問(wèn)題呢？是的，就是鏈表元素的查找，由于只能是遍歷，所有鏈表查找元素的時(shí)間復(fù)雜度為O（n），那有沒(méi)有辦法優(yōu)化呢？那就是我們以后要講的另外一種數(shù)據(jù)結(jié)構(gòu)了。
2. 空間的訪客記錄是以時(shí)間為維度的倒序排列，所以業(yè)務(wù)以及DB時(shí)間列的設(shè)計(jì)類型推薦為UTC時(shí)間戳long類型，畢竟long類型在多數(shù)語(yǔ)言中比datetime類型占用內(nèi)存要小很多。
3. 無(wú)論是否使用緩存，用戶的訪問(wèn)記錄都是需要DB來(lái)持久化的，當(dāng)有大量的請(qǐng)求的時(shí)候，我們可以利用某種機(jī)制來(lái)批量持久化到DB，而不是一個(gè)請(qǐng)求就訪問(wèn)數(shù)據(jù)庫(kù)一次。
4. 當(dāng)對(duì)空間的訪客記錄實(shí)時(shí)性要求不是很高的時(shí)候，我們可以每10秒或者5秒更新緩存，也就是批量更新緩存，這比單條加鎖更新緩存效果更好。

X總的個(gè)人空間需求并沒(méi)有結(jié)束，菜菜仍然在持續(xù)優(yōu)化中，歡迎大佬指正！

添加關(guān)注，查看更精美版本，收獲更多精彩