導(dǎo)讀知識(shí)點(diǎn)列表一、redisredis應(yīng)用場(chǎng)景stringhashset：去重zset:排行榜list：（阻塞隊(duì)列、消息通信）HyperLogLog：大量統(tǒng)計(jì)（....

知識(shí)點(diǎn)列表

一、redis

1. redis

• 應(yīng)用場(chǎng)景
• string
• hash
• set：去重
• zset: 排行榜
• list：（阻塞隊(duì)列、消息通信）
• HyperLogLog：大量統(tǒng)計(jì)（非精確）
• 內(nèi)部數(shù)據(jù)結(jié)構(gòu)
• dict：key[string] VS value （redis obj）;拉鏈法解決沖突（同php）;裝載因子（哈希表已保存節(jié)點(diǎn)數(shù)量 / 哈希表大小）超過預(yù)定值自動(dòng)擴(kuò)充內(nèi), 引發(fā)（增量式）rehashing
• 根據(jù)ht[0]創(chuàng)建一個(gè)比原來size大一倍（也可能減少）的hashtable，
• 重新計(jì)算hash和index值，根據(jù)rehashindex逐步操作
• 到達(dá)一定閾值（ht[0]為空）操作停止
• 期間響應(yīng)客戶端
• 寫操作：寫到新的ht[1]
• 讀操作：先讀ht[0]，再讀ht[1]
• sds：simple dynamic string
• string的底層實(shí)現(xiàn)為sds，但是string存儲(chǔ)數(shù)字的時(shí)候，執(zhí)行incr decr的時(shí)候，內(nèi)部存儲(chǔ)就不是sds了。
• 二進(jìn)制安全binary safe（5種類型的header falgs得到具體類型，進(jìn)而匹配len和alloc）
• robj：redis object，為多種數(shù)據(jù)類型提供一種統(tǒng)一的表示方式，同時(shí)允許同一類型的數(shù)據(jù)采用不同的內(nèi)部表示，支持對(duì)象共享和引用計(jì)數(shù)。
• sds
• string
• long
• ziplist
• quicklist
• skiplist

typedef struct redisObject { unsigned type:4;【OBJ_STRING, OBJ_LIST, OBJ_SET, OBJ_ZSET, OBJ_HASH】 unsigned encoding:4【上述type的OBJ-ENCODING _XXX常量，四個(gè)位說明同一個(gè)type可能是不同的encoding，或者說同一個(gè)數(shù)據(jù)類型，可能不同的內(nèi)部表示】; unsigned lru:LRU_BITS; /* lru time (relative to server.lruclock) */ int refcount; void *ptr【真正指向的數(shù)據(jù)】; } robj

• OBJ_ENCODING_
• string
• OBJ_ENCODING_RAW,代表sds ，原生string類型
• OBJ_ENCODING_INT，long類型
• OBJ_ENCODING_EMBSTR ，嵌入
• OBJ_HASH
• OBJ_ENCODING_HT，表示成dict
• OBJ_ENCODING_ZIPLIST，hash用ziplist表示
• OBJ_SET
• OBJ_ENCODING_INTSET,表示成intest
• config
• set-max-intset-entries 512【是整型而且數(shù)據(jù)元素較少時(shí)，set使用intset；否則使用dict】
• OBJ_ZSET
• OBJ_ENCODING_SKIPLIST,表示成skiplist
• 思想：多層鏈表，指針來回查找，插入和更新采取隨機(jī)層數(shù)的方法來規(guī)避
• config
• zset-max-ziplist-entries 128
• zset-max-ziplist-value 64
• OBJ_LIST
• OBJ_ENCODING_QUICKLIST
• config
• list-max-ziplist-size -2
• list-compress-depth 0
• 內(nèi)部結(jié)構(gòu)實(shí)現(xiàn)
• string
• hash（兩種encoding,根據(jù)下面的config）
• ziplist
• dict
• config
• hash-max-ziplist-entries 512【注意單位是“對(duì)兒”】
• hash-max-ziplist-value 64【單個(gè)value超過64】
• set
• zset
• list
• quicklist
• 定義：是一個(gè)ziplist型的雙向鏈表
• 壓縮算法:LZF
• zset如何根據(jù)兩個(gè)屬性排序？比如根據(jù)id和age
• 可以用位操作，把兩個(gè)屬性合成一個(gè)double
• 用zunionstore合并存儲(chǔ)為新的key，再zrange
• redis是如何保證原子性操作的？
• 因?yàn)樗莟m單線程的?。╬s:mysql是多線程）
• 在并發(fā)腳本中的get set等不是原子的~
• 在并發(fā)中的原子命令incr setnx等是原子的
• 事務(wù)是保證批量操作的原子性
• 主從復(fù)制過程：

1. 從服務(wù)器向主服務(wù)器發(fā)送sync
2. 主服務(wù)器收到sync命令執(zhí)行BGSAVE,且在這期間新執(zhí)行的命令保存到一個(gè)緩沖區(qū)
3. 主執(zhí)行（BGSAVE）完畢后,將.rdb文件發(fā)送給從服務(wù)器，從服務(wù)器將文件載入內(nèi)存
4. BGSAVE期間到緩沖區(qū)的命令會(huì)以redis命令協(xié)議的方式，將內(nèi)容發(fā)送給從服務(wù)器。

