• CPU組成與功能

• 數(shù)據(jù)通路與總線系統(tǒng)結(jié)構(gòu)

• 總線結(jié)構(gòu)與CPU指令周期

• 硬布線控制器設(shè)計(jì)

  
  

• 微程序控制器

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

• 微指令格式

• 單周期MIPS CPU

• 多周期MIPS CPU數(shù)據(jù)通路

• 習(xí)題

• 快速面經(jīng)

• Q: 寫入存儲系統(tǒng)的粒度太大，會不會導(dǎo)致數(shù)據(jù)原子性問題？例如一次性寫100MB，如果系統(tǒng)突然crash，會不會只有一部分?jǐn)?shù)據(jù)持久化了，另一部分丟失了？如果要解決原子性問題，一般會設(shè)計(jì)什么機(jī)制？

• A:?如果寫入存儲系統(tǒng)的粒度太大，會導(dǎo)致數(shù)據(jù)原子性問題。為了解決這個問題，一般會采用分布式事務(wù)機(jī)制，即將一次性寫入的數(shù)據(jù)分割成多個小塊，每個小塊都要經(jīng)過一系列的事務(wù)操作，確保每個小塊的數(shù)據(jù)都能夠持久化，從而保證數(shù)據(jù)的原子性。

• Q: 在從應(yīng)用程序到存儲介質(zhì)的鏈路上，無論讀還是寫，數(shù)據(jù)可能要被拷貝好幾次，這幾次拷貝能不能去掉？如果我們?nèi)サ舸蟛糠挚截惒僮鳎瑫惺裁锤弊饔?，要怎么緩解副作用?/p>

• 是的，可以通過使用直接訪問技術(shù)來減少數(shù)據(jù)拷貝次數(shù)。例如，可以使用內(nèi)存映射文件（MMF）技術(shù)，將應(yīng)用程序的內(nèi)存直接映射到存儲介質(zhì)，從而避免數(shù)據(jù)拷貝。但是，這種技術(shù)也會帶來一些副作用，例如安全性問題和性能問題。為了緩解這些副作用，可以使用安全機(jī)制，如加密和訪問控制，來保護(hù)數(shù)據(jù)安全，并使用緩存技術(shù)來提高性能。
  

• Q:?一個關(guān)系型數(shù)據(jù)庫大概率是會被并發(fā)訪問的，如果要保證并發(fā)安全，除了在行數(shù)據(jù)上加悲觀鎖還有其他方式嗎？

• 除了悲觀鎖之外，還可以使用樂觀鎖來保證并發(fā)安全。樂觀鎖通過在每次更新操作前檢查數(shù)據(jù)的版本號來實(shí)現(xiàn)，如果版本號不匹配，則拒絕更新操作，從而避免數(shù)據(jù)的不一致性。此外，還可以使用分布式鎖來保證并發(fā)安全，它可以通過在多個節(jié)點(diǎn)上同步鎖定數(shù)據(jù)來實(shí)現(xiàn)。
  

• Q:?在數(shù)據(jù)庫領(lǐng)域，把數(shù)據(jù)按行存和按列存各有好處，你能從性能優(yōu)先的角度設(shè)計(jì)出一種混合存儲格式嗎？

• 可以設(shè)計(jì)出一種混合存儲格式，它可以將數(shù)據(jù)按行存儲和按列存儲相結(jié)合，以提高性能。例如，可以將數(shù)據(jù)按行存儲在內(nèi)存中，而將數(shù)據(jù)按列存儲在磁盤上，以便更快地訪問和更新數(shù)據(jù)。此外，可以使用索引來提高查詢性能，并使用緩存來減少磁盤訪問次數(shù)。
  

• Q:?WAL 日志到底是如何保證數(shù)據(jù)的持久化，宕機(jī)后數(shù)據(jù)不丟失的？相比于其他方案，WAL 日志都有什么優(yōu)勢？

• WAL就像日志中心一樣，它被同一個region server中的所有region共享。當(dāng)客戶端啟動一個操作來修改數(shù)據(jù)，該操作便會被封裝成一個KeyValue對象實(shí)例中，并通過RPC調(diào)用發(fā)送出去。這些調(diào)用成批的發(fā)送給含有匹配region的HRegionServer。一旦KeyValue到達(dá)，它們會被發(fā)送到管理相應(yīng)行的HRegion對象實(shí)例。數(shù)據(jù)便被寫入到WAL，然后放入到實(shí)際擁有記錄的存儲文件的MemStore中。最后當(dāng)memstore達(dá)到一定的大小或者經(jīng)歷一個特定時間之后，數(shù)據(jù)就會異步地連續(xù)寫入到文件系統(tǒng)中。在寫入的過程中，數(shù)據(jù)以一種不穩(wěn)定的狀態(tài)存放在內(nèi)容中，即使在服務(wù)器完全崩潰的情況下，WAL也能夠保證數(shù)據(jù)不丟失，因?yàn)閷?shí)際的日志存儲在HDFS上。其他服務(wù)器可以打開日志然后回放這些修改。

