lsbwahaha

1. sudo -s
2. cd /System/Library/Frameworks/JavaVM.framework/Home
3. ln -s /Library/Java/JavaVirtualMachines/1.6.0_35-b10-428.jdk/Contents/Home/docs.jar
4. ln -s  /Library/Java/JavaVirtualMachines/1.6.0_35-b10-428.jdk/Contents/Home/src.jar
5. 最后跟windows類似，在eclipse中用command + click點擊查看一個類的源碼。然后選“add source"，選中上面的 src.jar 文件即可

地理位置索引支持是MongoDB的一大亮點，這也是全球最流行的LBS服務foursquare 選擇MongoDB的原因之一。我們知道，通常的數據庫索引結構是B+ Tree，如何將地理位置轉化為可建立B+Tree的形式，下文將為你描述。

首先假設我們將需要索引的整個地圖分成16×16的方格，如下圖（左下角為坐標0,0 右上角為坐標16,16）：

單純的［x，y］的數據是無法建立索引的，所以MongoDB在建立索引的時候，會根據相應字段的坐標計算一個可以用來做索引的hash值，這個值叫做geohash，下面我們以地圖上坐標為［4，6］的點（圖中紅叉位置）為例。

我們第一步將整個地圖分成等大小的四塊，如下圖：

劃分成四塊后我們可以定義這四塊的值，如下（左下為00，左上為01，右下為10，右上為11）：

01	11
00	10

這樣［4，6］點的geohash值目前為 00

然后再將四個小塊每一塊進行切割，如下：

這時［4，6］點位于右上區域，右上的值為11，這樣［4，6］點的geohash值變為：0011

繼續往下做兩次切分：

最終得到［4，6］點的geohash值為：00110100

這樣我們用這個值來做索引，則地圖上點相近的點就可以轉化成有相同前綴的geohash值了。

我們可以看到，這個geohash值的精確度是與劃分地圖的次數成正比的，上例對地圖劃分了四次。而MongoDB默認是進行26次劃分，這個值在建立索引時是可控的。具體建立二維地理位置索引的命令如下：

db.map.ensureIndex({point : "2d"}, {min : 0, max : 16, bits : 4})

其中的bits參數就是劃分幾次，默認為26次。

單例創建模式是一個通用的編程習語。和多線程一起使用時，必需使用某種類型的同步。在努力創建更有效的代碼時，Java 程序員們創建了雙重檢查鎖定習語，將其和單例創建模式一起使用，從而限制同步代碼量。然而，由于一些不太常見的 Java 內存模型細節的原因，并不能保證這個雙重檢查鎖定習語有效。它偶爾會失敗，而不是總失敗。此外，它失敗的原因并不明顯，還包含 Java 內存模型的一些隱秘細節。這些事實將導致代碼失敗，原因是雙重檢查鎖定難于跟蹤。在本文余下的部分里，我們將詳細介紹雙重檢查鎖定習語，從而理解它在何處失效。

單例創建習語

要理解雙重檢查鎖定習語是從哪里起源的，就必須理解通用單例創建習語，如清單 1 中的闡釋：

                        import java.util.*;
            class Singleton
            {
            private static Singleton instance;
            private Vector v;
            private boolean inUse;
            private Singleton()
            {
            v = new Vector();
            v.addElement(new Object());
            inUse = true;
            }
            public static Singleton getInstance()
            {
            if (instance == null)          //1
            instance = new Singleton();  //2
            return instance;               //3
            }
            }
            

此類的設計確保只創建一個 Singleton 對象。構造函數被聲明為 private，getInstance() 方法只創建一個對象。這個實現適合于單線程程序。然而，當引入多線程時，就必須通過同步來保護 getInstance() 方法。如果不保護 getInstance() 方法，則可能返回 Singleton 對象的兩個不同的實例。假設兩個線程并發調用 getInstance() 方法并且按以下順序執行調用：