• 特性：
• 單線程，自實(shí)現(xiàn)（event driver庫(kù)，見下面四個(gè)io多路復(fù)用函數(shù)）
• 在/src/ae.c中:宏定義的方式

/* Include the best multiplexing layer supported by this system. * The following should be ordered by performances, descending. */ #ifdef HAVE_EVPORT #include "ae_evport.c" #else #ifdef HAVE_EPOLL #include "ae_epoll.c" #else #ifdef HAVE_KQUEUE #include "ae_kqueue.c" #else #include "ae_select.c" #endif #endif

• io多路復(fù)用，最常用調(diào)用函數(shù)：select（epoll，kquene，avport等），同時(shí)監(jiān)控多個(gè)文件描述符的可讀可寫
• reactor方式實(shí)現(xiàn)文件處理器（每一個(gè)網(wǎng)絡(luò)連接對(duì)應(yīng)一個(gè)文件描述符），同時(shí)監(jiān)聽多個(gè)fd的accept，read（from client），write（to client），close文件事件。
• 備份與持久化
• rdb（fork 進(jìn)程dump到file，但是注意觸發(fā)節(jié)點(diǎn)的覆蓋問題，導(dǎo)致數(shù)據(jù)不完整）
• 手動(dòng) save bgsave
• 自動(dòng) conf:save 900 1 save 300 10 save 60 10000 dbfilename dump.rdb
• 優(yōu)點(diǎn)：對(duì)服務(wù)進(jìn)程影響小，記錄原數(shù)據(jù)文件方式便于管理還原
• 缺點(diǎn)：可能數(shù)據(jù)不完整
• aof（類似binlog）
• appendfsync no
• appendfsync everysec
• appendfsync always （每執(zhí)行一個(gè)命令）
• 優(yōu)點(diǎn)：數(shù)據(jù)最完整，支持rewrite
• 缺點(diǎn):文件相對(duì)rdb更大，導(dǎo)入速度比rdb慢
• 過期策略：
• 定時(shí)過期：時(shí)間到了立即刪除，cpu不友好，內(nèi)存友好。
• 惰性過期：訪問時(shí)判斷是否過期：cpu友好，內(nèi)存不友好
• 定期過期：expires dict中scan，清除已過期的key。cpu和內(nèi)存最優(yōu)解
• 內(nèi)存淘汰機(jī)制
• 127.0.0.1:6379> config get maxmemory-policy

1) "maxmemory-policy"2) "noeviction"127.0.0.1:6379>

• noeviction：新寫入時(shí)回報(bào)錯(cuò)
• allkeys-lru:移除最近最少使用的key
• allkeys-random：隨機(jī)移除某些key
• volatile-lru：設(shè)置了過期時(shí)間的key中，移除最近最少使用
• volatile-random：不解釋
• volatile-ttl：設(shè)置類過期時(shí)間的鍵中，有更早過期時(shí)間的key優(yōu)先移除
• redis隊(duì)列不足之處
• 隊(duì)列可能丟東西
• 比如redis掛了，producer沒有停止，但是隊(duì)列數(shù)據(jù)無(wú)法寫入（除非同步落地到mysql）
• 隊(duì)列的consumer 需要手動(dòng)處理commit協(xié)議
• 如果consumer處理完，表示真正完成
• 如果沒有處理完？放回隊(duì)列？直接丟棄？
• 事件重放機(jī)制不支持
• 比如consumer消費(fèi)錯(cuò)了，那能不能將隊(duì)列回放呢再次處理呢？
• 隊(duì)列最大長(zhǎng)度及過期時(shí)間
• 如果producer遠(yuǎn)大于consumer，撐爆了怎么辦
• 如果comsumer 一直沒有處理，producer的數(shù)據(jù)如何處理
• exactly once
• 單機(jī)分布式鎖沒問題，集群情況下不靠譜
• vs memcache
• memcached
• 優(yōu)勢(shì)
• 多線程（listen & woker)，利用多核
• round robin
• cas（check and set，compare and swap）
• 劣勢(shì)
• cache coherency、鎖
• key大小有限制（1M）
• 特點(diǎn)
• 內(nèi)存預(yù)分配：slab trunk
• redis
• 優(yōu)勢(shì)：
• 自己封裝了一個(gè)AEEvent（epoll select kqueue），io多路復(fù)用
• 豐富的數(shù)據(jù)結(jié)構(gòu)（對(duì)內(nèi) 對(duì)外）
• 良好的持久化策略（rdb aof）
• 單機(jī)可部署多實(shí)例，利用多核
• 劣勢(shì)：
• 排序、聚合cpu密集操作會(huì)等影響吞吐量
• key 大小最大為1g
• more | other
• redis ziplist與普通雙向鏈表的區(qū)別：普通的鏈表每一項(xiàng)都占用獨(dú)立的一塊內(nèi)存，各項(xiàng)之間用地址指針（引用）連接起來，這樣會(huì)導(dǎo)致大量碎片。而ziplist是將表中每項(xiàng)放在前后連續(xù)地址空間內(nèi)，而且對(duì)值存儲(chǔ)采取變長(zhǎng)編碼。
• redis msetnx對(duì)應(yīng)的del，可以采取lua腳本保證get del的原子性
• redis 單線程如何實(shí)現(xiàn)阻塞隊(duì)列？
• 阻塞是阻塞client，又不是阻塞server，server不發(fā)數(shù)據(jù)，client不就阻塞住了，當(dāng)client想要阻塞在某個(gè)key上，server會(huì)把這個(gè)client放到一個(gè)block list里，等key發(fā)生變化，就send數(shù)據(jù)給client。
• redis 阻塞隊(duì)列的時(shí)間設(shè)置實(shí)現(xiàn)？
• blocklist里只存了列表，這個(gè)timeout存在連接上，靠serverCron來遍歷檢測(cè)，每次遍歷5個(gè)，
• 高性能的方案是小堆或者紅黑樹或者時(shí)間輪實(shí)現(xiàn)的定時(shí)器結(jié)構(gòu)，epoll wait那塊timeout參數(shù)就設(shè)置成下次超時(shí)時(shí)間
• 每次poll loop里除了處理io事件，再把定時(shí)器的數(shù)據(jù)結(jié)構(gòu)里處理下，堆和紅黑只要檢測(cè)到一個(gè)未超時(shí)就可以break了，時(shí)間輪這是當(dāng)前槽都觸發(fā)了就行
• 每次檢測(cè)5個(gè)這種比較折中，因?yàn)樗麍?chǎng)景不是大量并發(fā)的服務(wù)器，rds cli的連接數(shù)量畢竟使用者內(nèi)部可控，而且不需要精確打擊，只要保障相對(duì)能及時(shí)清理就行，redis的網(wǎng)絡(luò)部分相對(duì)比較簡(jiǎn)單，業(yè)務(wù)場(chǎng)景可控，足夠了
• redis集群情況下如何做到兩個(gè)key必hash到一個(gè)節(jié)點(diǎn)？用{}

