Lucene有一個問題一直困擾著我, 就是如何在索引文件的時候節省空間, 合理的分配不大也不小的空間有助於在提高搜索速度的同時也能夠監測內存的使用情況, 在內存使用到達某個阈值的時候可以觸發合並的操作
之前在寫一個小程序, 來實現類似於Lucene索引文件的時候, 我是用c++寫的, 沒有使用內存池, 需要的時候就找操作系統"要"一塊, 不需要的時候就還給它, 這樣不僅僅在內存的頻繁的分配中造成大量的內存碎片, 而且沒有用內存池還會帶來操作系統的換頁情況, 使得本來一共就3M左右的文件讀取到內存中, 進行分詞操作後要70M(當然是增加了一些屬性了, 不過也沒有這麼高吧!), 把豆腐都盤成肉價錢了.
另外還是聲明一下: 本文的著作權歸LeftNoteasy所有, 如果需要轉載請保留這句話並注明出處.
在TermsHashPerField中有三個Pool, CharBlockPool, IntBlockPool, ByteBlockPool. 三者之間非常類似, 其實我覺得Lucene的開發者應該加以統一, 把代碼進行規范化處理, 我看到Lucene中隨處可見重復的代碼, 這樣不僅給開發帶來很多重復的工作, 而且對維護也不一定好, 如果那一天發現某個算法可以改進或者出現了bug, 那估計得忙上一陣子了.
三個緩存都是來自於TermsHashPerThread, 也就是說, 每個線程都有獨立的Pool,這樣的設計很好, 可以利用多核來對索引進行加速.
1. CharBlockPool
1: final class CharBlockPool
2: {
3: char[][] buffers = new char[10][];
4: int bufferUpTo = -1;
5: int charUpTo = DocumentWriter.CHAR_BLOCK_SIZE;
6: char[] buffer;
7: int charOffset = -DocumentWriter.CHAR_BLOCK_SIZE;
8: }
這裡給出了CharBlockPool的主要成員變量, Lucene的Buffer設計有一個特點, 就是采用了二維數組, 就像房子一樣, 最開始是個平房, 如果不夠住了就往天上蓋, 越蓋越高, 當然, 是當前層住不下了才蓋新的一層.
buffers就是這個樓房
bufferUpTo是這個樓房有多少層
charUpTo是我們在當前層的定位(where we are)
charOffset是我們總體的偏移量.
下面看看CharBlockPool的nextBuffer()函數, 也就是房子不夠, 修樓房的函數:
1: public void nextBuffer() {
2: if (1+bufferUpto == buffers.length) {
3: char[][] newBuffers = new char[(int) (buffers.length*1.5)][];
4: System.arraycopy(buffers, 0, newBuffers, 0, buffers.length);
5: buffers = newBuffers;
6: }
7: buffer = buffers[1+bufferUpto] = docWriter.getCharBlock();
8: bufferUpto++;
9:
10: charUpto = 0;
11: charOffset += DocumentsWriter.CHAR_BLOCK_SIZE;
12: }
程序應該是比較好理解的, 首先看看buffers.length(房子的規劃)是不是不夠了, 如果規劃少了, 就把規劃*1.5得到新的規劃, 比如本來預計房子會修到10層, 就提高到15層.
然後把bufferUpto指針++, 從docWriter.getCharBlock函數來"要"內存, 在getCharBlock()函數中還會對申請的內容進行記載, 以進行內存的監控.
然後我們看看CharBlockPool是怎樣被調用的, 在TermsHashPerField的add()函數中:
1: if (p == null) {
2: final int textLen1 = 1+tokenTextLen;
3: if (textLen1 + charPool.charUpto > DocumentsWriter.CHAR_BLOCK_SIZE) {
4: if (textLen1 > DocumentsWriter.CHAR_BLOCK_SIZE) {
5: if (docState.maxTermPrefix == null)
6: docState.maxTermPrefix = new String(tokenText, 0, 30);
7: consumer.skippingLongTerm();
8: return;
9: }
10: charPool.nextBuffer();
11: }
這段代碼首先計算出當前單詞的長度(textLen1), 然後看看當前緩存的"層"是否夠住了, 如果不夠, 就調用charPool.nextBuffer()加蓋樓房.
1: final char[] text = charPool.buffer;
2: final int textUpto = charPool.charUpto;
3: p.textStart = textUpto + charPool.charOffset;
4: charPool.charUpto += textLen1;
5: System.arraycopy(tokenText, 0, text, textUpto, tokenTextLen);
6: text[textUpto+tokenTextLen] = 0xffff;
這段代碼就是怎麼使用緩存的了. 首先拿到charBlockPool的buffer, 然後修改p.textStart, 這個成員變量的意思是這個posting(也就是這個單詞了)是從charPool中什麼位置起始的. 然後把單詞結束後的一位設置為0xffff.
可以看出, charBlockPool的用法還是很樸素的, 這可能也說明了, 越樸素, 越靈活吧, 或許lucene的開發者是這樣考慮的, 呵呵.
2. IntBlockPool, ByteBlockPool
這個類非常類似於charBlockPool, 在lucene的緩存中, 對每一種類型都設置了一種內存池, 對於token來說, text使用charPool, 位置采用一個一個的byte來構成, 而表示位置byte的起始序列的值采用IntPool來保存, 起始我覺得IntBlockPool並不是那樣的有必要, 我感覺保存在postingHash中也是可以的, 具體我慢慢再理解一下, 也歡迎大家討論.
IntBlockPool與ByteBlockPool結合非常緊密, 從代碼中就可以看得出來:
1: intUptos = intPool.buffer;
2: intUptoStart = intPool.intUpto;
3: intPool.intUpto += streamCount;
4:
5: p.intStart = intUptoStart + intPool.intOffset;
6:
7: for(int i=0;i<streamCount;i++) {
8: final int upto = bytePool.newSlice(ByteBlockPool.FIRST_LEVEL_SIZE);
9: intUptos[intUptoStart+i] = upto + bytePool.byteOffset;
10: }
11: p.byteStart = intUptos[intUptoStart];
12:
13: consumer.newTerm(p);
14:
15: else {
16: intUptos = intPool.buffers[p.intStart >> DocumentsWriter.INT_BLOCK_SHIFT];
17: intUptoStart = p.intStart & DocumentsWriter.INT_BLOCK_MASK;
18: consumer.addTerm(p);
19: }
streamCount就是表示使用幾個int表示偏移指針. intUptos就是一個int[], 保留當前的"層", 下面研究一下這個for循環:
1: for(int i=0;i<streamCount;i++) {
2: final int upto = bytePool.newSlice(ByteBlockPool.FIRST_LEVEL_SIZE);
3: intUptos[intUptoStart+i] = upto + bytePool.byteOffset;
4: }
newSlice就是為bytePool分配一個int大小的空間, FIRST_LEVEL_SIZE為5個byte, 如果按這個程序運行, intUptos[intUptoStart]的值與bytePool的byteUpto並不一致, 要小了5. 這樣說吧. 我來畫一個例子
bytePool
....../xxxxxx/…… : in memory
^(A),xxxxxx為一段數據
intPool
……A, 指向的應該是這段數據的開始位置, 所以int的Upto要比byte的Upto小了一個size的大小, 這個size就是bytePool對應的這段數據的長度.
接下來的問題是: 當對內存進行數據的寫入的時候, 分配的內存不夠怎麼辦呢, 之前已經說了, bytePool是存儲單詞出現的位置的, 但是在分配內存的時候, 卻不知道單詞將會出現多少次, 所以必然會出現擴展內存的情況, 下面舉一個例子:
AA. . .B . . . C . . .這樣的一個buffer, 假設現在要在B後面寫入4位, 但是B卻只有3位的剩余空間了, 怎麼辦呢, 首先我們分配一個更大的片(slice), 具體的slice的大小可以參見levelSizeArray[], 然後把B的後三位復制到新的slice中, 並且把B的後三位改成一個offset, 指向新的slice, 可能看起來是這樣的:
AA. . .B offset C . . . (new B): B B B B, 這段程序請見TermsHashPerField中的writeByte.
不過說起來, 這段Pool相關的代碼寫得也確實惡心了一點, 很容易讓人糊塗, 而且注釋也是很金貴的.
另外在Lucene中還廣泛應用的就是RawPostingList[]這樣類似於數組的hash形式, 之前一直覺得很奇怪, 為什麼作者不能用泛型的hashMap呢, 想了想, 覺得第一個這樣做會造成一些不必要的時間開銷, 另外要是需要對這個hash排序就不是那樣的友好了. 這種hash形式確實很不錯哦.
