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.fail;
25  
26  import java.io.IOException;
27  import java.util.Random;
28  import java.util.concurrent.CountDownLatch;
29  
30  import org.apache.directory.mavibot.btree.Tuple;
31  import org.apache.directory.mavibot.btree.TupleCursor;
32  import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
33  import org.apache.directory.mavibot.btree.serializer.LongSerializer;
34  import org.apache.directory.mavibot.btree.serializer.StringSerializer;
35  import org.junit.AfterClass;
36  import org.junit.BeforeClass;
37  import org.junit.Test;
38  
39  
40  /**
41   * A class to test multi-threaded operations on the btree
42   *  
43   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
44   */
45  public class MultiThreadedBtreeTest
46  {
47      /** The btree we use */
48      private static BTree<Long, String> btree;
49  
50  
51      /**
52       * Create the btree once
53       * @throws IOException If the creation failed
54       */
55      @BeforeClass
56      public static void setup() throws IOException
57      {
58          btree = new BTree<Long, String>( "test", new LongSerializer(), new StringSerializer() );
59      }
60  
61  
62      /**
63       * Close the btree
64       */
65      @AfterClass
66      public static void shutdown() throws IOException
67      {
68          btree.close();
69      }
70  
71  
72      /**
73       * Create a btree with 500 000 elements in it
74       * @throws IOException If the creation failed
75       */
76      private void create500KBTree() throws IOException
77      {
78          Random random = new Random( System.nanoTime() );
79  
80          int nbElems = 500000;
81  
82          // Create a BTree with 500 000 entries
83          btree.setPageSize( 32 );
84  
85          for ( int i = 0; i < nbElems; i++ )
86          {
87              Long key = ( long ) random.nextLong();
88              String value = Long.toString( key );
89  
90              try
91              {
92                  btree.insert( key, value );
93  
94                  if ( i % 100000 == 0 )
95                  {
96                      System.out.println( "Written " + i + " elements" );
97                  }
98              }
99              catch ( Exception e )
100             {
101                 e.printStackTrace();
102                 System.out.println( btree );
103                 System.out.println( "Error while adding " + value );
104                 return;
105             }
106         }
107     }
108 
109 
110     /**
111      * Browse the btree in its current revision, reading all of its elements
112      * @return The number of read elements 
113      * @throws IOException If the browse failed
114      */
115     private int testBrowse() throws IOException
116     {
117         TupleCursor<Long, String> cursor = btree.browse();
118 
119         int nb = 0;
120         long elem = Long.MIN_VALUE;
121 
122         while ( cursor.hasNext() )
123         {
124             Tuple<Long, String> res = cursor.next();
125 
126             if ( res.getKey() > elem )
127             {
128                 elem = res.getKey();
129                 nb++;
130             }
131         }
132 
133         cursor.close();
134 
135         return nb;
136     }
137 
138 
139     /**
140      * Check that we can read the btree while it is being modified. We will start
141      * 100 readers for one writer.
142      * 
143      * @throws InterruptedException If the btree access failed.
144      */
145     @Test
146     public void testBrowseMultiThreads() throws InterruptedException
147     {
148         int nbThreads = 100;
149         final CountDownLatch latch = new CountDownLatch( nbThreads );
150 
151         Thread writer = new Thread()
152         {
153             public void run()
154             {
155                 try
156                 {
157                     create500KBTree();
158                 }
159                 catch ( Exception e )
160                 {
161                 }
162             }
163         };
164 
165         long t0 = System.currentTimeMillis();
166 
167         // Start the writer
168         writer.start();
169 
170         for ( int i = 0; i < nbThreads; i++ )
171         {
172             Thread test = new Thread()
173             {
174                 public void run()
175                 {
176                     try
177                     {
178                         int res = 0;
179                         int previous = -1;
180 
181                         while ( previous < res )
182                         {
183                             previous = res;
184                             res = testBrowse();
185                             Thread.sleep( 500 );
186                         }
187 
188                         latch.countDown();
189                     }
190                     catch ( Exception e )
191                     {
192                     }
193                 }
194             };
195 
196             // Start each reader
197             test.start();
198         }
199 
200         // Wait for all the readers to be done
201         latch.await();
202 
203         long t1 = System.currentTimeMillis();
204 
205         System.out.println( " Time to create 500K entries and to have " + nbThreads + " threads reading them : "
206             + ( ( t1 - t0 ) / 1000 ) + " seconds" );
207     }
208 
209 
210     /**
211      * Test that we can use many threads inserting data in a BTree
212      * @throws InterruptedException
213      */
214     @Test
215     public void testInsertMultiThreads() throws InterruptedException, IOException
216     {
217         int nbThreads = 100;
218         final CountDownLatch latch = new CountDownLatch( nbThreads );
219 
220         //Thread.sleep( 60000L );
221 
222         long t0 = System.currentTimeMillis();
223 
224         for ( int i = 0; i < nbThreads; i++ )
225         {
226             final long prefix = i;
227             Thread test = new Thread()
228             {
229                 public void run()
230                 {
231                     try
232                     {
233                         // Inject 1000 elements
234                         for ( int j = 0; j < 1000; j++ )
235                         {
236                             long value = prefix * 1000 + j;
237                             btree.insert( value, Long.toString( value ) );
238 
239                             /*
240                             if ( j % 10000 == 0 )
241                             {
242                                 System.out.println( "Thread " + Thread.currentThread().getName() + " flushed " + j
243                                     + " elements" );
244                             }
245                             */
246                         }
247 
248                         latch.countDown();
249                     }
250                     catch ( Exception e )
251                     {
252                     }
253                 }
254             };
255 
256             // Start each reader
257             test.start();
258         }
259 
260         // Wait for all the readers to be done
261         latch.await();
262 
263         long t1 = System.currentTimeMillis();
264 
265         // Check that the tree contains all the values
266         try
267         {
268             for ( long i = 0L; i < 10000L; i++ )
269             {
270                 assertEquals( Long.toString( i ), btree.get( i ) );
271             }
272         }
273         catch ( KeyNotFoundException knfe )
274         {
275             fail();
276         }
277 
278         System.out.println( " Time to create 1M entries : "
279             + ( ( t1 - t0 ) / 1000 ) + " seconds" );
280     }
281 }