---

二、MySql

1. mysql

• 索引
• 物理存儲(chǔ)
• 聚簇索引
• 非聚簇索引
• 數(shù)據(jù)結(jié)構(gòu)
• B 樹
• hash
• fulltext
• R-tree
• 邏輯角度
• 唯一索引 unique
• 普通索引index
• 主鍵索引 primary key
• 全文索引 full index（myisam）
• 復(fù)合索引 （最左前綴原則）
• 類似 where a and b and c a b c 問題
• 聯(lián)合索引（a,b,c） 能夠正確使用索引的有（a=1）， （a=1 and b=1），（a=1 and b=1 and c=1）（b=1 and c =1
• 引擎類型
• myisam
• innodb
• 區(qū)別：

1. myisam采用非聚集索引，innodb采用聚集索引
2. myisam索引myi與數(shù)據(jù)myd文件分離，索引文件僅保存數(shù)據(jù)記錄指針地址。
3. myisam的主索引與輔助索引在結(jié)構(gòu)上沒區(qū)別，而innodb不一樣：innodb的所有輔助索引都引用主索引作為data域。
4. innodb支持事務(wù)，行級(jí)鎖。myisam不行。
5. innodb必須有主鍵，而myisam可以沒有。

• 相同點(diǎn)：
• 都是b tree 索引
• 存儲(chǔ)
• innodb

• 數(shù)據(jù)被邏輯的存在tablespace，extend（區(qū)）中有多個(gè)page，page（默認(rèn)16kb）里放row（每一行，大概每個(gè)page放2-200行記錄）
• .frm:tables format
• .ibd:table data & associated index data
• ubunut的frm文件和ibd文件可在目錄root@udev:/var/lib/mysql# ls中查看，下圖為innodb行格式,由下到上，均向上兼容

• Antelope 羚羊 對(duì)存放bolb或者大varchar存儲(chǔ)極長(zhǎng)的數(shù)據(jù)時(shí)，將行數(shù)據(jù)的前768字節(jié)存儲(chǔ)在數(shù)據(jù)頁(yè)中，后面通過偏移量指向溢出頁(yè)。
• compact 緊湊的
• redundant 多余的
• Barracuda 梭魚
• antelope對(duì)存放blob的數(shù)據(jù)完全溢出，在數(shù)據(jù)頁(yè)中只存在20個(gè)字節(jié)的指針，實(shí)際數(shù)據(jù)放在bolb page
• compressed
• dynamic
• more
• myisam
• frm(與innodb通用)，在磁盤的datadir文件
• myi
• myd
• 事務(wù)
• 原子性atomicity
• 一致性consistency
• 隔離性lsolation
• 持久性durability
• 分表數(shù)量級(jí)
• 單表在500w左右，性能最佳。BTREE索引樹 在3-5之間
• 隔離級(jí)別
• 事務(wù)的隔離性是數(shù)據(jù)庫(kù)處理數(shù)據(jù)的基礎(chǔ)之一，隔離級(jí)別是提供給用戶在性能和可靠性做除選擇和權(quán)衡的配置項(xiàng)目，以下四種情況都有一個(gè)前提（在同一個(gè)事物中）
• read_uncommited:臟讀，不加任何鎖，可能讀到未提交的行，見下圖

• read_commit：不可重復(fù)讀，只對(duì)記錄加記錄鎖，而不會(huì)在記錄間加間隙鎖。所以允許新的記錄插入到被鎖定記錄的附近，所以多次使用查詢語(yǔ)句時(shí)，可能得到不同的結(jié)果，non_repeatable_read，見下圖

• repeatable_read【默認(rèn)級(jí)別】：幻讀，返回第一次的查詢的快照（不會(huì)返回不同數(shù)據(jù)），但是可能有幻讀（phantom read），雖然第一次是個(gè)空，但是在session2中提交之后，發(fā)現(xiàn)已經(jīng)有了這條數(shù)據(jù)。見下圖

