一、數據結構中Passes和I/O cost

Passes和I/O cost

pass翻譯成“趟”。一趟過去做若干歸并。

I/O cost翻譯成“I/O開銷”。I/O是整個操作系統(tǒng)數據交換與人機交互的通道，現(xiàn)在系統(tǒng)都有可能處理大量文件，大量數據庫操作，而這些操作都依賴于系統(tǒng)的I/O性能。

BIO （Blocking I/O）：同步阻塞I/O模式，數據的讀取寫入必須阻塞在一個線程內等待其完成。這里使用那個經典的燒開水例子，這里假設一個燒開水的場景，有一排水壺在燒開水，BIO的工作模式就是， 叫一個線程停留在一個水壺那，直到這個水壺燒開，才去處理下一個水壺。但是實際上線程在等待水壺燒開的時間段什么都沒有做。

NIO （New I/O）：同時支持阻塞與非阻塞模式，但這里我們以其同步非阻塞I/O模式來說明，那么什么叫做同步非阻塞？如果還拿燒開水來說，NIO的做法是叫一個線程不斷的輪詢每個水壺的狀態(tài)，看看是否有水壺的狀態(tài)發(fā)生了改變，從而進行下一步的操作。

AIO （ Asynchronous I/O）：異步非阻塞I/O模型。異步非阻塞與同步非阻塞的區(qū)別在哪里？異步非阻塞無需一個線程去輪詢所有IO操作的狀態(tài)改變，在相應的狀態(tài)改變后，系統(tǒng)會通知對應的線程來處理。對應到燒開水中就是，為每個水壺上面裝了一個開關，水燒開之后，水壺會自動通知我水燒開了。

IO調用步驟

進程中的IO調用步驟大致可以分為以下四步：

進程向操作系統(tǒng)請求數據 ;

操作系統(tǒng)把外部數據加載到內核的緩沖區(qū)中;

操作系統(tǒng)把內核的緩沖區(qū)拷貝到進程的緩沖區(qū) ;

進程獲得數據完成自己的功能 ;

當操作系統(tǒng)在把外部數據放到進程緩沖區(qū)的這段時間（即上述的第二，三步），如果應用進程是掛起等待的，那么就是同步IO，反之，就是異步IO，也就是AIO 。

延伸閱讀：

二、數據庫IO特點

IO有四種類型：連續(xù)讀，隨機讀，隨機寫和連續(xù)寫，連續(xù)讀寫的IO size通常比較大(128KB-1MB)，主要衡量吞吐量，而隨機讀寫的IO size比較小(小于8KB)，主要衡量IOPS和響應時間。數據庫中的全表掃描是連續(xù)讀IO，索引訪問則是典型的隨機讀IO，日志文件是連續(xù)寫IO，而數據文件則是隨機寫IO。

數據庫系統(tǒng)基于傳統(tǒng)磁盤訪問特性來設計，最大特點是日志文件采用sequential logging，數據庫中的日志文件，要求必須在事務提交時寫入到磁盤，對響應時間的要求很高，所以設計為順序寫入的方式，可以有效降低磁盤尋道花費的時間，減少延遲時間。日志文件的順序寫入，雖然是物理位置是連續(xù)的，但是并不同于傳統(tǒng)的連續(xù)寫類型，日志文件的IO size很小(通常小于4K),每個IO之間是獨立的(磁頭必須抬起來重新尋道，并等待磁盤轉動到相應的位置)，而且間隔很短，數據庫通過log buffer(緩存)和group commit的方式(批量提交)來達到提高IO size的大小，并減少IO的次數，從而得到更小的響應延遲，所以日志文件的順序寫入可以被認為是“連續(xù)位置的隨機寫入”，更關注IOPS，而不是吞吐量。

數據文件采用in place uddate的方式，意思是數據文件的修改都是寫入到原來的位置，數據文件不同于日志文件，并不會在事務commit時寫入數據文件，只有當數據庫發(fā)現(xiàn)dirty buffer過多或者需要做checkpoint動作時，才會刷新這些dirty buffer到相應的位置，這是一個異步的過程，通常情況下，數據文件的隨機寫入對IO的要求并不是特別高，只要滿足checkpoint和dirty buffer的要求就可以了。