• Q:?除了 Undo Log 之外，是否還有其他方案可以實(shí)現(xiàn) MVCC？
  

• 比如：使用版本號來標(biāo)記每個記錄，使用鎖定機(jī)制來防止沖突，使用快照讀取來實(shí)現(xiàn)讀取的隔離性，使用多版本并發(fā)控制來實(shí)現(xiàn)寫入的隔離性等。

• Q:?基于代價的優(yōu)化器一般需要考慮哪些代價？

• 總代價 = IO 代價 + CPU 代價COST = P*a_page_cpu_time + W * T
  

• Q:?執(zhí)行器的執(zhí)行模型，除了本課中提到的火山模型是否還有其他模型？相比于火山模型有什么優(yōu)劣勢？

• 物化模型（Materialization Model）——物化模型的處理方式是：每個 operator 一次處理所有的輸入，處理完之后將所有結(jié)果一次性輸出。物化模型更適合OLTP負(fù)載，這些查詢每次只訪問小規(guī)模的數(shù)據(jù)，只需要少量的函數(shù)調(diào)用。

• 向量化/批處理模型（Vectorized / Batch Model）——向量化模型 和 火山模型 類似，每個 operator 需要實(shí)現(xiàn)一個 next() 函數(shù)，但是每次調(diào)用 next() 函數(shù)會返回一批的元組（tuples），而不是一個元組，所以向量化模型也可稱為批處理模型。向量化模型是火山模型和物化模型的折衷。向量化模型比較適合 OLAP 查詢，因?yàn)槠浯蟠鬁p少了每個 operator 的調(diào)用次數(shù)，也就簡單減少了虛函數(shù)的調(diào)用。Presto、snowflake、SQLServer、Amazon Redshift等數(shù)據(jù)庫支持這種處理模式。Spark 2.x 的 SQL 引擎開始也支持向量化執(zhí)行模型。在 Hive 中使用 向量化執(zhí)行的方式：1、必須以 ORC 格式來存儲數(shù)據(jù)，2、將 hive.vectorized.execution.enabled 參數(shù)設(shè)置為 true

• Q:?InnoDB 的 B+ Tree 是怎么實(shí)現(xiàn)的？

  基本特征：該數(shù)據(jù)結(jié)構(gòu)的基本特點(diǎn)和性質(zhì): ①多路節(jié)點(diǎn)②一個樹節(jié)點(diǎn)中，有多個數(shù)據(jù)，數(shù)據(jù)個數(shù)大于等于N時，分裂成三部分：左、中、右，這三部分變成三個樹節(jié)點(diǎn)，中間樹節(jié)點(diǎn)成為左右兩部分的父節(jié)點(diǎn)。③所有葉子節(jié)點(diǎn)形成一條有序鏈表④所有數(shù)據(jù)都在葉子節(jié)點(diǎn)上

  大體結(jié)構(gòu)設(shè)計(jì)：①一個樹節(jié)點(diǎn)看作一個類；②樹節(jié)點(diǎn)類里面有多個數(shù)據(jù)元素節(jié)點(diǎn)，數(shù)據(jù)元素看作一個類；③樹節(jié)點(diǎn)類中有父節(jié)點(diǎn)指針④數(shù)據(jù)元素節(jié)點(diǎn)中有左右子樹節(jié)點(diǎn)指針。設(shè)計(jì)的是同一個樹節(jié)點(diǎn)內(nèi)，左邊第一個元素節(jié)點(diǎn)左右可能都有樹節(jié)點(diǎn)，其他元素節(jié)點(diǎn)只有右邊有子樹節(jié)點(diǎn)；⑤葉子節(jié)點(diǎn)中維護(hù)了一個前后葉子節(jié)點(diǎn)的指針，從而形成一條鏈表

????????????????結(jié)構(gòu)設(shè)計(jì)：定義類①首先，B+Tree是有序的，存的數(shù)據(jù)類型是不確定的。所以需要一個比較器Comparable/Comparator,為了方便選擇了Comparable。還需要一個泛型，但這個泛型具體的類型必須得實(shí)現(xiàn)了Comparable接口，即該泛型有上限，方便比較。②B+Tree,得持有一個整棵樹的一個入口，即Root節(jié)點(diǎn);一個鏈表的入口，即head節(jié)點(diǎn)。③B+Tree的結(jié)構(gòu)特點(diǎn)，決定了它需要一些內(nèi)部類。樹節(jié)點(diǎn)內(nèi)部類，樹節(jié)點(diǎn)里面單個數(shù)據(jù)類。④BTree需要分裂平衡，觸發(fā)條件是，當(dāng)一個樹節(jié)點(diǎn)的數(shù)據(jù)個數(shù)大于等于N時，向上分裂。所以需要一個全局變量N。