1. 線程 1 調用 getInstance() 方法并決定 instance 在 //1 處為 null。
   
   
2. 線程 1 進入 if 代碼塊，但在執行 //2 處的代碼行時被線程 2 預占。
   
   
3. 線程 2 調用 getInstance() 方法并在 //1 處決定 instance 為 null。
   
   
4. 線程 2 進入 if 代碼塊并創建一個新的 Singleton 對象并在 //2 處將變量 instance 分配給這個新對象。
   
   
5. 線程 2 在 //3 處返回 Singleton 對象引用。
   
   
6. 線程 2 被線程 1 預占。
   
   
7. 線程 1 在它停止的地方啟動，并執行 //2 代碼行，這導致創建另一個 Singleton 對象。
   
   
8. 線程 1 在 //3 處返回這個對象。

結果是 getInstance() 方法創建了兩個 Singleton 對象，而它本該只創建一個對象。通過同步 getInstance() 方法從而在同一時間只允許一個線程執行代碼，這個問題得以改正，如清單 2 所示：

                        public static synchronized Singleton getInstance()
            {
            if (instance == null)          //1
            instance = new Singleton();  //2
            return instance;               //3
            }
            

清單 2 中的代碼針對多線程訪問 getInstance() 方法運行得很好。然而，當分析這段代碼時，您會意識到只有在第一次調用方法時才需要同步。由于只有第一次調用執行了 //2 處的代碼，而只有此行代碼需要同步，因此就無需對后續調用使用同步。所有其他調用用于決定 instance 是非 null 的，并將其返回。多線程能夠安全并發地執行除第一次調用外的所有調用。盡管如此，由于該方法是 synchronized 的，需要為該方法的每一次調用付出同步的代價，即使只有第一次調用需要同步。

為使此方法更為有效，一個被稱為雙重檢查鎖定的習語就應運而生了。這個想法是為了避免對除第一次調用外的所有調用都實行同步的昂貴代價。同步的代價在不同的 JVM 間是不同的。在早期，代價相當高。隨著更高級的 JVM 的出現，同步的代價降低了，但出入 synchronized 方法或塊仍然有性能損失。不考慮 JVM 技術的進步，程序員們絕不想不必要地浪費處理時間。

因為只有清單 2 中的 //2 行需要同步，我們可以只將其包裝到一個同步塊中，如清單 3 所示：

                        public static Singleton getInstance()
            {
            if (instance == null)
            {
            synchronized(Singleton.class) {
            instance = new Singleton();
            }
            }
            return instance;
            }
            

清單 3 中的代碼展示了用多線程加以說明的和清單 1 相同的問題。當 instance 為 null 時，兩個線程可以并發地進入 if 語句內部。然后，一個線程進入 synchronized 塊來初始化 instance，而另一個線程則被阻斷。當第一個線程退出 synchronized 塊時，等待著的線程進入并創建另一個 Singleton 對象。注意：當第二個線程進入 synchronized 塊時，它并沒有檢查 instance 是否非 null。

雙重檢查鎖定

為處理清單 3 中的問題，我們需要對 instance 進行第二次檢查。這就是“雙重檢查鎖定”名稱的由來。將雙重檢查鎖定習語應用到清單 3 的結果就是清單 4 。

                        public static Singleton getInstance()
            {
            if (instance == null)
            {
            synchronized(Singleton.class) {  //1
            if (instance == null)          //2
            instance = new Singleton();  //3
            }
            }
            return instance;
            }
            

雙重檢查鎖定背后的理論是：在 //2 處的第二次檢查使（如清單 3 中那樣）創建兩個不同的 Singleton 對象成為不可能。假設有下列事件序列：

