View Javadoc

1   /*
2    *  Licensed to the Apache Software Foundation (ASF) under one
3    *  or more contributor license agreements.  See the NOTICE file
4    *  distributed with this work for additional information
5    *  regarding copyright ownership.  The ASF licenses this file
6    *  to you under the Apache License, Version 2.0 (the
7    *  "License"); you may not use this file except in compliance
8    *  with the License.  You may obtain a copy of the License at
9    *
10   *    http://www.apache.org/licenses/LICENSE-2.0
11   *
12   *  Unless required by applicable law or agreed to in writing,
13   *  software distributed under the License is distributed on an
14   *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   *  KIND, either express or implied.  See the License for the
16   *  specific language governing permissions and limitations
17   *  under the License.
18   *
19   */
20  package org.apache.directory.mavibot.btree.memory;
21  
22  
23  import static org.junit.Assert.assertEquals;
24  import static org.junit.Assert.assertFalse;
25  import static org.junit.Assert.assertTrue;
26  
27  import java.io.File;
28  import java.io.IOException;
29  import java.util.Random;
30  import java.util.Set;
31  
32  import org.apache.directory.mavibot.btree.Tuple;
33  import org.apache.directory.mavibot.btree.TupleCursor;
34  import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
35  import org.apache.directory.mavibot.btree.serializer.IntSerializer;
36  import org.apache.directory.mavibot.btree.serializer.LongSerializer;
37  import org.apache.directory.mavibot.btree.serializer.StringSerializer;
38  import org.junit.Rule;
39  import org.junit.Test;
40  import org.junit.rules.TemporaryFolder;
41  
42  
43  /**
44   * A unit test class for BTree flush() operation
45   * 
46   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
47   */
48  public class BTreeFlushTest
49  {
50      @Rule
51      public TemporaryFolder tempFolder = new TemporaryFolder();
52  
53      // Some values to inject in a btree
54      private static int[] sortedValues = new int[]
55          {
56              0, 1, 2, 4, 5, 6, 8, 9, 11, 12,
57              13, 14, 16, 19, 21, 22, 23, 25, 26, 28,
58              30, 31, 32, 34, 36, 37, 38, 39, 41, 42,
59              44, 45, 47, 50, 52, 53, 54, 55, 56, 58,
60              59, 60, 63, 64, 67, 68, 70, 72, 73, 74,
61              76, 77, 79, 80, 81, 82, 85, 88, 89, 90,
62              92, 93, 95, 97, 98, 100, 101, 102, 103, 104,
63              105, 106, 107, 109, 110, 111, 112, 117, 118, 120,
64              121, 128, 129, 130, 131, 132, 135, 136, 137, 138,
65              139, 140, 141, 142, 143, 146, 147, 148, 149, 150,
66              152, 154, 156, 160, 161, 162, 163, 165, 167, 168,
67              169, 171, 173, 174, 175, 176, 177, 178, 179, 180,
68              181, 182, 183, 189, 190, 193, 194, 195, 199, 200,
69              202, 203, 205, 206, 207, 208, 209, 210, 212, 215,
70              216, 217, 219, 220, 222, 223, 224, 225, 226, 227,
71              228, 230, 231, 235, 236, 238, 239, 241, 242, 243,
72              245, 246, 247, 249, 250, 251, 252, 254, 256, 257,
73              258, 259, 261, 262, 263, 264, 266, 268, 272, 273,
74              274, 276, 277, 278, 279, 282, 283, 286, 289, 290,
75              292, 293, 294, 296, 298, 299, 300, 301, 303, 305,
76              308, 310, 316, 317, 318, 319, 322, 323, 324, 326,
77              327, 329, 331, 333, 334, 335, 336, 337, 338, 339,
78              340, 341, 346, 347, 348, 349, 350, 351, 352, 353,
79              355, 356, 357, 358, 359, 361, 365, 366, 373, 374,
80              375, 379, 380, 381, 382, 384, 385, 387, 388, 389,
81              390, 392, 393, 395, 396, 397, 398, 399, 400, 401,
82              404, 405, 406, 407, 410, 411, 412, 416, 417, 418,
83              420, 421, 422, 424, 426, 427, 428, 430, 431, 432,
84              433, 436, 439, 441, 443, 444, 445, 446, 447, 448,
85              449, 450, 451, 452, 453, 454, 455, 456, 458, 459,
86              464, 466, 469, 470, 471, 472, 475, 477, 478, 482,
87              483, 484, 485, 486, 488, 490, 491, 492, 493, 495,
88              496, 497, 500, 502, 503, 504, 505, 506, 507, 509,
89              510, 514, 516, 518, 520, 521, 523, 524, 526, 527,
90              528, 529, 530, 532, 533, 535, 538, 539, 540, 542,
91              543, 544, 546, 547, 549, 550, 551, 553, 554, 558,
92              559, 561, 563, 564, 566, 567, 568, 569, 570, 571,
93              572, 576, 577, 578, 580, 582, 583, 586, 588, 589,
94              590, 592, 593, 596, 597, 598, 599, 600, 601, 604,
95              605, 606, 607, 609, 610, 613, 615, 617, 618, 619,
96              620, 621, 626, 627, 628, 631, 632, 633, 635, 636,
97              637, 638, 639, 640, 641, 643, 645, 647, 648, 649,
98              650, 651, 652, 653, 655, 656, 658, 659, 660, 662,
99              666, 669, 673, 674, 675, 676, 677, 678, 680, 681,
100             682, 683, 685, 686, 687, 688, 689, 690, 691, 692,
101             693, 694, 696, 698, 699, 700, 701, 705, 708, 709,
102             711, 713, 714, 715, 719, 720, 723, 725, 726, 727,
103             728, 731, 732, 733, 734, 735, 736, 739, 740, 743,
104             744, 745, 746, 747, 749, 750, 752, 753, 762, 763,
105             765, 766, 768, 770, 772, 773, 774, 776, 777, 779,
106             782, 784, 785, 788, 790, 791, 793, 794, 795, 798,
107             799, 800, 801, 803, 804, 805, 808, 810, 812, 813,
108             814, 816, 818, 821, 822, 823, 824, 827, 828, 829,
109             831, 832, 833, 834, 835, 837, 838, 839, 840, 843,
110             846, 847, 849, 852, 853, 854, 856, 857, 859, 860,
111             863, 864, 865, 866, 867, 868, 869, 872, 873, 877,
112             880, 881, 882, 883, 887, 888, 889, 890, 891, 894,
113             895, 897, 898, 899, 902, 904, 905, 907, 908, 910,
114             911, 912, 915, 916, 917, 918, 919, 923, 925, 926,
115             927, 928, 929, 930, 932, 935, 936, 937, 938, 939,
116             944, 945, 947, 952, 953, 954, 955, 956, 957, 958,
117             960, 967, 970, 971, 972, 974, 975, 976, 978, 979,
118             980, 981, 983, 984, 985, 987, 988, 989, 991, 995
119     };
120 
121 
122     private String create100KElementsFile() throws IOException
123     {
124         Random random = new Random( System.nanoTime() );
125 
126         int nbError = 0;
127 
128         long l1 = System.currentTimeMillis();
129         int n = 0;
130         long delta = l1;
131         int nbElems = 100000;
132 
133         BTree<Long, String> btree = new BTree<Long, String>( "test", new LongSerializer(), new StringSerializer() );
134         btree.setPageSize( 32 );
135 
136         for ( int i = 0; i < nbElems; i++ )
137         {
138             Long key = ( long ) random.nextLong();
139             String value = Long.toString( key );
140 
141             try
142             {
143                 btree.insert( key, value );
144             }
145             catch ( Exception e )
146             {
147                 e.printStackTrace();
148                 System.out.println( btree );
149                 System.out.println( "Error while adding " + value );
150                 nbError++;
151                 btree.close();
152 
153                 return null;
154             }
155 
156             if ( i % 10000 == 0 )
157             {
158                 if ( n > 0 )
159                 {
160                     long t0 = System.currentTimeMillis();
161                     System.out.println( "Written " + i + " elements in : " + ( t0 - delta ) + "ms" );
162                     delta = t0;
163                 }
164 
165                 n++;
166             }
167         }
168 
169         long l2 = System.currentTimeMillis();
170 
171         System.out.println( "Delta : " + ( l2 - l1 ) + ", nbError = " + nbError
172             + ", Nb insertion per second : " + ( ( nbElems ) / ( l2 - l1 ) ) * 1000 );
173 
174         // Now, flush the btree
175 
176         File tempFile = tempFolder.newFile( "mavibot.tmp" );
177 
178         long t0 = System.currentTimeMillis();
179 
180         btree.flush( tempFile );
181 
182         long t1 = System.currentTimeMillis();
183 
184         System.out.println( "Time to flush 100 000 elements : " + ( t1 - t0 ) + "ms" );
185         btree.close();
186 
187         return tempFile.getCanonicalPath();
188     }
189 
190 
191     /**
192      * Checks the created BTree contains the expected values
193      */
194     private boolean checkTreeLong( Set<Long> expected, BTree<Long, String> btree ) throws IOException
195     {
196         // We loop on all the expected value to see if they have correctly been inserted
197         // into the btree
198         for ( Long key : expected )
199         {
200             try
201             {
202                 btree.get( key );
203             }
204             catch ( KeyNotFoundException knfe )
205             {
206                 return false;
207             }
208         }
209 
210         return true;
211     }
212 
213 
214     /**
215      * Test the browse method going backward
216      * @throws Exception
217      */
218     @Test
219     public void testFlushBTree() throws Exception
220     {
221         // Create a BTree with pages containing 8 elements
222         String path = tempFolder.getRoot().getCanonicalPath();
223 
224         BTree<Integer, String> btree = new BTree<Integer, String>( "test", path, new IntSerializer(),
225             new StringSerializer() );
226         btree.setPageSize( 8 );
227 
228         File journal = btree.getJournal();
229         File data = btree.getFile();
230 
231         try
232         {
233             // Inject the values
234             for ( int value : sortedValues )
235             {
236                 String strValue = "V" + value;
237 
238                 btree.insert( value, strValue );
239             }
240 
241             // The journal must be full
242             assertTrue( journal.length() > 0 );
243 
244             // Now, flush the btree
245             btree.flush();
246 
247             // The journal must be empty
248             assertEquals( 0, journal.length() );
249 
250             // Load the data into a new tree
251             BTree<Integer, String> btreeLoaded = new BTree<Integer, String>( "test", path, new IntSerializer(),
252                 new StringSerializer() );
253             btree.setPageSize( 8 );
254 
255             TupleCursor<Integer, String> cursor1 = btree.browse();
256             TupleCursor<Integer, String> cursor2 = btree.browse();
257 
258             while ( cursor1.hasNext() )
259             {
260                 assertTrue( cursor2.hasNext() );
261 
262                 Tuple<Integer, String> tuple1 = cursor1.next();
263                 Tuple<Integer, String> tuple2 = cursor2.next();
264 
265                 assertEquals( tuple1.getKey(), tuple2.getKey() );
266                 assertEquals( tuple1.getValue(), tuple2.getValue() );
267             }
268 
269             assertFalse( cursor2.hasNext() );
270 
271             btree.close();
272             btreeLoaded.close();
273         }
274         finally
275         {
276             data.delete();
277             journal.delete();
278         }
279     }
280 
281 
282     /**
283      * Test the insertion of 5 million elements in a BTree
284      * @throws Exception
285      */
286     @Test
287     public void testLoadBTreeFromFile() throws Exception
288     {
289         String data100K = create100KElementsFile();
290         File dataFile = new File( data100K );
291         BTree<Long, String> btree = new BTree<Long, String>(
292             "test",
293             dataFile.getParent(),
294             new LongSerializer(),
295             new StringSerializer() );
296         btree.setPageSize( 32 );
297         btree.close();
298     }
299 }