成都創(chuàng)新互聯(lián)是一家專注于網(wǎng)站制作、做網(wǎng)站與策劃設(shè)計(jì),恩平網(wǎng)站建設(shè)哪家好?成都創(chuàng)新互聯(lián)做網(wǎng)站,專注于網(wǎng)站建設(shè)10余年,網(wǎng)設(shè)計(jì)領(lǐng)域的專業(yè)建站公司;建站業(yè)務(wù)涵蓋:恩平等地區(qū)。恩平做網(wǎng)站價(jià)格咨詢:18980820575

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

需求要點(diǎn)

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

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

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

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

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

鏈表分類

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

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

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

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

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

特性

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

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

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

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

優(yōu)化

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

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

---

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

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

文章標(biāo)題：程序猿修仙之路--數(shù)據(jù)結(jié)構(gòu)之設(shè)計(jì)高性能訪客記錄系統(tǒng)-創(chuàng)新互聯(lián)
網(wǎng)站網(wǎng)址：http://weahome.cn/article/jghgi.html