1. 線程 1 進入 getInstance() 方法。
   
   
2. 由于 instance 為 null，線程 1 在 //1 處進入 synchronized 塊。
   
   
3. 線程 1 被線程 2 預占。
   
   
4. 線程 2 進入 getInstance() 方法。
   
   
5. 由于 instance 仍舊為 null，線程 2 試圖獲取 //1 處的鎖。然而，由于線程 1 持有該鎖，線程 2 在 //1 處阻塞。
   
   
6. 線程 2 被線程 1 預占。
   
   
7. 線程 1 執行，由于在 //2 處實例仍舊為 null，線程 1 還創建一個 Singleton 對象并將其引用賦值給 instance。
   
   
8. 線程 1 退出 synchronized 塊并從 getInstance() 方法返回實例。
   
   
9. 線程 1 被線程 2 預占。
   
   
10. 線程 2 獲取 //1 處的鎖并檢查 instance 是否為 null。
    
    
11. 由于 instance 是非 null 的，并沒有創建第二個 Singleton 對象，由線程 1 創建的對象被返回。

雙重檢查鎖定背后的理論是完美的。不幸地是，現實完全不同。雙重檢查鎖定的問題是：并不能保證它會在單處理器或多處理器計算機上順利運行。

雙重檢查鎖定失敗的問題并不歸咎于 JVM 中的實現 bug，而是歸咎于 Java 平臺內存模型。內存模型允許所謂的“無序寫入”，這也是這些習語失敗的一個主要原因。

無序寫入

為解釋該問題，需要重新考察上述清單 4 中的 //3 行。此行代碼創建了一個 Singleton 對象并初始化變量 instance 來引用此對象。這行代碼的問題是：在 Singleton 構造函數體執行之前，變量 instance 可能成為非 null 的。

什么？這一說法可能讓您始料未及，但事實確實如此。在解釋這個現象如何發生前，請先暫時接受這一事實，我們先來考察一下雙重檢查鎖定是如何被破壞的。假設清單 4 中代碼執行以下事件序列：

1. 線程 1 進入 getInstance() 方法。
   
   
2. 由于 instance 為 null，線程 1 在 //1 處進入 synchronized 塊。
   
   
3. 線程 1 前進到 //3 處，但在構造函數執行之前，使實例成為非 null。
   
   
4. 線程 1 被線程 2 預占。
   
   
5. 線程 2 檢查實例是否為 null。因為實例不為 null，線程 2 將 instance 引用返回給一個構造完整但部分初始化了的 Singleton 對象。
   
   
6. 線程 2 被線程 1 預占。
   
   
7. 線程 1 通過運行 Singleton 對象的構造函數并將引用返回給它，來完成對該對象的初始化。

此事件序列發生在線程 2 返回一個尚未執行構造函數的對象的時候。

為展示此事件的發生情況，假設為代碼行 instance =new Singleton(); 執行了下列偽代碼： instance =new Singleton();

mem = allocate();             //Allocate memory for Singleton object.
            instance = mem;               //Note that instance is now non-null, but
            //has not been initialized.
            ctorSingleton(instance);      //Invoke constructor for Singleton passing
            //instance.
            

這段偽代碼不僅是可能的，而且是一些 JIT 編譯器上真實發生的。執行的順序是顛倒的，但鑒于當前的內存模型，這也是允許發生的。JIT 編譯器的這一行為使雙重檢查鎖定的問題只不過是一次學術實踐而已。

為說明這一情況，假設有清單 5 中的代碼。它包含一個剝離版的 getInstance() 方法。我已經刪除了“雙重檢查性”以簡化我們對生成的匯編代碼（清單 6）的回顧。我們只關心 JIT 編譯器如何編譯 instance=new Singleton(); 代碼。此外，我提供了一個簡單的構造函數來明確說明匯編代碼中該構造函數的運行情況。

                        class Singleton
            {
            private static Singleton instance;
            private boolean inUse;
            private int val;
            private Singleton()
            {
            inUse = true;
            val = 5;
            }
            public static Singleton getInstance()
            {
            if (instance == null)
            instance = new Singleton();
            return instance;
            }
            }
            

