Shopee蝦皮SRE工程師一面面經

2020.08.31，大概面了一個小時左右，其中半小時在做算法（而且還沒做出來，我真是太菜了），之後狀态就不是很好，感覺面試官想考察的點總是get不到，表達也不是特别專業性。面試官感覺有些嚴肅，但是我回答不上來的地方也會和我說沒事給一些提示給我，總的來說作為春招以來過了這麼久第一場面試，還是挺有收獲的

1. 自我介紹

2. 平時用什麼語言，寫一道算法題

一開始看到 O ( n l o g n ) O(nlogn) O(nlogn) 我也覺得是快排或者歸并，可是由于是連結清單沒想出來如何二分且是常數級空間複雜度，後來征求了面試官同意後使用暴力解法也沒有很快解出來，面試官就讓我說思路了，當時想是用字典映射連結清單中的節點位置以及對應值再進行排序，但會占用額外 O ( n ) O(n) O(n) 的空間，出來看到别人歸并的題解才知道這麼簡單

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
    	# 遞歸傳回條件
        if not head or not head.next:
            return head
        # 使用快慢指針，當快指針到終點時慢指針的位置剛好是一半，時間複雜度為O(logn)
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        # 将連結清單cut成兩端，兩邊遞歸
        mid, slow.next = slow.next, None
        left, right = self.sortList(head), self.sortList(mid)
        # 使用一個節點作為傳回連結清單的頭節點，将排序好的連結清單逐個判斷插入傳回連結清單中
        h = res = ListNode(0)
        while left and right:
            if left.val < right.val:
                h.next = left
                left = left.next
            else:
                h.next = right
                right = right.next
            h = h.next
        # 左連結清單或右連結清單周遊完後，另一半直接插入到最末尾
        h.next = left if left else right
        return res.next
           

3. 程序和線程了解過嗎，他們有什麼差別，優缺點，應用場景是什麼

算法沒做出來腦子就卡殼了，許多詞就硬是不知道怎麼表達

• 程序是作業系統配置設定資源的最小機關；線程是作業系統排程的最小機關
• 一個程序可以有一個或多個線程；一個線程隻屬于一個程序
• 程序之間互相隔離，互不幹擾；同個程序間的多個線程共享程序資源
• 程序切換時的代價比線程高得多
• 多線程隻要有一個線程崩潰，整個程序就可能崩潰；多程序中的一個程序崩潰并不影響其他程序
• 提了一下PIL，但是沒有說好：python中的多線程是僞并行，線程在執行時需要擷取程序的PIL，一個程序隻有一把鎖，隻有擷取鎖的線程才能運作，其他線程必須等待，是以python中的多線程無法排程到各個處理器上進行并行運作
• 多程序适用于CPU密集型任務，多程序可以充分發揮出多核處理器的性能，将各個程序排程到不同處理器上運作；多線程适用于IO密集型任務，每當一個線程阻塞時處理器就會排程到下一個線程繼續執行，而線程排程的消耗是比程序排程小得多的

4. 程序線程排程時的上下文了解嗎

這個不會

5. 核心态和使用者态了解嗎

當在系統中執行一個程式時，大部分時間是運作在使用者态下的，在其需要作業系統幫助完成一些使用者态自己沒有特權和能力完成的操作時就會切換到核心态。這裡應該是想問虛拟化中的Ring0~Ring3，當時沒get到

6. 僵屍程序和孤兒程序是什麼

• 僵屍程序：一個子程序結束後，它的父程序并沒有等待它（調用wait或者waitpid），那麼這個子程序将成為一個僵屍程序。僵屍程序是一個已經死亡的程序，但是并沒有真正被銷毀。它已經放棄了幾乎所有記憶體空間，沒有任何可執行代碼，也不能被排程，僅僅在程序表中保留一個位置，記載該程序的程序ID、終止狀态以及資源利用資訊(CPU時間，記憶體使用量等等)供父程序收集，除此之外，僵屍程序不再占有任何記憶體空間。這個僵屍程序可能會一直留在系統中直到系統重新開機。
• 孤兒程序：一個父程序已經結束了，但是它的子程序還在運作，那麼這些子程序将成為孤兒程序。孤兒程序會被Init（程序ID為1）接管，當這些孤兒程序結束時由Init完成狀态收集工作。

7. docker是什麼，和虛拟機有什麼不同

docker作為“小型虛拟機”，是虛拟化的一種産物，與虛拟機不同的是，docker中的容器并不依賴于特定的環境，而是“build once，run anywhere”。docker利用namespace的隔離技術，将容器與容器、容器與主控端隔離開來，而每個程式在容器内部仿佛都像是在一個完整的作業系統，對主控端環境并無感覺。而作為主控端中的程序，容器能發揮的性能接近于原生（這裡一開始說錯說成了比原生若，後來才想起來是虛拟機的性能弱于原生）

8. docker的資源隔離是怎麼做到的

docker使用了核心提供的namespace隔離技術，實作容器間的資源隔離，現有6種namespace：