• serialize：解決了幻讀
• 索引機(jī)制（算法）
• hash
• b tree（m階b tree）
• 所有數(shù)據(jù)保存在葉子節(jié)點(diǎn)，有k個(gè)子樹的中間節(jié)點(diǎn)包含有k個(gè)元素
• 所有葉子節(jié)點(diǎn)包含了全部的元素信息，及指向這些元素記錄的指針，且葉子節(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大順序鏈接
• 所有的中間節(jié)點(diǎn)元素都同時(shí)存在于子節(jié)點(diǎn)，在子節(jié)點(diǎn)元素中都是最大（或最小）元素（或者說：每一個(gè)父節(jié)點(diǎn)的元素都出現(xiàn)在子節(jié)點(diǎn)中，是子節(jié)點(diǎn)的最大或者最小元素）
• 插入的元素，要始終保持最大元素在根節(jié)點(diǎn)中，再次說：所有的葉子節(jié)點(diǎn)包含了全量元素信息。每個(gè)葉子節(jié)點(diǎn)都帶有指向下個(gè)節(jié)點(diǎn)的指針，形成了有序鏈表

• b-tree【不要念成b減tree】
• 內(nèi)存操作（單一節(jié)點(diǎn)數(shù)量很多時(shí)，注意并不比二叉查找樹數(shù)量少，只是速度比硬盤要快）
• 自平衡
• 左旋、右旋
• mongoDB用的是balance tree
• 特點(diǎn)（m階的B樹）
• 根節(jié)點(diǎn)至少有兩個(gè)子女
• 每個(gè)中間節(jié)點(diǎn)都包括k-1個(gè)元素和k個(gè)孩子（m/2<=k<=m)
• 每個(gè)葉子節(jié)點(diǎn)都包括k-1個(gè)元素，（m/2<=k<=m)
• 所有的葉子節(jié)點(diǎn)位于同一層
• 每個(gè)節(jié)點(diǎn)中的元素從小到大排序，節(jié)點(diǎn)當(dāng)中k-1個(gè)元素正好是k個(gè)孩子包含元素的值域劃分
• b 與b-區(qū)別

1. b 中間節(jié)點(diǎn)沒有衛(wèi)星數(shù)據(jù)，而b-tree有衛(wèi)星數(shù)據(jù)（可以理解為key data的二維數(shù)組），所以前者同樣大小可以容納更多的節(jié)點(diǎn)元素。這樣又導(dǎo)致了b 比b更“矮胖”，更進(jìn)一步減少了io查詢次數(shù)。很好的解釋了下面這句話：在cluster index（聚集索引中），葉子節(jié)點(diǎn)直接包含衛(wèi)星數(shù)據(jù)；在非聚集索引中nonclustered index中，葉子節(jié)點(diǎn)帶有指向衛(wèi)星數(shù)據(jù)的指針。
2. b-只要查找到匹配元素，直接返回，網(wǎng)絡(luò)匹配元素處理中間節(jié)點(diǎn)還是葉子節(jié)點(diǎn)。而b 查詢必須查找到葉子節(jié)，相對(duì)于b-，b 無(wú)需返回上層節(jié)點(diǎn)重復(fù)遍歷查找工作，所以得出b-查找并不穩(wěn)定，而b 是穩(wěn)定的。
3. 針對(duì)范圍查詢，b-需要n次中序遍歷，而b 只需要通過子節(jié)點(diǎn)鏈表指針遍歷即可。
4. 鎖

• 種類
• optimistic lock樂觀鎖（并非真正的鎖，先嘗試在，再更改，loop and try）
• 特點(diǎn)：不會(huì)真死鎖，一定條件下有較高的沖突頻率和重試成本，但是相對(duì)悲觀可以有更好的并發(fā)量
• pessimistic lock悲觀鎖（先占有，再修改，再釋放）
• 粒度劃分
• 行鎖
• 表鎖
• 意向鎖 intention lock（表級(jí)鎖)
• 場(chǎng)景：A對(duì)表中一行進(jìn)行修改，B對(duì)整個(gè)表修改。如果沒有以下的兩個(gè)鎖，B將對(duì)全表掃描是否被鎖定。反之，A可以對(duì)某行添加意向互斥鎖（表級(jí)），然后再添加互斥鎖（行級(jí)），然后B只需要等待意向互斥鎖釋放）
• 意向共享鎖
• 意向互斥鎖
• 共享鎖shard lock 讀鎖（行鎖）
• 排它鎖exclusive lock 寫鎖（行鎖）
• 鎖的算法
• record lock：加到索引記錄上的鎖，如果通過where條件上鎖，而不知道具體哪行，這樣會(huì)鎖定整個(gè)表
• gap lock：某個(gè)區(qū)間的鎖定，對(duì)索引記錄中的一段連續(xù)區(qū)域的鎖。
• next-key lock：上兩者的結(jié)合
• 死鎖：

• 注意區(qū)分 deadlock VS lock wait timeout

1. 分庫(kù)分表
2. 主從
3. ACID
4. 覆蓋索引（復(fù)合索引）