清單 6 包含由 Sun JDK 1.2.1 JIT 編譯器為清單 5 中的 getInstance() 方法體生成的匯編代碼。

                        ;asm code generated for getInstance
            054D20B0   mov         eax,[049388C8]      ;load instance ref
            054D20B5   test        eax,eax             ;test for null
            054D20B7   jne         054D20D7
            054D20B9   mov         eax,14C0988h
            054D20BE   call        503EF8F0            ;allocate memory
            054D20C3   mov         [049388C8],eax      ;store pointer in
            ;instance ref. instance
            ;non-null and ctor
            ;has not run
            054D20C8   mov         ecx,dword ptr [eax]
            054D20CA   mov         dword ptr [ecx],1   ;inline ctor - inUse=true;
            054D20D0   mov         dword ptr [ecx+4],5 ;inline ctor - val=5;
            054D20D7   mov         ebx,dword ptr ds:[49388C8h]
            054D20DD   jmp         054D20B0
            

注: 為引用下列說明中的匯編代碼行，我將引用指令地址的最后兩個值，因為它們都以 054D20 開頭。例如，B5 代表 test eax,eax。

匯編代碼是通過運行一個在無限循環中調用 getInstance() 方法的測試程序來生成的。程序運行時，請運行 Microsoft Visual C++ 調試器并將其附到表示測試程序的 Java 進程中。然后，中斷執行并找到表示該無限循環的匯編代碼。

B0 和 B5 處的前兩行匯編代碼將 instance 引用從內存位置 049388C8 加載至 eax 中，并進行 null 檢查。這跟清單 5 中的 getInstance() 方法的第一行代碼相對應。第一次調用此方法時，instance 為 null，代碼執行到 B9。BE 處的代碼為 Singleton 對象從堆中分配內存，并將一個指向該塊內存的指針存儲到 eax 中。下一行代碼，C3，獲取 eax 中的指針并將其存儲回內存位置為 049388C8 的實例引用。結果是，instance 現在為非 null 并引用一個有效的 Singleton 對象。然而，此對象的構造函數尚未運行，這恰是破壞雙重檢查鎖定的情況。然后，在 C8 行處，instance 指針被解除引用并存儲到 ecx。CA 和 D0 行表示內聯的構造函數，該構造函數將值 true 和 5 存儲到 Singleton 對象。如果此代碼在執行 C3 行后且在完成該構造函數前被另一個線程中斷，則雙重檢查鎖定就會失敗。

不是所有的 JIT 編譯器都生成如上代碼。一些生成了代碼，從而只在構造函數執行后使 instance 成為非 null。針對 Java 技術的 IBM SDK 1.3 版和 Sun JDK 1.3 都生成這樣的代碼。然而，這并不意味著應該在這些實例中使用雙重檢查鎖定。該習語失敗還有一些其他原因。此外，您并不總能知道代碼會在哪些 JVM 上運行，而 JIT 編譯器總是會發生變化，從而生成破壞此習語的代碼。

雙重檢查鎖定：獲取兩個

考慮到當前的雙重檢查鎖定不起作用，我加入了另一個版本的代碼，如清單 7 所示，從而防止您剛才看到的無序寫入問題。

                        public static Singleton getInstance()
            {
            if (instance == null)
            {
            synchronized(Singleton.class) {      //1
            Singleton inst = instance;         //2
            if (inst == null)
            {
            synchronized(Singleton.class) {  //3
            inst = new Singleton();        //4
            }
            instance = inst;                 //5
            }
            }
            }
            return instance;
            }
            

看著清單 7 中的代碼，您應該意識到事情變得有點荒謬。請記住，創建雙重檢查鎖定是為了避免對簡單的三行 getInstance() 方法實現同步。清單 7 中的代碼變得難于控制。另外，該代碼沒有解決問題。仔細檢查可獲悉原因。

此代碼試圖避免無序寫入問題。它試圖通過引入局部變量 inst 和第二個 synchronized 塊來解決這一問題。該理論實現如下：

