存儲系統的實現-探析存儲的機制和原理
這一篇主要想寫寫一些自己對于存儲的思考和領悟，因為有些東西自己實踐過，所以感觸過更加深一些，技術上我還是認為自己實現和看別人的代碼在感觸上是不同的。
這里假設一個圖書館，假如說書就是要我們要放的數據，會怎么放。最土的辦法就是隨便往里面丟，然后毫無章法，這樣每次找書我們就累死了，因為必須每一本書都要一本書一本書翻過去（有點像DB的全表掃描），如果運氣好可能會在比較前面找到，最差情況下就是翻遍整個圖書館最后找到了這本書。所以現實中圖書館的書也不是隨便丟了，都是各個書架對應各種類型的書籍，這樣才方便查找。具體到我們的數據存儲也是這樣的，不可能有一條數據就往文件里面放，這樣當數據量一大整個查找就非常困難了。
我對于整個存儲的實現是非常簡單的一種，沒有DB中按照各種字段進行查找，只有按照ID進行查找，按照ID進行刪除。我實現的初衷也并非要重復制造輪子，而是在實現的過程中更好的理解這些存儲的基本原理。
系統架構圖
先看一下整個系統的架構圖，了解一下整個分層思想。
第一層為整個入口，包括插入、更新、查詢、刪除等入口。核心是對于文件的管理，包括文件的分配、讀寫文件等等。這里所有對文件的操作都是用RandomAccessFile這個類去操作。用這個類的好處是可以知道文件具體的偏移。另外具體的存儲文件分為索引文件和數據文件。也就是對應存儲那一層的Index和Data。這里和數據庫的文件分配有些類似。索引單列成一個文件主要是為了加快查詢速度。一個好處是可以利用索引的有序性然后利用各種查找算法，我這里利用的是“跳躍表”算法。另外由于索引文件通常比真實的數據文件小很多，查找過程中可以減少多次IO，可以得到性能上的提升。
數據格式
在上面的系統架構圖中可以看出第三層的存儲分為三個文件，一個是管理文件（Manager），索引文件（Index），數據文件（Data）。
名詞解釋
管理文件（Manager）：理解為一個文件的統一管理者，下面講文件格式的時候會詳細講。
索引文件（Index）：索引文件就比較好理解，用過數據庫的大概都知道索引文件這個概念。
數據文件（Data）：數據文件就是真實數據的存儲塊。
管理文件（Manager）
上面在名詞解釋中大概講到了Manager這一個文件的職責。如果要講清楚這個文件職責之前必須要對整個存儲空間配置的機制有一些了解。這里先用文字描述一下：假設我要存儲一段數據，最簡單的方式就是用RandomAccessFile直接往文件里面按行寫，每一行就是一條記錄，并且每行都需要一個標識，來標識這一行的唯一性，有點像DB里面主鍵的概念，這樣刪除的時候就不需要移動整個文件的位移（物理刪除就需要移動整個位移），只需要把這一行置為可用。那么回到一個問題：怎么知道當前行是可用還是已經被占用，這里就需要對空間有一個管理。就像買票，如果我買了A座位的票，那么A座位的票就是被使用狀態，如果退票（對應我們的刪除）那么這個座位還可以出售給其他人。總結一下，Manager其實就是對整個空間的一個管理文件，存儲著空間的使用狀態。
說了這么多，上一張圖來看看這個Manager具體格式：
整個文件由5部分組成：文件唯一標識塊、使用狀態、文件類型、文件超始偏移、文件結束偏移。總共是22個字節。這幾個字段還是比較好理解，文件類型下面會講，文件起始偏移和結束偏移其實說白了是一個坐標，告訴你這個位置在哪里，你直接去那兒找就好了。
這里先說一下整個文件的配置機制，是采用定長分配。簡單的說就是一個房間開始就會分配成多種大小的小格，就是上圖右上角所看到的256bytes、512bytes、4K、1024K，這樣分配的好處是便于管理，避免碎片的產生（為了解決碎片問題會有定期的文件合并）。定額分配就會規避碎片的問題，那么帶來的弊端可能導致數據的不連續性。
索引文件（Index，嚴格來講是一個主鍵文件）
索引文件如果用過DB的就應該比較好理解，不理解的可以參考字典的目錄，重點可以看一下整個索引文件文件格式：
從上圖可以看出索引文件的大小是固定的，由索引文件標識、數據文件起始偏移、索引使用狀態三部分組成，總共是13bytes。這里稍微解釋一下數據文件起始偏移，其實就是一個定位數據具體位置的標志位，一般查找如果走索引的話會先找到具體的索引項，然后根據數據文件起始偏移找到具體的數據位置。這里為什么會有一個索引使用狀態，因為索引的分配是不走Manager管理的（理論上也是要走 Manager管理），但是這里為了簡單。另外我這里的索引嚴格意義來講是主鍵，因為索引文件標識ID只能表示一個int類型。和真實的索引格式有一定的區別。
數據文件
接下來就是最復雜的數據文件存儲格式了，先上一張圖再進行解釋
一個數據空間由固定的29bytes+數據長度組成，也就是說申請256bytes容量的空間有29bytes是得不到利用的。就如我上圖中所出的，由于每個空間都是定長的，但是不一定每個數據都只申請一個空間，這里舉一個簡單的例子：300bytes字節的數據會申請一個256bytes空間和一個 128bytes的空間，我在這里定為A和B，而在物理上這兩個空間極有可能是不連續的。那么我在A找到了一部分數據，然后再去B找到余下的數據，再做一個拼接，一個完整的數據就出來了。那么這里就可以用鏈式存儲的方式進行，也可以用另外的方式進行，比如說在某個地方存儲一個完整數據的所有空間地址。
具體操作數據
上面講到了一些數據的存儲協議，那么接下來就會講如何存儲數據、刪除數據、更新數據。
Insert數據
這里先以一張圖來看看整個Insert的過程：
從上面的的流程中可以看出insert大概有四步：
格式化數據：因為一般數據都會有一定的格式，這里就需要定義具體的格式，比如說數據中 Table的概念。這樣才可以按照約定進行格式化。不過就最后轉化的結果而言是一個byte[]，但是具體格式化的過程會有一些講究，比如說一個 String，你必須知道這個String的長度，就是對應到byte[]數組的具體哪一段。其他定長類型好一些，比如說int，就是存儲4個字節，long就存儲8個字節。
申請存儲空間：這一步在上面講到了一些，經過格式化數據后可以知道當前存儲數據的大小，那么可以按照這個大小進行分配一些合適的空間。
寫數據文件：拿到存儲空間，就把byte[]往里面填就好了。
寫索引文件：嚴格意義來講我這里并非索引而是主鍵，而且我這里的索引都是固定的int類型，相對來說狹隘了一些。
Delete數據
我這里只能根據ID（索引文件里面的ID）進行刪除，采用其他列進行刪除的方式目前還是不支持的。
查找索引：其實我這里的查找都簡化成了簡單的根據ID進行查找，如果根據其他字段進行查找就不是這樣了。具體的查找算法會在后面Select數據給出。
查找數據：找到了索引（主鍵）后就可以根據這個索引找到具體的數據地址，然后把這些空間地址置為可用（具體看一下Manger文件格式）
回收索引：這個時候索引文件的使用狀態就派上用場了。
Update數據
這里我的update策略是會先刪除一條記錄，然后再插入一條記錄進行處理，這樣的好處是簡單方便，因為本身的更新也涉及到空間的回收一重用。且我在這里格式化數據沒有細化到數據庫字段的概念，所有無法按字段進行管理。
Select數據
在刪除數據里面就會用到根據ID進行查找數據。從索引文件的特性可以知道索引文件是有序的，那么就可以根據這個特性進行一些查找算法，我這里采用的查找算法就是"跳躍表"算法，這個算法的原理其實就是改變步長 。具體可以參考《跳躍表實現索引檢索》，這里就不再做詳述。
總結
上面我寫的存儲應該是最簡單的，對于學習存儲的原理還是很有幫助的。比如說索引，空間的預分配，為什么要這么做會有一個非常好的認識。因為很多存儲，比如說memcached都是采用這種方式進行分配空間。嘗試著自己實現也是一種幫助自己理解的手段。
來自：http://blog.csdn.net/luohuacanyue/article/details/17617847
來自：http://blog.csdn.net/luohuacanyue/article/details/17617847
本文由用戶 jopen 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。
轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。
本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！