• PID：不同程序就是通過PID進行劃分的，不同namespace中的PID都是獨立的，并且可以與其他命名空間的相同
• NET：隔離網絡，每個NET命名空間中都有獨立的網絡裝置、ip位址、路由等
• IPC：程序間通信，讓容器内擁有自己的程序間通信方式
• UTS：unix time-sharing systemc，讓容器可以擁有自己的主機名和域名
• MNT：類似于 change root，讓容器内看起來仿佛是個完整的檔案系統
• USER：容器内可以擁有自己的使用者，并且于主控端的使用者是隔離的

9. MySQL的存儲引擎

因為面試前看了一篇關于B+數結構的文章，滿腦子都是B+樹，沒答好，續多Innodb的特性都沒答到

InnoDB是MySQL目前預設的存儲引擎，底層使用了B+樹作為資料結構，與MyiSAM不同的時，InnoDB屬于聚集索引，主鍵和資料一起存儲在B+樹的葉子節點中，而MyiSAM的主鍵和資料是分開存儲的，葉子節點中存儲的是資料所在的位址。InnoDB和MyiSAM的差別：

• 存儲方式：前者索引和資料共存于一個檔案中；後者索引和資料分開存儲
• 鎖粒度：前者支援行鎖（MVCC特性)；而後者僅支援到表鎖
• 事務支援：前者支援事務；後者不支援事務
• 對于寫多的場景，由于MyiSAM需要頻繁的鎖表，性能開銷比InnoDB大得多
• 對于讀多寫少的場景，由于InnoDB每次操作都需要在事務中，MyiSAM的性能可能會比前者好

這上面的都沒答到，我答的是下面的。。。：

InnoDB的資料結構是B+樹，根據B+樹的特點，所有查詢都是等時的，且因為資料都存在葉子節點上，而葉子節點又是經過排序的，在範圍查詢場景中這種資料結構就顯得十分友善，隻需要雙指針定位範圍起點終點，中間的資料就是我們想要的；而對于hash索引來說，由于鍵映射的值隻是資料的位址位置，無法看到資料中具體的值，在範圍查詢的場景中就隻能全表搜尋了

MySQL為了加快資料存取速度，最小機關不使用檔案系統中的塊，而是使用連續4個塊作為一個頁（16k），而在InnoDB中，B+樹存儲的内容是：

• 非葉子節點：key+指針
• 葉子節點：資料行

對于葉子節點，假設一行資料存儲需要1k（對普通業務絕對夠了），那麼一頁就可以存儲6行資料

對于非葉子節點，假設使用bitint（8位元組）作為主鍵，MySQL中的指針大小為6位元組，一共是14位元組，一頁大概能存 16 ∗ 1024 / 14 = 1170 16*1024/14=1170 16∗1024/14=1170（個）key，一棵高度為3的B+樹就能存儲 1170 ∗ 1170 ∗ 6 = 21902400 1170*1170*6=21902400 1170∗1170∗6=21902400（千萬級），是以InnoDB中一半樹的高度為3就能滿足千萬資料量的需求

10. 看你履歷上說你用過Mycat，你認為為什麼要分庫分表呢

分庫分表的目的都是為了防止海量資料存儲在單台伺服器上造成的單點性能問題，Mycat作為分布式中間件，可以讓我們的真實資料庫伺服器存儲不同的庫表，而在使用者通路Mycat時并感覺不到後端資料的分布，就像是通路原先存儲所有資料的資料庫一樣，但實際的請求會根據真實資料所處位置打到不同的資料庫中

11. 表分片又是為了什麼

雖然分庫分表已經較好的解決了單點性能問題，但是随着業務量的日益增長，我們的表也是會越來越大的，也會導緻資料庫的性能問題，是以将表按一定的規則劃分，分别存儲在不同資料庫中，再由Mycat對使用者請求進行分流，這就解決了表越來越大所造成的問題了

12. 表分片有什麼問題

• 拆分規則難以抽象
• 分片事務一緻性難以解決
• 資料多次擴充難度跟維護量極大
• 跨庫join性能差（重點是這個，後面的題也是想提這個，我又沒get到)

13. 你認為Mycat的适用和不适用的場景有哪些

沒有get到跨庫性能問題，就答了上面說的上面業務量過大表過大庫過大導緻單點性能問題做成分布式減輕壓力。。。然後不适用就答了小庫小表劃分反而會造成徒增運維成本，最後面試官提了一句跨庫的性能問題我才想起來，然後答了Mycat中的全局表和ER表，又嗯了半天不知道怎麼表達，面試官就說了我大概了解你的意思了，真是太菜了我

反問：不好意思問了就問了學習上的建議

面試官說我學的還可以，問題應該還是實踐不多，缺少總結經驗，很多細節沒法關聯起來，建議我多實踐。因為自己學習基本上都是在虛拟機上做的，沒辦法模拟出真正生産中的各種問題，面試官說這行可能比較吃經驗，這方面的話可以多看看别人寫的博文，多看看人家怎麼想的，自己再多總結。