1. 線程 1 進入 getInstance() 方法。
   
   
2. 由于 instance 為 null，線程 1 在 //1 處進入第一個 synchronized 塊。
   
   
3. 局部變量 inst 獲取 instance 的值，該值在 //2 處為 null。
   
   
4. 由于 inst 為 null，線程 1 在 //3 處進入第二個 synchronized 塊。
   
   
5. 線程 1 然后開始執行 //4 處的代碼，同時使 inst 為非 null，但在 Singleton 的構造函數執行前。（這就是我們剛才看到的無序寫入問題。）
   
   
6. 線程 1 被線程 2 預占。
   
   
7. 線程 2 進入 getInstance() 方法。
   
   
8. 由于 instance 為 null，線程 2 試圖在 //1 處進入第一個 synchronized 塊。由于線程 1 目前持有此鎖，線程 2 被阻斷。
   
   
9. 線程 1 然后完成 //4 處的執行。
   
   
10. 線程 1 然后將一個構造完整的 Singleton 對象在 //5 處賦值給變量 instance，并退出這兩個 synchronized 塊。
    
    
11. 線程 1 返回 instance。
    
    
12. 然后執行線程 2 并在 //2 處將 instance 賦值給 inst。
    
    
13. 線程 2 發現 instance 為非 null，將其返回。

這里的關鍵行是 //5。此行應該確保 instance 只為 null 或引用一個構造完整的 Singleton 對象。該問題發生在理論和實際彼此背道而馳的情況下。

由于當前內存模型的定義，清單 7 中的代碼無效。Java 語言規范（Java Language Specification，JLS）要求不能將 synchronized 塊中的代碼移出來。但是，并沒有說不能將 synchronized 塊外面的代碼移入 synchronized 塊中。

JIT 編譯器會在這里看到一個優化的機會。此優化會刪除 //4 和 //5 處的代碼，組合并且生成清單 8 中所示的代碼。

                        public static Singleton getInstance()
            {
            if (instance == null)
            {
            synchronized(Singleton.class) {      //1
            Singleton inst = instance;         //2
            if (inst == null)
            {
            synchronized(Singleton.class) {  //3
            //inst = new Singleton();      //4
            instance = new Singleton();
            }
            //instance = inst;               //5
            }
            }
            }
            return instance;
            }
            

如果進行此項優化，您將同樣遇到我們之前討論過的無序寫入問題。

用 volatile 聲明每一個變量怎么樣？

另一個想法是針對變量 inst 以及 instance 使用關鍵字 volatile。根據 JLS（參見 參考資料），聲明成 volatile 的變量被認為是順序一致的，即，不是重新排序的。但是試圖使用 volatile 來修正雙重檢查鎖定的問題，會產生以下兩個問題：

• 這里的問題不是有關順序一致性的，而是代碼被移動了，不是重新排序。
  
  
• 即使考慮了順序一致性，大多數的 JVM 也沒有正確地實現 volatile。

第二點值得展開討論。假設有清單 9 中的代碼：

                        class test
            {
            private volatile boolean stop = false;
            private volatile int num = 0;
            public void foo()
            {
            num = 100;    //This can happen second
            stop = true;  //This can happen first
            //...
            }
            public void bar()
            {
            if (stop)
            num += num;  //num can == 0!
            }
            //...
            }
            

根據 JLS，由于 stop 和 num 被聲明為 volatile，它們應該順序一致。這意味著如果 stop 曾經是 true，num 一定曾被設置成 100。盡管如此，因為許多 JVM 沒有實現 volatile 的順序一致性功能，您就不能依賴此行為。因此，如果線程 1 調用 foo 并且線程 2 并發地調用 bar，則線程 1 可能在 num 被設置成為 100 之前將 stop 設置成 true。這將導致線程見到 stop 是 true，而 num 仍被設置成 0。使用 volatile 和 64 位變量的原子數還有另外一些問題，但這已超出了本文的討論范圍。有關此主題的更多信息，請參閱 參考資料。

