程序猿修仙之路--數據結構之設計高性能訪客記錄系統

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

準備加班中ing.....

需求要點

每個用戶都有自己的個人空間，當有其他用戶來訪問的時候，需要添加訪客記錄，并且更新為最新的訪客，這里設計到一個坑，如果存在這個用戶的訪問記錄需要更新用戶的最后訪問時間。那這個需求在技術維度來說，有什么特點嗎？
先想10秒鐘，在接著往下看！！！

有什么設計要點呢？

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

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

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

鏈表分類

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秒更新緩存，也就是批量更新緩存，這比單條加鎖更新緩存效果更好。

X總的個人空間需求并沒有結束，菜菜仍然在持續優化中，歡迎大佬指正！

添加關注，查看更精美版本，收獲更多精彩