????????????構(gòu)造方法：要傳遞一個參數(shù)進(jìn)來的，幾路平衡樹，即一個樹節(jié)點(diǎn)有幾個元素。關(guān)系到分裂平衡。

????????????添加數(shù)據(jù)：①從root節(jié)點(diǎn)開始比較查找，依次比較根節(jié)點(diǎn)中所有數(shù)據(jù)元素。沒找到合適的位置，繼續(xù)往下一個節(jié)點(diǎn)找。②當(dāng)定位到某個樹節(jié)點(diǎn)，在該節(jié)點(diǎn)中找到插入位置，將數(shù)據(jù)插入樹節(jié)點(diǎn)。③判斷該樹節(jié)點(diǎn)是否大于等于N。
??a. 是，則將該樹節(jié)點(diǎn)分裂成三個節(jié)點(diǎn)，形成一棵小子樹。
??b. 否，直接插入。

• Q:?InnoDB 的 buffer pool 是怎么實(shí)現(xiàn)頁面管理和淘汰的？

• A: innodb buffer pool 采用經(jīng)典的 LRU 算法來進(jìn)行頁面淘汰，以提高緩存命中率。與傳統(tǒng)的 LRU 算法相比，buffer pool 中的 LRU 列表其中間位置被打了一個 old 標(biāo)識，可以簡單的理解為將 LRU 列表分為兩個部分，這個標(biāo)記到 LRU 列表頭部的數(shù)據(jù)頁稱為 young 數(shù)據(jù)頁池，這個標(biāo)志到 LRU 列表尾部的數(shù)據(jù)頁稱之為 old 數(shù)據(jù)頁池。當(dāng)一個頁從磁盤上加載到緩存池的時候，會將它放在 old 標(biāo)識之后的第一個位置，也就是說放在了 old 池子中（“中點(diǎn)插入策略”）。這個機(jī)制保證了在做大表的一次性全表掃描時，即使有大量新進(jìn)來的數(shù)據(jù)頁，也會被存放在 old 池子中，當(dāng) old 池子的大小不夠緩存新進(jìn)來頁面的時候，也只是在 old 池子中進(jìn)行循環(huán)沖洗，這樣就不會沖洗 young 池子中的熱點(diǎn)頁，從而保護(hù)了熱點(diǎn)頁。這就是 buffer pool LRU 算法的簡單機(jī)制。
  

• Q:?列存和行存的差別是什么，使用場景有什么不同？

• A:?分析類查詢往往只查詢一個表里面很少的幾個字段，Column-Store只需要從磁盤讀取用戶查詢的Column，而Row-Store讀取每一條記錄的時候你會把所有Column的數(shù)據(jù)讀出來，在IO上Column-Store比Row-Store效率高很多，因此性能更好。當(dāng)你的核心業(yè)務(wù)是 OLTP 時，一個行式數(shù)據(jù)庫，再加上優(yōu)化操作，可能是個最好的選擇。
  當(dāng)你的核心業(yè)務(wù)是 OLAP 時，一個列式數(shù)據(jù)庫，絕對是更好的選擇。

• Q:?列存的優(yōu)點(diǎn)有哪些？

• A:?列存儲數(shù)據(jù)庫的優(yōu)點(diǎn)有： 一、查找速度快；二、可擴(kuò)展性；三、更容易進(jìn)行分布式擴(kuò)展

• Q:?列存的缺點(diǎn)有哪些？

• A:??整行讀取時，可能需要多次I/O操作。

• Q:?列存適合什么樣的索引？

• A:?列存儲索引是聚集或非聚集索引。

• Q:?ClickHouse的列存是什么樣的存儲架構(gòu)？

• A:?ClickHouse采用列存格式作為單機(jī)存儲,并且采用了類LSM tree的結(jié)構(gòu)來進(jìn)行組織與合并。

• Q:?ClickHouse的索引是怎么設(shè)計(jì)的？

• A:?ClickHouse索引有主索引（Primary Indexes）和二級索引（Skipping Indexes)。一級索引：數(shù)據(jù)按照主鍵排序存儲在磁盤上→數(shù)據(jù)被組織成顆粒以進(jìn)行并行數(shù)據(jù)處理→主索引被用來選擇顆?！鷺?biāo)記文件用來定位顆粒。

• Q:?ClickHouse的查詢是怎么使用索引的？

• A:?ClickHouse使用它的稀疏主索引來快速(通過二分查找算法)選擇可能包含匹配查詢的行的顆粒。