解決方案

底線就是：無論以何種形式，都不應使用雙重檢查鎖定，因為您不能保證它在任何 JVM 實現上都能順利運行。JSR-133 是有關內存模型尋址問題的，盡管如此，新的內存模型也不會支持雙重檢查鎖定。因此，您有兩種選擇：

• 接受如清單 2 中所示的 getInstance() 方法的同步。
  
  
• 放棄同步，而使用一個 static 字段。

選擇項 2 如清單 10 中所示

                        class Singleton
            {
            private Vector v;
            private boolean inUse;
            private static Singleton instance = new Singleton();
            private Singleton()
            {
            v = new Vector();
            inUse = true;
            //...
            }
            public static Singleton getInstance()
            {
            return instance;
            }
            }
            

清單 10 的代碼沒有使用同步，并且確保調用 static getInstance() 方法時才創建 Singleton。如果您的目標是消除同步，則這將是一個很好的選擇。

String 不是不變的

鑒于無序寫入和引用在構造函數執行前變成非 null 的問題，您可能會考慮 String 類。假設有下列代碼：

private String str;
            //...
            str = new String("hello");
            

String 類應該是不變的。盡管如此，鑒于我們之前討論的無序寫入問題，那會在這里導致問題嗎？答案是肯定的。考慮兩個線程訪問 String str。一個線程能看見 str 引用一個 String 對象，在該對象中構造函數尚未運行。事實上，清單 11 包含展示這種情況發生的代碼。注意，這個代碼僅在我測試用的舊版 JVM 上會失敗。IBM 1.3 和 Sun 1.3 JVM 都會如期生成不變的 String。

                        class StringCreator extends Thread
            {
            MutableString ms;
            public StringCreator(MutableString muts)
            {
            ms = muts;
            }
            public void run()
            {
            while(true)
            ms.str = new String("hello");          //1
            }
            }
            class StringReader extends Thread
            {
            MutableString ms;
            public StringReader(MutableString muts)
            {
            ms = muts;
            }
            public void run()
            {
            while(true)
            {
            if (!(ms.str.equals("hello")))         //2
            {
            System.out.println("String is not immutable!");
            break;
            }
            }
            }
            }
            class MutableString
            {
            public String str;                         //3
            public static void main(String args[])
            {
            MutableString ms = new MutableString();  //4
            new StringCreator(ms).start();           //5
            new StringReader(ms).start();            //6
            }
            }
            

此代碼在 //4 處創建一個 MutableString 類，它包含了一個 String 引用，此引用由 //3 處的兩個線程共享。在行 //5 和 //6 處，在兩個分開的線程上創建了兩個對象 StringCreator 和 StringReader。傳入一個 MutableString 對象的引用。StringCreator 類進入到一個無限循環中并且使用值“hello”在 //1 處創建 String 對象。StringReader 也進入到一個無限循環中，并且在 //2 處檢查當前的 String 對象的值是不是 “hello”。如果不行，StringReader 線程打印出一條消息并停止。如果 String 類是不變的，則從此程序應當看不到任何輸出。如果發生了無序寫入問題，則使 StringReader 看到 str 引用的惟一方法絕不是值為“hello”的 String 對象。

在舊版的 JVM 如 Sun JDK 1.2.1 上運行此代碼會導致無序寫入問題。并因此導致一個非不變的 String。

結束語

為避免單例中代價高昂的同步，程序員非常聰明地發明了雙重檢查鎖定習語。不幸的是，鑒于當前的內存模型的原因，該習語尚未得到廣泛使用，就明顯成為了一種不安全的編程結構。重定義脆弱的內存模型這一領域的工作正在進行中。盡管如此，即使是在新提議的內存模型中，雙重檢查鎖定也是無效的。對此問題最佳的解決方案是接受同步或者使用一個 static field。