資料結構相關
1. 介紹一下哈希表
散清單（Hash table，也叫哈希表），是根據關鍵碼值(Key value)而直接進行通路的資料結構。也就是說，它通過把關鍵碼值映射到表中一個位置來通路記錄，以加快查找的速度。這個映射函數叫做散列函數，存放記錄的數組叫做散清單。 散列函數能使對一個資料序列的通路過程更加迅速有效，通過散列函數，資料元素将被更快地定位。 常見的散列函數有：
- 直接尋址法
取關鍵字或關鍵字的某個線性函數值為散列位址
- 平方取中法
當無法确定關鍵字中哪幾位分布較均勻時，可以先求出關鍵字的平方值，然後按需要取平方值的中間幾位作為哈希位址
- 随機數法
擇一随機函數，取關鍵字的随機值作為散列位址，通常用于關鍵字長度不等的場合
- 除留餘數法
取關鍵字被某個不大于散清單表長m的數p除後所得的餘數為散列位址。即 H(key) = key % p, p <= m
2. 怎麼解決哈希沖突
- 開放尋址法 -- 當發生哈希沖突後，就去尋找下一個空的散列位址，隻要散清單足夠大，這個空的位置一定能找到
線性探測: 此時這個位置已經存在數，那麼就繼續對下一個位置進行探測，當到表尾時還沒有空位置，此時就傳回表頭繼續找尋空位置 二次探測: Hi=(H(key) + di) MOD m, 每次查找的是距離上一個為 i^2 個距離的位置
- 再散列法
當散清單元素太多（即裝填因子 α 太大）時，查找效率會下降；當裝填因子過大時，解決的方法是加倍擴大散清單，這個過程叫做“再散列（Rehashing）”。Hash 表中每次發現 loadFactor==1 時，就開辟一個原來桶數組的兩倍空間（稱為新桶數組），然後把原來的桶數組中元素全部轉移過來到新的桶數組中。注意這裡轉移是需要元素一個個重新哈希到新桶中的。實用最大裝填因子一般取 0.5 <= α<= 0.85
- 鍊位址法
當發生沖突時，該位置上的資料會用連結清單鍊起來，當表中的某些位置沒有結點時，該位置就為 NULL
- 公共溢出區 為所有沖突的關鍵字記錄建立一個公共的溢出區來存放。在查找時，對給定關鍵字通過散列函數計算出散列位址後，先與基本表的相應位置進行比對，如果相等，則查找成功；如果不相等，則到溢出表進行順序查找。如果相對于基本表而言，在有沖突的資料很少的情況下，公共溢出區的結構對查找性能來說還是非常高的。
3. 哈希表的擴容
假設以數組形式存放哈希表，當數組中元素過多時，可能會導緻接下來存放資料時多次遇到沖突且尋找資料時也會遇到同樣的問題。這時哈希表引入了一個裝填因子(元素個數/數組長度)，當裝填因子越大，表明數組可能存在的沖突越多，越需要擴容，實用的裝填因子大小為0.5-0.85。當裝填因子過大時，就需要考慮為哈希表進行擴容，一般來說，擴容選擇二倍的目前容量，一方面可以快速的進行位運算，另一方面能夠減少再哈希的沖突。需要注意的是，擴容的時候，原哈希表中的元素需要重新進行哈希。顯然，再哈希是個非常耗時的問題，引入了漸進式rehash。以下是哈希表漸進式 rehash 的詳細步驟：
- 為 ht[1] 配置設定空間， 讓字典同時持有 ht[0] 和 ht[1] 兩個哈希表。 *在字典中維持一個索引計數器變量 rehashidx ， 并将它的值設定為 0 ， 表示 rehash 工作正式開始。
- 在 rehash 進行期間， 每次對字典執行添加、删除、查找或者更新操作時， 程式除了執行指定的操作以外， 還會順帶将 ht[0] 哈希表在 rehashidx 索引上的所有鍵值對 rehash 到 ht[1] ， 當 rehash 工作完成之後， 程式将 rehashidx 屬性的值增一。
- 随着字典操作的不斷執行， 最終在某個時間點上， ht[0] 的所有鍵值對都會被 rehash 至 ht[1] ， 這時程式将 rehashidx 屬性的值設為 -1 ， 表示 rehash 操作已完成。
4. 數組和連結清單的差別
- 數組必須事先定義固定的長度（元素個數），不能适應資料動态地增減的情況，即數組的大小一旦定義就不能改變。當資料增加時，可能超出原先定義的元素個數；當資料減少時，造成記憶體浪費；連結清單動态地進行存儲配置設定，可以适應資料動态地增減的情況，且可以友善地插入、删除資料項。（數組中插入、删 除資料項時，需要移動其它資料項）。
- （靜态)數組從棧中配置設定空間（用 new 建立的在堆中）, 對于程式員友善快速,但是自由度小；連結清單從堆中配置設定空間, 自由度大但是申請管理比較麻煩。
- 數組在記憶體中是連續存儲的，是以，可以利用下标索引進行随機通路；連結清單是鍊式存儲結構，在通路元素的時候隻能通過線性的方式由前到後順序通路，是以通路效率比數組要低。
5. 二叉樹、二叉搜尋樹、平衡二叉樹、紅黑樹
- 二叉樹特點是每個結點最多隻能有兩棵子樹，且有左右之分。
- 二叉查找樹（Binary Search Tree），（又：二叉搜尋樹，二叉排序樹）它或者是一棵空樹，或者是具有下列性質的二叉樹： 若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值； 若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；它的左、右子樹也分别為二叉排序樹。
- 平衡二叉樹（AVL）。它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。這個方案很好的解決了二叉查找樹退化成連結清單的問題，把插入，查找，删除的時間複雜度最好情況和最壞情況都維持在O(logN)。但是頻繁旋轉會使插入和删除犧牲掉O(logN)左右的時間，不過相對二叉查找樹來說，時間上穩定了很多
- 紅黑樹。一種二叉查找樹，但在每個節點增加一個存儲位表示節點的顔色，可以是紅或黑（非紅即黑）。通過對任何一條從根到葉子的路徑上各個節點着色的方式的限制，紅黑樹確定沒有一條路徑會比其它路徑長出兩倍，是以，紅黑樹是一種弱平衡二叉樹（由于是弱平衡，可以看到，在相同的節點情況下，AVL樹的高度低于紅黑樹），相對于要求嚴格的AVL樹來說，它的旋轉次數少，是以對于搜尋，插入，删除操作較多的情況下，我們就用紅黑樹。 性質：1. 每個節點非紅即黑 2. 根節點是黑的; 3. 每個葉節點（葉節點即樹尾端NULL指針或NULL節點）都是黑的; 4. 如果一個節點是紅的，那麼它的兩兒子都是黑的; 5. 對于任意節點而言，其到葉子點樹NULL指針的每條路徑都包含相同數目的黑節點; 6. 每條路徑都包含相同的黑節點。
- 平衡二叉樹和紅黑樹對比。 結構對比： AVL 的結構高度平衡，RBT 的結構基本平衡。平衡度 AVL > RBT。 查找對比： AVL 查找時間複雜度最好，最壞情況都是 O(logN)。RBT 查找時間複雜度最好為 O(logN)，最壞情況下比 AVL 略差。 插入删除對比： 1. AVL 的插入和删除結點很容易造成樹結構的不平衡，而 RBT 的平衡度要求較低。是以在大量資料插入的情況下，RBT 需要通過旋轉變色操作來重新達到平 衡的頻度要小于 AVL。2. 如果需要平衡處理時，RBT 比 AVL 多一種變色操作，而且變色的時間複雜度在 O(logN)數量級上。但是由于操作簡單，是以在實踐中這種變色仍然是非常快速的。3. 當插入一個結點引起了樹的不平衡，AVL 和 RBT 都最多需要 2 次旋轉操作。但删除一個結點引起不平衡後，AVL 最多需要 logN 次旋轉操作，而 RBT 最多隻需要 3 次。是以兩者插入一個結點的代價差不多，但删除一個結點的代價 RBT要低一些。4. AVL 和 RBT 的插入删除代價主要還是消耗在查找待操作的結點上。是以時間複雜度基本上都是與 O(logN) 成正比的。 總體評價：大量資料實踐證明，RBT 的總體統計性能要好于平衡二叉樹。 紅黑樹詳解
6. B樹、B+樹
B 樹：
- 一種二叉搜尋樹。
- 除根節點外的所有非葉節點至少含有（M/2（向上取整）-1）個關鍵字，每個節點最多有M-1個關鍵字，并且以升序排列。是以M階B樹的除根節點外的所有非葉節點的關鍵字取值區間為[M/2-1(向上取整),M-1]。
- 每個葉節點最多有M-1個關鍵字。
B+樹：
- 有n棵子樹的非葉子結點中含有n個關鍵字（b樹是n-1個），這些關鍵字不儲存資料，隻用來索引，所有資料都儲存在葉子節點（b樹是每個關鍵字都儲存資料）。
- 所有的葉子結點中包含了全部關鍵字的資訊，及指向含這些關鍵字記錄的指針，且葉子結點本身依關鍵字的大小自小而大順序連結（葉子節點組成一個連結清單）。
- 所有的非葉子結點可以看成是索引部分，結點中僅含其子樹中的最大（或最小）關鍵字。
- 通常在b+樹上有兩個頭指針，一個指向根結點，一個指向關鍵字最小的葉子結點。
- 同一個數字會在不同節點中重複出現，根節點的最大元素就是b+樹的最大元素。
B樹與B+樹的差別：
- B樹每個節點都存儲資料，所有節點組成這棵樹。B+樹隻有葉子節點存儲資料（B+數中有兩個頭指針：一個指向根節點，另一個指向關鍵字最小的葉節點），葉子節點包含了這棵樹的所有資料，所有的葉子結點使用連結清單相連，便于區間查找和周遊，所有非葉節點起到索引作用。
- B樹中葉節點包含的關鍵字和其他節點包含的關鍵字是不重複的，B+樹的索引項隻包含對應子樹的最大關鍵字和指向該子樹的指針，不含有該關鍵字對應記錄的存儲位址。
- B樹中每個節點（非根節點）關鍵字個數的範圍為m/2(向上取整)-1,m-1，并且具有n個關鍵字的節點包含（n+1）棵子樹。B+樹中每個節點（非根節點）關鍵字個數的範圍為m/2(向上取整),m，具有n個關鍵字的節點包含（n）棵子樹。
- B+樹中查找，無論查找是否成功，每次都是一條從根節點到葉節點的路徑。
B樹的優點:
- B樹的每一個節點都包含key和value，是以經常通路的元素可能離根節點更近，是以通路也更迅速。
B+樹的優點：
- 所有的葉子結點使用連結清單相連，便于區間查找和周遊。B樹則需要進行每一層的遞歸周遊。相鄰的元素可能在記憶體中不相鄰，是以緩存命中性沒有B+樹好。
- b+樹的中間節點不儲存資料，能容納更多節點元素。
B樹與B+樹的共同優點：
- 考慮磁盤IO的影響，它相對于記憶體來說是很慢的。資料庫索引是存儲在磁盤上的，當資料量大時，就不能把整個索引全部加載到記憶體了，隻能逐一加載每一個磁盤頁（對應索引樹的節點）。是以我們要減少IO次數，對于樹來說，IO次數就是樹的高度，而“矮胖”就是b樹的特征之一，m的大小取決于磁盤頁的大小。
B樹和B+樹簡介
資料庫相關
1. ACID
原子性：指事務是一個不可再分割的工作機關，事務中的操作要麼都發生，要麼都不發生。事務在執行過程中發生錯誤，會被復原（Rollback）到事務開始前的狀态，就像這個事務從來沒有執行過一樣 一緻性：指事務使得系統從一個一緻的狀态轉換到另一個一緻狀态。這是說資料庫事務不能破壞關系資料的完整性以及業務邏輯上的一緻性 隔離性：多個事務并發通路時，事務之間是隔離的，一個事務不應該影響其它事務運作效果。這指的是在并發環境中，當不同的事務同時操縱相同的資料時，每個事務都有各自的完整資料空間。由并發事務所做的修改必須與任何其他并發事務所做的修改隔離。 持久性：意味着在事務完成以後，該事務所對資料庫所作的更改便持久的儲存在資料庫之中，并不會被復原。即使出現了任何事故比如斷電等，事務一旦送出，則持久化儲存在資料庫中。
2. 四種隔離級别以及 MySQL 的預設隔離級别
READ UNCIMMITTED（讀未送出） 事務中的修改，即使沒有送出，其他事務也可以看得到。會出現髒讀現象 READ COMMITTED（讀送出）大多數資料庫系統的預設隔離級别是 READ COMMITTED（mySQL 不是），這種隔離級别就是一個事務的開始，隻能看到已經完成的事務的結果，正在執行的，是無法被其他事務看到的。這種級别會出現讀取舊資料的現象 REPEATABLE READ（可重複讀）REPEATABLE READ 解決了髒讀的問題，該級别保證了每行的記錄的結果是一緻的，也就是上面說的讀了舊資料的問題，但是卻無法解決另一個問題，幻行 SERIALIZABLE（可串行化）SERIALIZABLE 是最高的隔離級别，它通過強制事務串行執行（注意是串行），避免了前面的幻讀情況，由于他大量加上鎖，導緻大量的請求逾時，是以性能會比較底下，再特别需要資料一緻性且并發量不需要那麼大的時候才可能考慮這個隔離級别。
MYSQL的預設隔離級别是可重複讀級别。
3. MYSQL怎麼實作多版本(MVCC)的
詳細
MVCC就是為了實作讀-寫沖突不加鎖，而這個讀指的就是快照讀, 而非目前讀，目前讀實際上是一種加鎖的操作，是悲觀鎖的實作。 在Mysql中進行資料操作時會将操作的相反指令寫入undo log，根據各種政策讀取時非阻塞就是MVCC，undo log中的行就是MVCC中的多版本。一般認為MVCC有下面幾個特點
- 每行資料都存在一個版本，每次資料更新時都更新該版本
- 修改時Copy出目前版本随意修改，個事務之間無幹擾
- 儲存時比較版本号，如果成功（commit），則覆寫原記錄；失敗則放棄copy（rollback）
Innodb的實作方式是：
- 事務以排他鎖的形式修改原始資料
- 把修改前的資料存放于undo log，通過復原指針與主資料關聯
- 修改成功（commit）啥都不做，失敗則恢複undo log中的資料（rollback）
4. 複合索引
索引有兩個特征，即唯一性索引和複合索引。唯一性索引保證在索引列中的全部資料是唯一的，不會包含備援資料。複合索引就是一個索引建立在兩個列或者多個列上，搜尋時需要兩個或者多個索引列作為一個關鍵值。 建立索引 key index_name (attr1, attr2, ...); # 聯合索引 key index_name (attr); # 唯一索引
5. 聚簇索引和非聚簇索引
聚簇索引的資料的實體存放順序與索引順序是一緻的，即：隻要索引是相鄰的，那麼對應的資料一定也是相鄰地存放在磁盤上的。 在聚簇索引下，資料在實體上按順序排在資料頁上，重複值也排在一起，因而在那些包含範圍檢查(between、<、<=、>、>=)或使用group by或orderby的查詢時，一旦找到具有範圍中第一個鍵值的行，具有後續索引值的行保證實體上毗連在一起而不必進一步搜尋，避免了大範圍掃描，可以大大提高查詢速度。 非聚簇索引，葉級頁指向表中的記錄，記錄的實體順序與邏輯順序沒有必然的聯系。 每個表可以有250個索引，其中至多有一個聚簇索引。 非聚簇索引需要大量的硬碟空間和記憶體。另外，雖然非聚簇索引可以提高從表中取資料的速度，它也會降低向表中插入和更新資料的速度。每當你改變了一個建立了非聚簇索引的表中的資料時，必須同時更新索引。
6. MyISAM和InnoDB差别
- Innodb 引擎提供了對資料庫 ACID 事務的支援，并且實作了 SQL 标準的四種隔離級别。該引擎還提供了行級鎖和外鍵限制，它的設計目标是處理大容量資料庫系統，它本身其實就是基于 MySQL 背景的完整資料庫系統，MySQL運作時 Innodb 會在記憶體中建立緩沖池，用于緩沖資料和索引。但是該引擎不支援 FULLTEXT類型的索引，而且它沒有儲存表的行數，當 SELECT COUNT(*) FROM TABLE 時需要掃描全表。當需要使用資料庫事務時，該引擎當然是首選。由于鎖的粒度更小，寫操作不會鎖定全表，是以在并發較高時，使用 Innodb 引擎會提升效率。但是使用行級鎖也不是絕對的，如果在執行一個 SQL 語句時 MySQL 不能确定要掃描的範圍，InnoDB 表同樣會鎖全表。
- MyIASM 是 MySQL 預設的引擎，但是它沒有提供對資料庫事務的支援，也不支援行級鎖和外鍵，是以當 INSERT(插入)或 UPDATE(更新)資料時即寫操作需要鎖定整個表，效率便會低一些。不過和 Innodb 不同，MyIASM 中存儲了表的行數，于是 SELECT COUNT(*) FROM TABLE 時隻需要直接讀取已經儲存好的值而不需要進行全表掃描。如果表的讀操作遠遠多于寫操作且不需要資料庫事務的支援，那麼 MyIASM 也是很好的選擇。
- 大尺寸的資料集趨向于選擇 InnoDB 引擎，因為它支援事務處理和故障恢複。資料庫的大小決定了故障恢複的時間長短，InnoDB 可以利用事務日志進行資料恢複，這會比較快。主鍵查詢在 InnoDB 引擎下也會相當快，不過需要注意的是如果主鍵太長也會導緻性能問題。大批的 INSERT 語句(在每個 INSERT 語句中寫入多行，批量插入)在 MyISAM 下會快一些，但是 UPDATE 語句在 InnoDB 下則會更快一些，尤其是在并發量大的時候。
7. Mysql 的 redo和undo
Undo日志記錄某資料被修改前的值，可以用來在事務失敗時進行復原；Redo日志記錄某資料塊被修改後的值，可以用來恢複未寫入data file的已成功事務更新的資料。 redo log是重做日志，提供前滾操作，undo log是復原日志，提供復原操作 undo log不是redo log的逆向過程，其實它們都算是用來恢複的日志: redo log通常是實體日志，記錄的是資料頁的實體修改，而不是某一行或某幾行修改成怎樣怎樣，它用來恢複送出後的實體資料頁(恢複資料頁，且隻能恢複到最後一次送出的位置)。undo用來復原行記錄到某個版本。undo log一般是邏輯日志，根據每行記錄進行記錄。 資料庫進行任何寫入操作的時候都是要先寫日志的，同樣的道理，我們在執行事務的時候資料庫首先會記錄下這個事務的 redo 記錄檔，然後才開始真正操作資料庫，在操作之前首先會把日志檔案寫入磁盤，那麼當突然斷電的時候，即使操作沒有完成，在重新啟動資料庫時候，資料庫會根據目前資料的情況進行 undo 復原或者是 redo 前滾，這樣就保證了資料的強一緻性。
8. MySQL主從同步有哪些政策？insert到master是等同步完成再響應還是？
詳細
MySQL主從複制的基礎是主伺服器對資料庫修改記錄二進制日志，從伺服器通過主伺服器的二進制日志自動執行更新。一句話表示就是，主資料庫做什麼，從資料庫就跟着做什麼。 mysql複制的類型:
- 基于語句的複制 ：主庫把sql語句寫入到bin log中，完成複制
- 基于行資料的複制：主庫把每一行資料變化的資訊作為事件，寫入到bin log，完成複制
- 混合複制：上面兩個結合體，預設用語句複制，出問題時候自動切換成行資料複制
- 和上面相對應的日志格式也有三種:STATEMENT，ROW，MIXED
- STATEMENT模式（SBR）: 每一條會修改資料的sql語句會記錄到binlog中。優點是并不需要記錄每一條sql語句和每一行的資料變化，減少了binlog日志量，節約IO，提高性能。缺點是在某些情況下會導緻master-slave中的資料不一緻(如sleep()函數,last_insert_id()，以及user-defined functions(udf)等會出現問題)
- ROW模式（RBR）: 不記錄每條sql語句的上下文資訊，僅需記錄哪條資料被修改了，修改成什麼樣了。而且不會出現某些特定情況下的存儲過程、或function、或trigger的調用和觸發無法被正确複制的問題。缺點是會産生大量的日志，尤其是alter table的時候會讓日志暴漲。
- MIXED模式（MBR）以上兩種模式的混合使用，一般的複制使用STATEMENT模式儲存binlog，對于STATEMENT模式無法複制的操作使用ROW模式儲存binlog，MySQL會根據執行的SQL語句選擇日志儲存方式。
主從複制工作原理剖析:
- Master 資料庫隻要發生變化，立馬記錄到Binary log 日志檔案中
- Slave資料庫啟動一個I/O thread連接配接Master資料庫，請求Master變化的二進制日志
- Slave I/O擷取到的二進制日志，儲存到自己的Relay log 日志檔案中
- Slave 有一個 SQL thread定時檢查Realy log是否變化，有變化那麼就更新資料
解決的問題有：
- 實作伺服器負載均衡: 可以通過在主伺服器和從伺服器之間切分處理客戶查詢的負荷，進而得到更好的客戶響應時間
- 通過複制實作資料的異地備份
- 提高資料庫系統的可用性: 當主伺服器出現問題時，資料庫管理者可以馬上讓從伺服器作為主伺服器，用來資料的更新與查詢服務
9. 慢查詢優化
- 優化資料庫結構
- 分解關聯查詢: 很多高性能的應用都會對關聯查詢進行分解，就是可以對每一個表進行一次單表查詢，然後将查詢結果在應用程式中進行關聯，很多場景下這樣會更高效。
- 增加索引
- 建立視圖
- 優化查詢語句
- 添加存儲過程
- 備援儲存資料
10. 主鍵索引和唯一索引的差別
- 在資料庫關系圖中為表定義主鍵将自動建立主鍵索引，主鍵索引是唯一索引的特定類型。該索引要求主鍵中的每個值都唯一。當在查詢中使用主鍵索引時，它還允許對資料的快速訪 問。
- 主鍵索引不僅僅具有索引的特征，還包含着主鍵限制，如不為空，值唯一的特征
- 主鍵可以被其他表引用為外鍵，而唯一索引不能
- 一個表最多隻能建立一個主鍵，但可以建立多個唯一索引
11. Innodb 自增主鍵
InnoDB使用聚集索引，資料記錄本身被存于主索引（一顆B+Tree）的葉子節點上。這就要求同一個葉子節點内（大小為一個記憶體頁或磁盤頁）的各條資料記錄按主鍵順序存放，是以每當有一條新的記錄插入時，MySQL會根據其主鍵将其插入适當的節點和位置，如果頁面達到裝載因子（InnoDB預設為15/16），則開辟一個新的頁（節點）。如果表使用自增主鍵，那麼每次插入新的記錄，記錄就會順序添加到目前索引節點的後續位置，當一頁寫滿，就會自動開辟一個新的頁。這樣就會形成一個緊湊的索引結構，近似順序填滿。由于每次插入時也不需要移動已有資料，是以效率很高，也不會增加很多開銷在維護索引上。
12. 忘了寫主鍵索引，但是已經有幾萬條資料，該怎麼優化
将資料導出，添加索引，導入資料
13. innodb和myism對count的支援？為什麼innodb不像myism存儲記錄總條數
因為MyISAM會儲存表的具體行數，MyISAM隻要簡單地讀出儲存好的行數即可。然而，InnoDB存儲引擎不會儲存表的具體行數，是以，在InnoDB存儲引擎中，InnoDB要掃描一遍整個表來計算有多少行。 InnoDB的事務特性，在同一時刻表中的行數對于不同的事務而言是不一樣的，是以count統計會計算對于目前事務而言可以統計到的行數，而不是将總行數儲存起來友善快速查詢。
14. mysql的存儲引擎有哪些？索引資料結構有哪些？
- InnoDB存儲引擎
- MyISAM存儲引擎
- MEMORY存儲引擎
MEMORY存儲引擎将表中的資料存儲到記憶體中，為查詢和引用其他表資料提供快速通路。
- Archive存儲引擎
如果隻有INSERT和SELECT操作，可以選擇Archive，Archive支援高并發的插入操作，但是本身不是事務安全的。Archive非常适合存儲歸檔資料，如記錄日志資訊可以使用Archive
相關視訊推薦
【mysql資料庫】C++程式員眼中MySQL的索引和事務
網絡原理tcp/udp，網絡程式設計epoll/reactor，面試中正經“八股文”
協程！協程！協程！給你一個吊打面試官的機會！
需要C/C++ Linux伺服器架構師學習資料及大廠面試題加qun812855908擷取（資料包括C/C++，Linux，golang技術，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒體，CDN，P2P，K8S，Docker，TCP/IP，協程，DPDK，ffmpeg等），免費分享
計算機網絡
1. 介紹一下 OSI
OSI七層網絡模型
- 實體層：規定通信裝置的機械的、電氣的、功能的和過程的特性，用以建立、維護和拆除實體鍊路連接配接。在這一層，資料的機關稱為比特(bit)。屬于實體層定義的典型規範代表包括：EIA/TIA RS-232、EIA/TIA RS-449、V.35、RJ-45 等
- 資料鍊路層：在實體層提供比特流服務的基礎上，建立相鄰結點之間的資料鍊路，通過差 錯控制提供資料幀(Frame)在信道上無差錯的傳輸，并進行各電路上的動作系列。資料鍊路層在不可靠的實體媒體上提供可靠的傳輸。該層的作用包括：實體位址尋址、資料的成幀、流量控制、資料的檢錯、重發等。在這一層，資料的機關稱為幀(frame)。資料鍊路層協定的代表包括：SDLC、HDLC、PPP、STP、幀中繼等。
- 網絡層：在 計算機網絡中進行通信的兩個計算機之間可能會經過很多個資料鍊路，也可能還要經過很多通信子網。網絡層的任務就是選擇合适的網間路由和交換結點，確定資料及時傳送。網絡層将資料鍊路層提供的幀組成資料包，包中封裝有網絡層標頭，其中含有邏輯位址資訊- -源站點和目的站點位址的網絡位址。IP 是第 3 層問題的一部分，此外還有一些路由協定和位址解析協定(ARP)。有關路由的一切事情都在這第 3 層處理。位址解析和路由是 3 層的重要目的。網絡層還可以實作擁塞控制、網際互連等功能。在這一層，資料的機關稱為資料包(packet)。網絡層協定的代表包括：IP、IPX、RIP、OSPF 等。
- 傳輸層：第 4 層的資料單元也稱作資料包(packets)。但是，當你談論 TCP 等具體的協定時又有特殊的叫法，TCP 的資料單元稱為段 (segments)而 UDP 協定的資料單元稱為“資料報(datagrams)”。這個層負責擷取全部資訊，是以，它必須跟蹤資料單元碎片、亂序到達的資料包和其它在傳輸過程中可能發生的危險。第 4 層為上層提供端到端(最終使用者到最終使用者)的透明的、可靠的資料傳輸服務。所謂透明的傳輸是指在通信過程中 傳輸層對上層屏蔽了通信傳輸系統的具體細節。傳輸層協定的代表包括：TCP、UDP、SPX 等。
- 會話層：在會話層及以上的高層次中，資料傳送的機關不再另外命名，而是統稱為封包。會話層不參與具體的傳輸，它提供包括通路驗證和會話管理在内的建立和維護應用之間通信的機制。如伺服器驗證使用者登入便是由會話層完成的。
- 表示層：這一層主要解決擁護資訊的文法表示問題。它将欲交換的資料從适合于某一使用者的抽象文法，轉換為适合于 OSI 系統内部使用的傳送文法。即提供格式化的表示和轉換資料服務。資料的壓縮和解壓縮， 加密和解密等工作都由表示層負責。
- 應用層：為作業系統或網絡應用程式提供通路網絡服務的接口。應用層協定的代表包括：Telnet、FTP、HTTP、SNMP 等
2. 輸入網址到頁面渲染的過程
詳細
- 浏覽器建構HTTP Request請求
- 網絡傳輸
- 伺服器建構HTTP Response 響應
- 網絡傳輸
- 浏覽器渲染頁面
DNS解析URL位址、生成HTTP請求封包、建構TCP連接配接、使用IP協定選擇傳輸路線、資料鍊路層保證資料的可靠傳輸、實體層将資料轉換成電子、光學或微波信号進行傳輸
3. 介紹一下不對稱加密以及對稱加密
- 對稱加密是最快速、最簡單的一種加密方式，加密（encryption）與解密（decryption）用的是同樣的密鑰（secret key）。對稱加密的一大缺點是密鑰的管理與配置設定，換句話說，如何把密鑰發送到需要解密你的消息的人的手裡是一個問題。在發送密鑰的過程中，密鑰有很大的風險會被黑客們攔截。現實中通常的做法是将對稱加密的密鑰進行非對稱加密，然後傳送給需要它的人。
- 非對稱加密為資料的加密與解密提供了一個非常安全的方法，它使用了一對密鑰，公鑰（public key）和私鑰（private key）。私鑰隻能由一方安全保管，不能外洩，而公鑰則可以發給任何請求它的人。非對稱加密使用這對密鑰中的一個進行加密，而解密則需要另一個密鑰。
4. HTTP 1.0、HTTP 2.0到HTTP 3.0以及HTTPS
- HTTP1.0 使用的是非持久連接配接，主要缺點是用戶端必須為每一個待請求的對象建立并維護一個新的連接配接，即每請求一個文檔就要有兩倍RTT 的開銷。因為同一個頁面可能存在多個對象，是以非持久連接配接可能使一個頁面的下載下傳變得十分緩慢，而且這種 短連接配接增加了網絡傳輸的負擔。(RTT(Round Trip Time)：一個連接配接的往返時間)
- HTTP1.1 支援長連接配接, 在HTTP1.0的基礎上引入了更多的緩存控制政策，引入了請求範圍設定，優化了帶寬，在錯誤通知管理中新增了錯誤狀态響應碼，增加了Host頭處理，可以傳遞主機名（hostname），但是傳輸内容是明文，不夠安全
- HTTP 1.x優化（SPDY）：SPDY 并不是新的一種協定，而是在 HTTP 之前做了一層會話層。為了達到減少頁面加載時間的目标，SPDY 引入了一個新的二進制分幀資料層，以實作優先次序、最小化及消除不必要的網絡延遲，目的是更有效地利用底層 TCP 連接配接。為多路複用設立了請求優先級，對header部分進行了壓縮，引入了HTTPS加密傳輸，用戶端可以在緩存中取到之前請求的内容。
- HTTP2.0：支援明文傳輸，而HTTP 1.X強制使用SSL/TLS加密傳輸，和HTTP 1.x使用的header壓縮方法不同。HTTP2.0 基于二進制格式進行解析，而HTTP 1.x基于文本格式進行解析，多路複用，HTTP1.1是多個請求串行化單線程處理，HTTP 2.0是并行執行，一個請求逾時并不會影響其他請求。多路複用可以繞過浏覽器限制同一個域名下的請求數量的問題，進而提高了網頁的性能。
- HTTP 3.0 (QUIC)：QUIC (Quick UDP Internet Connections), 快速 UDP 網際網路連接配接 ，QUIC是基于UDP協定的。
- 線頭阻塞(HOL)問題的解決更為徹底：基于TCP的HTTP/2，盡管從邏輯上來說，不同的流之間互相獨立，不會互相影響，但在實際傳輸方面，資料還是要一幀一幀的發送和接收，一旦某一個流的資料有丢包，則同樣會阻塞在它之後傳輸的流資料傳輸。而基于UDP的QUIC協定則可以更為徹底地解決這樣的問題，讓不同的流之間真正的實作互相獨立傳輸，互不幹擾。
- 切換網絡時的連接配接保持： 目前移動端的應用環境，使用者的網絡可能會經常切換，比如從辦公室或家裡出門，WiFi斷開，網絡切換為3G或4G。基于TCP的協定，由于切換網絡之後，IP會改變，因而之前的連接配接不可能繼續保持。而基于UDP的QUIC協定，則可以内建與TCP中不同的連接配接辨別方法，進而在網絡完成切換之後，恢複之前與伺服器的連接配接 HTTPS: HTTPS運作在安全套接字協定(Secure Sockets Layer，SSL )或傳輸層安全協定（Transport Layer Security，TLS）之上，所有在TCP中傳輸的内容都需要經過加密。HTTP的端口是80，HTTPS的端口是443
5. TCP 的擁塞控制、流量控制、滑動視窗
- TCP擁塞控制用于控制發送端向網絡一次連續寫入的資料量。
- 使用的方法有 當發送視窗大小小于發送門限時，使用慢開始指數增大視窗，當發送視窗大于發送門限時，使用擁塞避免算法加性增加發送視窗大小，當出現網絡擁塞時，門限減為目前發送視窗的一半，重新開始慢啟動。另一種快速重傳的方法是：如果收到連續三個ACK，則視作網絡的阻塞程度不嚴重，将門限減為目前發送視窗大小的一半，将發送視窗尺寸設定為目前門限大小，啟動擁塞避免算法。
- 如果發送方把資料發送得過快，接收方可能會來不及接收，這就會造成資料的丢失。TCP 的流量控制是利用滑動視窗機制實作的，接收方在傳回的 ACK 中會包含自己的接收視窗（RWND）的大小，TCP 頭部有個 16 位視窗大小，表示的就是 RWND。以控制發送方的資料發送。
6. TCP與UDP
- TCP 面向連接配接的，UDP 是無連接配接的
- TCP 面向位元組流，UDP 面向資料包 (位元組流：發送端執行的寫操作數和接收端執行的讀操作數之間沒有任何數量關系)
- Tcp 通過校驗和，重傳控制，序号辨別，滑動視窗、确認應答實作可靠傳輸
- UDP 具有較好的實時性，工作效率比 TCP 高，适用于對高速傳輸和實時性有較高的通信或廣播通信
- 每一條 TCP 連接配接隻能是點到點的, UDP 支援一對一，一對多，多對一和多對多的互動通信
- TCP 對系統資源要求較多，UDP 對系統資源要求較少
- 若通信資料完整性需讓位與通信實時性，則應該選用 TCP 協定（如檔案傳輸、重要狀态的更新等）；反之，則使用 UDP 協定（如視訊傳輸、實時通信等）
7. 為什麼三次握手、SYN攻擊、SYN攻擊的應對方法
采用兩次握手，那麼若 Client 向 Server 發起的包 A1 如果在傳輸鍊路上遇到的故障，導緻傳輸到 Server 的時間相當滞後，在這個時間段由于 Client 沒有收到 Server的對于包 A1 的确認，那麼就會重傳一個包 A2，假設伺服器正常收到了 A2 的包，然後傳回确認 B2 包。由于沒有第三次握手，這個時候 Client 和 Server 已經建立連接配接了。再假設 A1 包随後在鍊路中傳到了 Server，這個時候 Server 又會傳回 B1 包确認，但是由于 Client 已經清除了 A1 包，是以 Client 會丢棄掉這個确認包，但是 Server 會保持這個相當于“僵屍”的連接配接。 TCP 在傳遞資料前需要經過三次握手，SYN 攻擊的原理就是向伺服器發送SYN 資料包，并僞造源 IP 位址，伺服器在收到 SYN 資料包時，會将連接配接加入 backlog 隊列，并向源 IP 發送 SYN-ACK 資料包，并等待 ACK 資料包，以完成三次握手建立連接配接。由于源 IP 位址是僞造的不存在主機 IP，是以伺服器無法收到 ACK 資料包，并會不斷重發，同時 backlog 隊列被不斷被攻擊的 SYN 連接配接占滿，導緻無法處理正常的連接配接。 針對 SYN 攻擊的幾個環節，提出相應的處理方法:
- 減少 SYN-ACK 資料包的重發次數
- 增加 backlog 隊列
- 限制 SYN 并發數
- 使用 SYN Cookie 技術
8. TCP四次揮手的TIME_WAIT
首先調用 close()發起主動關閉的一方，在發送最後一個 ACK 之後會進入 time_wait 的狀态，也就說該發送方會保持 2MSL 時間之後才會回到初始狀态。MSL 指的是資料包在網絡中的最大生存時間,一般是2min。 為什麼存在 time_wait:
- 可靠地終止 TCP 連接配接。維持一個狀态防止對端沒有接受到最後一個 ACK 封包段
- 保證讓遲來的 TCP 封包段有足夠的時間被識别進而丢棄。TCP 封包段最大生存時間是 MSL，2MSL 保證兩個傳輸方向上沒有接收到的、遲到的 TCP 封包段全部消失。一個使用原本 IP 和端口的新連接配接可以在 2MSL 之後安全建立，而絕對不會接收到原有連接配接上的資料。
9. TCP 如何保證資料傳輸的可靠性
- 可靠連接配接
- 序号
- 應答機制 序列号與ACK
- 逾時重傳
- 流量控制
- 擁塞控制
- CRC校驗
- TCP 對接收到的 TCP 封包段重排、整理，再傳遞給應用層
10. HTTP狀态碼
- 1XX 資訊碼，伺服器收到請求，需要請求者繼續執行操作；100 正常，用戶端應該繼續請求
- 2XX 成功碼，操作被成功接收并處理；200 正常處理，204 成功處理，但是沒有内容傳回
- 3XX 重定向，需要進一步的操作以完成請求；301 永久重定向，302 臨時重定向
- 4XX 用戶端錯誤，請求包含文法錯誤或無法完成請求；400 文法錯誤，401 要求身份認證，403 禁止 404 找不到資源
- 5XX 伺服器錯誤，伺服器在處理請求的過程中發生了錯誤 500 内部伺服器錯誤，503服務不可用
11. 路由器的作用
12. 我們的電腦能轉發網絡嗎，原理是什麼
14. 五層網絡IO模型
- 實體層
- 資料鍊路層
- 網絡層
- 運輸層
- 應用層 (OSI會話層、表示層、應用層)
15. HTTP協定怎麼解決拆包粘包的問題
TCP發送端為了将多個發往接收端的包，更有效的發到對方，使用了優化方法（Nagle 算 法），将多次間隔較小、資料量小的資料，合并成一個大的資料塊，然後進行封包。這樣，接收端，就難于分辨出來了，必須提供科學的拆包機制。 TCP 粘包是指發送方發送的若幹包資料到接收方接收時粘成一包，從接收緩沖區看，後一包資料的頭緊接着前一包資料的尾。 出現粘包的原因，發送端使用Nagle算法将多個小TCP合并發送，接收端将多個TCP包緩存接收。 解決方案：
- 發送方：關閉Nagle算法
- 接收方：在應用層處理
16. HTTPS握手的過程，用到的加密算法
- 浏覽器請求連接配接
- 伺服器傳回證書：證書裡面包含了網站位址，加密公鑰，以及證書的頒發機構等資訊
- 浏覽器收到證書後作以下工作
- 驗證證書的合法性
- 生成随機（對稱）密碼，取出證書中提供的公鑰對随機密碼加密
- 将之前生成的加密随機密碼等資訊發送給網站
- 伺服器收到消息後作以下的操作
- 使用自己的私鑰解密浏覽器用公鑰加密後的消息，并驗證 HASH 是否與浏覽器發來的一緻；獲得浏覽器發過來的對稱秘鑰
- 使用加密的随機對稱密碼加密一段消息，發送給浏覽器
- 浏覽器解密并計算握手消息的 HASH：如果與服務端發來的 HASH 一緻，此時握手過程結束，之後進行通信
幂等性怎麼確定的
- 通過唯一的業務單号來保證
TCP封包内容，http封包内容
ARP協定的作用
ARP（位址解析）協定是一種解析協定，本來主機是完全不知道這個 IP 對應的是哪個主機的哪個接口，當主機要發送一個 IP 包的時候，會首先查一下自己的 ARP 高速緩存表（最近資料傳遞更新的 IP-MAC 位址對應表），如果查詢的 IP－MAC 值對不存在，那麼主機就向網絡廣播一個 ARP請求包，這個包裡面就有待查詢的 IP 位址，而直接收到這份廣播的包的所有主機都會查詢自己的 IP 位址，如果收到廣播包的某一個主機發現自己符合條件，那麼就回應一個 ARP 應答包（将自己對應的 IP-MAC 對應位址發回主機），源主機拿到 ARP 應答包後會更新自己的 ARP 緩存表。源主機根據新的 ARP 緩存表準備好資料鍊路層的的資料包發送工作。
HTTP 無狀态 無連接配接
- 無連接配接的含義是限制每次連接配接隻處理一個請求。伺服器處理完客戶的請求，并收到客戶的應答後，即斷開連接配接。采用這種方式可以節省傳輸時間。為請求時建連接配接、請求完釋放連接配接，以盡快将資源釋放出來服務其他用戶端，可以加KeepAlive彌補無連接配接的問題
- 無狀态是指協定對于事務處理沒有記憶能力，伺服器不知道用戶端是什麼狀态。即我們給伺服器發送 HTTP 請求之後，伺服器根據請求，會給我們發送資料過來，但是，發送完，不會記錄任何資訊。 可以通過Cookie和Session來彌補這個問題。
Cookie 和 Session
- cookie 是一種發送到客戶浏覽器的文本串句柄，并儲存在客戶機硬碟上，可以用來在某個WEB站點會話間持久的保持資料。
- Session的本質上也是cookie，但是不同點是存在伺服器上的。這就導緻，你如果使用cookie，你關閉浏覽器之後，就丢掉Cookie了，但是如果關掉浏覽器，重新打開之後，發現還有相應的資訊，那就說明用的是Session。因為cookie是存在本地的，是以也會有相應的安全問題，攻擊者可以去僞造他，填寫相應的字段名，就能登入你的賬戶，還有如果cookie的有效期很長的話，也不安全。
- session 由伺服器産生，對于用戶端，隻存儲session id在cookie中
作業系統
程序與線程的差別
協程與線程
- 協程是一種比線程更加輕量級的存在。一個線程可以擁有多個協程；協程不是被作業系統核心管理，而完全是由程式所控制
- 協程的開銷遠遠小于線程
- 協程擁有自己寄存器上下文和棧。協程排程切換時，将寄存器上下文和棧儲存到其他地方，在切換回來的時候，恢複先前儲存的寄存器上下文和棧
- 每個協程表示一個執行單元，有自己的本地資料，與其他協程共享全局資料和其他資源
- 跨平台、跨體系架構、無需線程上下文切換的開銷、友善切換控制流，簡化程式設計模型
- 協程又稱為微線程，協程的完成主要靠 yeild 關鍵字，協程執行過程中，在子程式内部可中斷，然後轉而執行别的子程式，在适當的時候再傳回來接着執行
- 協程極高的執行效率，和多線程相比，線程數量越多，協程的性能優勢就越明顯
- 不需要多線程的鎖機制
同一個程序中，不同線程什麼是共享的，什麼不是共享的（操作棧、程式計數器）
共享：
- 程序代碼段
- 程序的公有資料(利用這些共享的資料，線程很容易的實作互相之間的通訊)
- 程序打開的檔案描述符
- 信号的處理器
- 程序的目前目錄
- 程序使用者ID與程序組ID
私有：
- 線程ID
- 寄存器組的值 (PC指針)
- 線程的堆棧
- 錯誤傳回碼
- 線程的信号屏蔽碼
線程上下文切換的時候，什麼東西需要儲存、什麼東西需要恢複
程序切換步驟：
- 儲存目前程序的上下文
- 恢複某個先前被搶占的程序的上下文
- 将控制傳遞給這個新恢複的程序
詳細步驟：
- 儲存處理器上下文環境即 PSW、PC 等寄存器和堆棧内容，儲存到核心堆棧中
- 調整被中斷程序的 PCB 程序控制塊資訊，改變程序狀态和其它資訊
- 将程序控制塊移到相應隊列即阻塞隊列或就緒隊列
- 選擇另一個程序執行
- 更新所選擇程序的 PCB 程序控制塊（包括将狀态變為運作态）
- 更新記憶體管理的資料結構
- 恢複第二個程序的上下文環境
程序排程算法
- 先來先服務排程算法
- 短作業優先排程算法
- 非搶占式優先級排程算法
- 搶占式優先級排程算法
- 高響應比優先排程算法
- 時間片輪轉法排程算法
程序間怎麼通信
- 管道 (具名管道，無名管道)
- 消息隊列
- 信号：用于通知接收程序某個事件已經發生
- 信号量: 信号量是一個計數器，信号量用于實作程序間的互斥與同步，而不是用于存儲程序間通信資料
- 共享記憶體
- socket套接字
線程間通信
- 臨界區：通過多線程的串行化來通路公共資源或一段代碼，速度快，适合控制資料通路
- 互斥量 Synchronized/Lock：采用互斥對象機制，隻有擁有互斥對象的線程才有通路公共資源的權限。因為互斥對象隻有一個，是以可以保證公共資源不會被多個線程同時通路
- 信号量 Semphare：為控制具有有限數量的使用者資源而設計的，它允許多個線程在同一時刻去通路同一個資源，但一般需要限制同一時刻通路此資源的最大線程數目
- 事件(信号)，Wait/Notify：通過通知操作的方式來保持多線程同步，還可以友善的實作多線程優先級的比較操作
LRU算法是如何實作的
哈希連結清單法
volatile 記憶體屏障
volatile 關鍵字是一種類型修飾符，用它聲明的類型變量表示可以被某些編譯器未知的因素更改，比如：作業系統、硬體或者其它線程等。遇到這個關鍵字聲明的變量，編譯器對通路該變量的代碼就不再進行優化，進而可以提供對特殊位址的穩定通路。聲明時文法：int volatile vInt; 當要求使用 volatile 聲明的變量的值的時候，系統總是重新從它所在的記憶體讀取資料，即使它前面的指令剛剛從該處讀取過資料。而且讀取的資料立刻被儲存 volatile 用在如下的幾個地方:
- 中斷服務程式中修改的供其它程式檢測的變量需要加 volatile
- 多任務環境下各任務間共享的标志應該加 volatile
- 存儲器映射的硬體寄存器通常也要加 volatile 說明，因為每次對它的讀寫都可能由不同意義
死鎖的四個條件和預防
- 互斥：一個資源每次隻能被一個程序使用
- 不可搶占性： 當某個程序已經獲得這種資源後，系統是不能強行收回，其他程序也不能強行奪走，隻能由自身使用完釋放
- 保持與等待：部分配置設定，允許程序在不釋放其已經分得的資源的情況下請求并等待配置設定别的資源
- 循環等待：若幹個程序形成環形鍊
預防方法：
- 允許程序強行從占有者那裡奪取某些資源，破壞不可搶占條件
- 程序在運作前一次性地向系統申請它所需要的全部資源。，破壞了保持與等待條件
- 把資源事先分類編号，按号配置設定，使程序在申請，占用資源時不會形成環路，破壞了 循環等待條件
銀行家算法
銀行家算法的基本思想是配置設定資源之前，判斷系統是否是安全的；若是，才配置設定。它是最具有代表性的避免死鎖的算法。 算法内容：
- 每一個線程進入系統時，它必須聲明在運作過程中，所需的每種資源類型最大數目，其數目不應超過系統所擁有每種資源總量，當線程請求一組資源系統必須确定有足夠資源配置設定給該程序，若有，再進一步計算這些資源配置設定給程序後，是否會使系統處于不安全狀态，不會（即若能在配置設定資源時找到一個安全序列），則将資源配置設定給它，否則等待
多路IO模型 NIO
在多路複用IO模型中，會有一個線程（Java中的Selector）不斷去輪詢多個socket的狀态，隻有當socket真正有讀寫事件時，才真正調用實際的IO讀寫操作。因為在多路複用IO模型中，隻需要使用一個線程就可以管理多個socket，系統不需要建立新的程序或者線程，也不必維護這些線程和程序，并且隻有在真正有socket讀寫事件進行時，才會使用IO資源，是以它大大減少了資源占用。
五種IO模型
- 阻塞IO: 應用程式調用一個 IO 函數，導緻應用程式阻塞，等待資料準備好
- 非阻塞IO: 我們把一個 SOCKET 接口設定為非阻塞就是告訴核心，當所請求的 I/O 操作 無法完成時，不要将程序睡眠，而是傳回一個錯誤。這樣我們的 I/O 操作函數将不斷的測試資料是否已經準備好，如果沒有準備好，繼續測試，直到資料準備好為止。在這個不斷測試的過程中，會大量的占用 CPU 的時間
- 多路IO複用: I/O 複用模型會用到 select、poll、epoll 函數，這幾個函數也會使程序阻塞，但是和阻塞 I/O 所不同的的，這三個函數可以同時阻塞多個 I/O 操作。而且可以同時對多個讀操作，多個寫操作的 I/O 函數進行檢測，直到有資料可讀或可寫時，才真正調用 I/O 操作函數
- 信号驅動IO（不常用）: 首先我們允許套接口進行信号驅動 I/O,并安裝一個信号處理函數，程序繼續運作并不阻塞。當資料準備好時，程序會收到一個 SIGIO 信号，可以在信号處理函數中調用 I/O操作函數處理資料。
- 異步IO: 當一個異步過程調用發出後，調用者不能立刻得到結果。實際處理這個調用的部件在完成後，通過狀态、通知和回調來通知調用者的輸入輸出操作
有哪幾種多路複用的方式？它們之間的差別
- select
- 單個程序能夠監視的檔案描述符的數量存在最大限制，通常是 1024。由于 select 采用輪詢的方式掃描檔案描述符，檔案描述符數量越多，性能越差
- 核心/使用者空間記憶體拷貝問題，select 需要大量句柄資料結構，産生巨大開銷
- Select 傳回的是含有整個句柄的數組，應用程式需要周遊整個數組才能發現哪些句柄發生事件
- Select 的觸發方式是水準觸發，應用程式如果沒有完成對一個已經就緒的檔案描述符進行 IO 操作，那麼每次 select 調用還會将這些檔案描述符通知程序
- poll
- 與 select 相比，poll 使用連結清單儲存檔案描述符，一沒有了監視檔案數量的限制，但其他三個缺點依然存在
- epoll
- epoll 使用一個檔案描述符管理多個描述符，将使用者關系的檔案描述符的事件存放到核心的一個事件表中，這樣在使用者空間和核心空間的 copy 隻需一次。Epoll 是事件觸發的，不是輪詢查詢的。沒有最大的并發連接配接限制，記憶體拷貝，利用 mmap() 檔案映射記憶體加速與核心空間的消息傳遞
epoll的兩種工作模式
- LT模式
當 epoll_wait 檢測到描述符事件發生并将此事件通知應用程式，應用程式可以不立即處理該事件。下次調用 epoll_wait 時，會再次響應應用程式并通知此事件。一個 socket 第一次有資料，LT 模式下檢測到 socket 處于活躍狀态，接下來再有資料過來，接着觸發。或者說可以根據需要收取部分資料，隻要 socket 上資料不收取完，epoll_wait 會接着傳回這個可讀 socket。程式設計上如果需要資料包一部分一部分的處理，可以使用 LT 模式
- ET模式
當 epoll_wait 檢測到描述符事件發生并将此事件通知應用程式，應用程式必須立即處理該事件。如果不處理，下次調用 epoll_wait 時，不會再次響應應用程式并通知此事件。第一次有資料會觸發 socket，第二次再有資料不會觸發，必須等第一次的資料完全讀完或寫完。必須把目前 socket 資料全部收完，才能接受下一次的可讀 socket。程式設計上 ET 模式必須是一個循環，收取資料到 recv 傳回-1，errno=EAGAIN
虛拟記憶體
- 虛拟記憶體使得應用程式認為它擁有連續的可用記憶體，這樣一來，就在邏輯層面上擴大了記憶體容量。但是實際上，隻是把比較常用的記憶體片段取出來了而已，還有部分資源是放在磁盤存儲器上的。需要的時候再進行資料交換。
- 排程方式有，分頁式，段式，段頁式。比較流行方式是段頁式，他結合了前兩者的優點，以頁為機關替換，以段為機關使用。
- 常見的替換替換算法有4種，随機算法，先進先出算法，LRU算法，最優算法。 比較常使用的是LRU算法，他在redis裡也有使用，當redis的記憶體滿了的時候就是使用LRU算法替換掉舊記憶體。
算法
加密算法 線性同餘法 快排的優化 列印二叉樹每一層，最右邊節點的值 尋找兩個連結清單的公共節點 鏡像二叉樹 删除連結清單中所有值相等的節點 單例模式 雞蛋摔樓的問題
Linux
kill -9與kill -15的差別
- SIGNKILL（9） 的效果是立即殺死程序. 該信号不能被阻塞, 處理和忽略。
- SIGNTERM（15） 的效果是正常退出程序，退出前可以被阻塞或回調處理。并且它是Linux預設的程式中斷信号(預設是15)。
- kill - 9 表示強制殺死該程序；與SIGTERM相比，這個信号不能被捕獲或忽略，同時接收這個信号的程序在收到這個信号時不能執行任何清理
Linux修改使用者權限
- 建立使用者
sudo password xxx # xxx 表示使用者名
- 删除使用者
sudo userdel xxx sudo rm -rf /home/xxx # 删除使用者權限相關配置 cd /home rm -rf xxx cat /etc/passwd # 找到最後一行，可以發現剛剛建立的使用者，再使用vi編輯器删除最後一行 cat /etc/group # 找到最後一行，可以發現剛剛建立的使用者，再使用vi編輯器删除最後一行 cd /var/spool/mail rm -rf xxx # 删除郵箱檔案
- 修改權限
# 采用修改系統中/etc/sudoers檔案的方法配置設定使用者權限。因為此檔案隻有r權限，在改動前需要增加w權限，改動後，再去掉w權限 sudo chmod +w /etc/sudoers sudo vim /etc/sudoers # User privilege specification add text root ALL=(ALL:ALL) ALL xxx ALL=(ALL:ALL) ALL # 這一行為添加的代碼，XXX表示需要添權重限的使用者名 sudo chmod -w /etc/sudoers # 改為隻讀模式
檢視網絡端口
netstat -a #列出所有端口 netstat -at #列出所有tcp端口 netstat -au #列出所有udp端口 netstat -ax #列出所有UNIX端口 netstat -al #列出所有監聽中的端口 netstat -lt #列出所有監聽中的tcp有端口 netstat -lu #列出所有監聽中的udp端口 netstat -lx #列出所有監聽中的unix端口 複制
檢視所有檔案的大小
du -h --max-depth=1 # 如果沒有--max-depth=1,則會遞歸顯示所有目錄 df 指令是檢視檔案系統給的大小 複制
Git 版本控制
git rebase 與 git merge
- Merge 會自動根據兩個分支的共同祖先和兩個分支的最新送出進行一個三方合并，然後将合并中修改的内容生成一個新的 commit，即 merge 合并兩個分支并生成一個新的送出,并且仍然後儲存原來分支的 commit 記錄。
- Rebase 會從兩個分支的共同祖先開始提取目前分支上的修改，然後将目前分支上的所有修改合并到目标分支的最新送出後面，如果提取的修改有多個，那 git 将依次應用到最新的送出後面。Rebase 後隻剩下一個分支的 commit 記錄