• 定義：包含兩個(gè)或多個(gè)屬性列的索引稱為復(fù)合索引。如果查詢字段是普通索引，或者是聯(lián)合索引的最左原則字段，查詢結(jié)果是聯(lián)合索引的字段或者是主鍵。這種就不必通過主鍵（聚集索引再次查詢）
• 目的：減少磁盤io，不用回表
• b 樹索引

1. 聚集索引cluster index 一般為primary key

• 定義：按照每張表主鍵構(gòu)建一棵B TREE,葉子節(jié)點(diǎn)放的整張表的行記錄數(shù)據(jù)
• 與之相對(duì)應(yīng)的是輔助索引（secondary index）
• innodb存儲(chǔ)引擎支持覆蓋索引，即從輔助索引中可以查到查詢記錄，而不需要查詢聚集索引中的記錄。
• b平衡樹 樹索引

• 上圖對(duì)應(yīng)的表結(jié)構(gòu):

CREATE TABLE users( id INT NOT NULL, first_name VARCHAR(20) NOT NULL, last_name VARCHAR(20) NOT NULL, age INT NOT NULL, PRIMARY KEY(id), KEY(last_name, first_name, age) KEY(first_name)

• 一張表一定包含一個(gè)聚集索引構(gòu)成的b 樹以及若干輔助索引構(gòu)成的b 樹
• 每次給字段建一個(gè)索引，字段中的數(shù)據(jù)就會(huì)被復(fù)制一份出來。用于生成索引，（考慮磁盤空間）。不管何種方式查表，最終都會(huì)利用主鍵通過聚集索引來定位到數(shù)據(jù)。聚集索引（主鍵）是通往真實(shí)數(shù)據(jù)的唯一出路。

1. 輔助索引：非聚集索引都可以被稱作輔助索引，其葉子節(jié)點(diǎn)不包含行記錄的全部數(shù)據(jù)，僅包含索引中的所有鍵及一個(gè)用于查找對(duì)應(yīng)行記錄的【書簽（即主鍵或者說聚集索引）】，下面兩個(gè)圖為輔助索引（first_name，age）以及通過主鍵再次查找的過程

1. 聯(lián)合索引：與覆蓋索引沒有區(qū)別，或者理解為覆蓋索引是聯(lián)合索引的最優(yōu)解（無(wú)需通過主鍵回表）。
2. explain

• extra
• using index ：condition(用了索引，但是回表了)
• using where ：uning index（查詢的字段在索引中就能查到，無(wú)需回表）
• using index condition：using filesort（重點(diǎn)優(yōu)化：表明查到數(shù)據(jù)后需要再進(jìn)行排序，盡量利用索引的有序性。）
• using where：using index
• type（連接類型：join type），以下逐步增大
• system 系統(tǒng)表，磁盤io忽略不計(jì)（有些數(shù)據(jù)就已經(jīng)在內(nèi)存中）
• const 常量連接（加了where條件限制，命中主鍵pk或者唯一unique索引）
• eq_ref 主鍵索引或者非空唯一索引、等值連接；如果把唯一索引改為普通索引 等值匹配，可能type只為ref，因?yàn)榭赡芤粚?duì)多
• range 區(qū)間范圍 between and；where in，gt lt；（注意必須是索引）
• index 索引樹掃描，即需要掃描索引上的全部數(shù)據(jù)，比如innodb的count
• all 全表掃描
• select * 與索引（看主要命中條數(shù)與總條數(shù)，如果相近，用不到索引，就全回表了，如果是一定范圍，那就是range use indexcondition）
• rows（粗略統(tǒng)計(jì)，不是精確）

1. 其他：
2. varchar為啥為65535？compact行記錄的第一個(gè)字段為變長(zhǎng)字段長(zhǎng)度列表，為2個(gè)字節(jié)16位。參考
3. 一個(gè)表最多多少行？1023，具體也是看行格式的數(shù)據(jù)結(jié)構(gòu)即可，參考上文的參考鏈接。
4. 為什么建議給表加主鍵？主鍵的作用是把數(shù)據(jù)格式轉(zhuǎn)為索引（平衡樹）
5. 聯(lián)合索引在b 樹中如何存儲(chǔ)？
6. 為什么索引不直接用二叉查找樹，要用b樹，b 樹？主要考慮減少磁盤io（考慮磁盤物理原理及局部性與磁盤預(yù)讀的特性：）
7. myisam和innodb必須有主鍵嗎？innodb必須有，數(shù)據(jù)文件需要按照主鍵聚集，如果沒有innodb會(huì)自動(dòng)生成。

---

三、算法&數(shù)據(jù)結(jié)構(gòu)

• 最小堆：根節(jié)點(diǎn)為最小值，且節(jié)點(diǎn)比其他孩子小
• 平衡樹（avl 紅黑樹）
• 最大堆：根節(jié)點(diǎn)為最大值，且節(jié)點(diǎn)比其他孩子大
• sikplist
• hash
• hash 碰撞原因
• hash 碰撞解決方案
• 拉鏈,塞到鏈表里（想到了php max_input_vars）
• 開放尋址，一直找..
• 線性探測(cè)
• 二次探測(cè)再散列
• 偽隨機(jī)數(shù)
• 再hash
• 給定數(shù)值n，判斷n是斐波那契數(shù)列的第幾項(xiàng)？寫算法
• 反轉(zhuǎn)列表如A->B->C->D 到A->D->C->B
• 插入排序
• 數(shù)組與鏈表區(qū)別與聯(lián)系
• 鏈表操作
• 單鏈表刪除

p->next=p->next->next; if(head->next===null){ head=null }

• 單鏈表插入

new_node->next=p->next; p->next=new_node if(head===null){ head=new_node; }

• 應(yīng)用問題
• 如何實(shí)現(xiàn)一個(gè)LRU功能？【雙向鏈表】
• 如何實(shí)現(xiàn)瀏覽器前進(jìn)后退功能？【兩個(gè)?！?/li>

---

四、設(shè)計(jì)模式

1. 設(shè)計(jì)模式

• 單例模式 （static ，consturct）

static private $instance; private $config; private funciton __construct($config){ $this->config=$config; } private funciton __clone(){ } static public function instance($config){ if(!self::$instance instanceof self){ self::$instance=new self($config); } return self::$instance; }}

• 簡(jiǎn)單工廠（switch case include new return )

{ public function makeModule($moduleName, $options) { switch ($moduleName) { case Fight: return new Fight($options[0], $options[1]); case Force: return new Force($options[0]); case Shot: return new Shot($options[0], $options[1], $options[2]); } } } # 使用工廠方式 001 class Superman { protected $power; public function __construct() { // 初始化工廠 $factory = new SuperModuleFactory; // 通過工廠提供的方法制造需要的模塊 $this->power = $factory->makeModule(Fight, [9, 100]); // $this->power = $factory->makeModule(Force, [45]); // $this->power = $factory->makeModule(Shot, [99, 50, 2]); /* $this->power = array( $factory->makeModule(Force, [45]), $factory->makeModule(Shot, [99, 50, 2]) ); */ } }# 使用工廠方式 002 class Superman { protected $power; public function __construct(array $modules) { // 初始化工廠 $factory = new SuperModuleFactory; // 通過工廠提供的方法制造需要的模塊 foreach ($modules as $moduleName => $moduleOptions) { $this->power[] = $factory->makeModule($moduleName, $moduleOptions); } } } // 創(chuàng)建超人 $superman = new Superman([ Fight => [9, 100], Shot => [99, 50, 2]

• 門面模式
• 對(duì)客戶屏蔽子系統(tǒng)組件，減少子系統(tǒng)與客戶之間的松耦合關(guān)系

---

五、正則表達(dá)式

1. 正則表達(dá)式

• 應(yīng)用場(chǎng)景
• 范匹配
• 模版引擎
• 詞法分析器（lex）
• 常見正則

---

六、PHP

1. php

• 代碼解釋過程(大多的非編譯語(yǔ)言)
• lexical詞法分析，輸入為源代碼，輸出為token
• 語(yǔ)法分析 工具為文法（LALR），輸出為表達(dá)式，7.0為AST，涉及:
• 注釋
• 分號(hào) & 分隔符
• 變量
• 常量
• 操作數(shù)
• 類型檢查、關(guān)鍵字處理、導(dǎo)入，輸出為中間代碼。工具為選定的的編譯器優(yōu)化工具
• 中間代碼生成（Opcodes）
• 機(jī)器碼生成（編譯語(yǔ)言）
• session共享配置
• phpunit用法
• cookie購(gòu)物車和session購(gòu)物車的實(shí)現(xiàn)
• 弱類型實(shí)現(xiàn)
• 代碼規(guī)范
• 自動(dòng)化：sonarquebe jenkins
• 單元測(cè)試
• php進(jìn)程間如何通信
• 信號(hào)量
• 消息隊(duì)列
• 管道
• socket
• 共享內(nèi)存
• php并發(fā)模型
• 變量底層存儲(chǔ)結(jié)構(gòu)
• 常用的數(shù)組函數(shù)(列出10個(gè))
• array_combine(前面數(shù)組作為其鍵，后面數(shù)組做為其值)
• array_merage(合并兩個(gè)數(shù)組，后面覆蓋前面，但數(shù)字索引會(huì)重新索引，不會(huì)覆蓋)
• array_multisort
• php垃圾回收機(jī)制（gc）
• zend.enable_gc php.ini
• gc_enable() funciton
• 把session放入redis里面還會(huì)觸發(fā)類似文件的state session
• session.gc_probability （default 1）
• session.gc_divisor （default 100）
• session.gc_maxlifetime（單位秒）
• session.cookie_lifetime（單位秒，0表示直到關(guān)閉瀏覽器）
• session.save_path
• session_write_close （顯示關(guān)閉，后期使用需要顯示開啟）

---

七、操作系統(tǒng)

1. 操作系統(tǒng)

• 多線程
• 多進(jìn)程
• 協(xié)程的理解
• socket和管道的區(qū)別
• 進(jìn)程間通信手段
• 共享內(nèi)存
• rpc
• 管道
• 線程間通信手段
• 讀寫進(jìn)程數(shù)據(jù)段

---

八、網(wǎng)絡(luò)協(xié)議

1. 網(wǎng)絡(luò)協(xié)議

• http
• 構(gòu)成：起始行（GET =>200）,首部頭 （ACCEPT=>CONTENT-TYPE）,主體 name =》tongbo
• 版本：
• 1.0
• 1.1
• 2.0 :多路復(fù)用、流量控制
• 長(zhǎng)連接
• 在一個(gè)連接上發(fā)送多個(gè)數(shù)據(jù)包
• 心跳、如何發(fā)送心跳
• httpdns
• 定義：用http協(xié)議代替原始的udp dns協(xié)議，可以繞過運(yùn)營(yíng)商的local dns
• 解決問題：避免local dns造成的域名劫持問題和調(diào)度不精確問題（更多是在移動(dòng)客戶端）
• 其他解決方案
• 客戶端dns緩存
• 熱點(diǎn)域名解析
• 懶更新策略（ttl過期后再同步）
• post請(qǐng)求分割head 和body
• get vs post：
• get（
• 安全冪等，請(qǐng)求實(shí)體資源
• 參數(shù)只能url編碼，且參數(shù)長(zhǎng)度有限制
• 瀏覽器會(huì)自動(dòng)加cache
• post
• 附加請(qǐng)求實(shí)體于服務(wù)器
• 產(chǎn)生兩個(gè)tcp數(shù)據(jù)包
• 數(shù)據(jù)支持多種編碼格式
• resultful
• get：獲取資源
• post：新建資源
• put:更新完整資源
• delete：刪除資源
• patch：更新部分資源
• Rpc VS Http/rest
• http/rest
• 同步阻塞
• 異步回調(diào)
• 優(yōu)點(diǎn)
• 客戶端支持度高
• 監(jiān)控方便
• 注意點(diǎn)
• 通信效率低
• rest的put/delete支持度差
• rpc
• 分類
• soap（http）
• protocol buffer（tcp）
• thrift（tcp）
• 優(yōu)勢(shì)
• 二進(jìn)制支持
• 自動(dòng)生成服務(wù)端、客戶端代碼，支持語(yǔ)言豐富
• 自帶序列化
• 注意點(diǎn)
• 字段類型與定義問題
• tcp
• 面向連接，先建立（握手），然后釋放（揮手確認(rèn)拜拜）
• 只能點(diǎn)對(duì)點(diǎn)
• 可靠交付（相對(duì)來說），全雙工，接收和發(fā)送端都設(shè)有發(fā)送和接收cache
• 面向字節(jié)流（流：一連串，無(wú)結(jié)構(gòu)的的信息流，流入到進(jìn)程或從進(jìn)程流出的字節(jié)序列，而一個(gè)報(bào)文段多少字節(jié)是根據(jù)窗口值和網(wǎng)絡(luò)擁塞程度動(dòng)態(tài)變化的）
• 釋放：
• 客戶端：FIN_WAIT 1,停止發(fā)送數(shù)據(jù)給服務(wù)端。等待服務(wù)端確認(rèn)
• 服務(wù)端：ack ，進(jìn)入CLOSE_WAIT(關(guān)閉等待)，此時(shí)如果服務(wù)端有數(shù)據(jù)要發(fā)送，客戶端還可以接收。
• 客戶端收到服務(wù)端確認(rèn)后，進(jìn)入FIN_WAIT 2,等待服務(wù)器發(fā)出連接釋放報(bào)文段。
• 此時(shí)如果服務(wù)端沒有數(shù)據(jù)要發(fā)送，發(fā)送上步驟客戶端等待的釋放報(bào)文段，然后服務(wù)端進(jìn)入LAST_ACK
• 客戶端收到服務(wù)端的last_ack后，發(fā)出確認(rèn)，進(jìn)入TIME_WAIT,經(jīng)過2MSL后，客戶端關(guān)閉
• 服務(wù)端收到客戶端報(bào)文段后，進(jìn)入CLOSE

• 關(guān)于TIME_WAIT:
• time_wait是一種TCP狀態(tài)，等待2msl可以保證客戶端最后一個(gè)報(bào)文段能夠到達(dá)服務(wù)器，如果未到達(dá)，服務(wù)器則會(huì)超時(shí)重傳連接釋放報(bào)文段。使得客戶端、服務(wù)器都可以正常進(jìn)入到CLOSE狀態(tài)。
• 關(guān)于粘包
• 分包：在一個(gè)消息體或一幀數(shù)據(jù)時(shí)，通過一定的處理，讓接收方能從字節(jié)流中識(shí)別并截?。ㄟ€原）出一個(gè)個(gè)消息體。
• 短連接tcp分包：發(fā)送方關(guān)閉連接，接收方read 0，就知道消息尾了
• 長(zhǎng)連接TCP分包：
• 消息長(zhǎng)度固定or消息頭中加長(zhǎng)度字段
• 固定消息邊界，比如http:rn
• 利用消息本身格式，如xml，json
• 特性協(xié)議
• 停等
• 超時(shí)重傳
• 慢啟動(dòng)
• 滑動(dòng)窗口
• 快速重傳
• udp
• 無(wú)連接、best effort、面向報(bào)文（不合并、不拆分，保留邊界）
• 無(wú)擁塞控制、流量控制、首部開銷小（8個(gè)字節(jié)，而tcp有20個(gè)首部）
• 支持一對(duì)一，一對(duì)多，多對(duì)一
• 自定義協(xié)議
• rpc

---

九、大前端

1. js

• 百度統(tǒng)計(jì)的實(shí)現(xiàn)
• 基于cookie，引入js腳本及baidu個(gè)人賬戶id，讀取當(dāng)前信息，適當(dāng)節(jié)點(diǎn)發(fā)送請(qǐng)求給百度服務(wù)器

---

十、中間件

1. 中間件

• rebbitmq
• kafka
• Redis 隊(duì)列

---

十一、php框架

1. php框架

• ci
• yii
• laravel
• AppServiceProvider register：服務(wù)提供者注冊(cè)
• iocContainer：(工廠模式的升華：ioc容器)
• 控制反轉(zhuǎn)（inversion of control）可以降低計(jì)算機(jī)代碼之間的耦合，其中最常見的方式叫做依賴注入。（Dependence Injection），還有一種方式為依賴查找。
• 實(shí)現(xiàn)方式
• 基于接口:實(shí)現(xiàn)特定接口以供外部容器注入所依賴類型的對(duì)象。
• 基于set方法：還沒搞明白。
• 基于構(gòu)造函數(shù)：實(shí)現(xiàn)特定參數(shù)的構(gòu)造函數(shù)
• 管理類依賴
• 執(zhí)行（依賴注入DI)：通過構(gòu)造函數(shù)或者某些情況下通過setter方法將類依賴注入到類中，容器并不需要被告知如何構(gòu)建對(duì)象，因?yàn)樗麜?huì)使用php的反射服務(wù)自動(dòng)解析出具體的對(duì)象。
• swoole
• 依賴注入與控制翻轉(zhuǎn)

---

十二 、運(yùn)維

1. 運(yùn)維&架構(gòu)

• 服務(wù)器cpu99%如何分析
• mysql 占cpu如何分析
• php占cpu較高如何分析
• sso實(shí)現(xiàn)方法
• mysql優(yōu)化方法
• 如何提高監(jiān)測(cè)數(shù)據(jù)的準(zhǔn)確性
• docker 原理及引用及編排管理

---

十三、golang

1. golang

• todo

---

十四、 Linux

1. linux

• epoll
• 查看負(fù)載：cat /proc/loadavg || w || top
• df
• top shift M
• free
• ipstat
• strace
• grep [-A ,-B, -C]HTTP/1.1" 200 access.log |wc -l
• socket和管道（pipe）的區(qū)別:socket全雙工，pipe半雙工*2
• awk
• awk {print $1} access.log |sort |uniq |wc -l

---

十五、nginx

1. nginx

• worker_connections
• upstream weight
• 負(fù)責(zé)均衡實(shí)現(xiàn)方式
• 輪詢
• ip 哈希
• 指定權(quán)重
• 第三方
• fair
• url_hash

---

十六、分布式 | 微服務(wù)

1. 分布式

• redis 分布式鎖問題
• cap 及常見應(yīng)用關(guān)注cap哪兩點(diǎn)

1. 微服務(wù)

• 最佳原則
• 高內(nèi)聚：修改一個(gè)功能，只需要改一個(gè)服務(wù)
• 低耦合：修改了一個(gè)地方，不需要改其他的地方（下游消費(fèi)者不受影響）
• 業(yè)務(wù)內(nèi)原則：
• 新服務(wù)用新的微服務(wù)，確定無(wú)誤后保留推進(jìn)，否則調(diào)整
• 老的保留，直到新服務(wù)穩(wěn)定再切換
• 必需的的監(jiān)控與日志|生產(chǎn)-訂閱—消費(fèi)模型
• 嘗試對(duì)外不可見的服務(wù)先做試點(diǎn)，錯(cuò)誤郵件、日志、系統(tǒng)內(nèi)調(diào)用、api內(nèi)部分成熟接口
• 考慮問題
• 服務(wù)發(fā)現(xiàn)是否需要客戶端自實(shí)現(xiàn)？
• 服務(wù)可用性保證
• 要不要拆MySQL表？保證服務(wù)底層的高內(nèi)聚？異或是存到nosql
• 數(shù)據(jù)一致性問題？主從|緩存
• 服務(wù)監(jiān)控日志存儲(chǔ)及查詢功能是否需要自實(shí)現(xiàn)？
• 基于事件 生產(chǎn)|消費(fèi)模型選型
• rabbitmq
• kafka
• redis 隊(duì)列
• 請(qǐng)求失敗是否需要存入隊(duì)列以便再次發(fā)起（最大重試次數(shù)與死信隊(duì)列）？

---

其他

1. 其他

• 兩個(gè)絕對(duì)路徑，求之間的相對(duì)路徑
• 分布式
• 基礎(chǔ)
• cap原理
• 解決多個(gè)節(jié)點(diǎn)數(shù)據(jù)一致性的方案其實(shí)就是共識(shí)算法
• 分布式協(xié)議
• Paxos：Proposer， Acceptor， Learner
• ZAB：Follower, Leader, Observer
• raft：leader ，follower，candidate

• 分布式工具
• zk：zab（base paxos）protocol，
• etcd：raft protocol（mini PAXOS）,k-v database

具體

1. 如何對(duì)一個(gè)大文件排序（裝不進(jìn)內(nèi)存的）-好未來

• 思路：
• map reduce
• 分割成小文件（臨時(shí)文件）
• 去重
• awk grep end for sort
• 輸入輸出緩沖區(qū)

1. 快速排序代碼
2. 冒泡排序代碼

• 外層循環(huán) 0到n-1 //控制比較輪數(shù) n 表示元素的個(gè)數(shù)
• 內(nèi)層循環(huán) 0到n-i-1 //控制每一輪比較次數(shù)
• 兩兩比較做交換
• 外層循環(huán)開始聲明 is_switch flag為false，內(nèi)層循環(huán)有交換為true，外層循環(huán)結(jié)束時(shí)判斷無(wú)switch break

1. 歸并排序代碼

,