Thread safe lock-free concurrent write operations for use with multi-threaded in-line logging
The disclosed embodiments relate to a mechanism for allowing concurrent access, e.g., write operations, to a data structure, e.g., a file, which may have limited capacity, by multiple processes or threads and, in particular, for allowing concurrent, or otherwise substantially simultaneously, appending of data to the file thereby. Each process/thread requests the amount of space it needs to append its data. Upon request, the disclosed mechanism allocates and reserves the requested amount of space and allows the requesting process/thread to commence its append operation. Subsequent to the commencement of the append operation, another thread is then free to request space for its needs and commence its append operation concurrently, or otherwise substantially simultaneously, with the previous append operation, i.e. before the prior append operation is completed.
1 . A system comprising:
a processor; and
a memory coupled therewith, wherein the memory comprises computer executable instructions operative to cause the processor to:
subsequent to receipt of a first request, from a first thread, append a first amount of first data in a selected data store beginning at a first location, receive a second request, from a second thread, to append a second amount of second data in the selected data store, wherein at a time of receipt of the second request, the first thread has at least begun appending the first data to the selected data store beginning at the first location;
determine, upon receipt of the second request, that the second amount of the second data does not exceed an available capacity of the selected data store;
compute, upon determination that the second amount does not exceed the available capacity of the selected store, based on the first location and the first amount, a second location in the selected data store, offset from the first location by the first amount;
determine that the second location is ready for appending by the second thread;
allocate space in the selected data store beginning at the computed second location sufficient to receive the second amount of the second data to be appended by the second thread; and
upon computation of the second location and allocation of space, cause the second thread to append the second data to the selected data store beginning at the computed second location, whereby, substantially simultaneously, the second thread commences appending the second data to the selected data store beginning at the computed second location at least before the appending, by the first thread, of the first data to the selected data store beginning at the first location is completed.
2 . The system of claim 1 , wherein the second thread begins appending the second data to the selected data store beginning at the computed second location at least before the appending, by the first thread, of the first data to the selected data store is completed.
3 . The system of claim 1 , wherein upon receipt of the second request, the first thread has not completed appending the first data to the selected data store.
4 . The system of claim 1 , wherein the computer executable instructions are further operative to cause the processor to receive a confirmation of the completion of the appending of the first data from the first thread and the completion of the appending of the second data from the second thread.
5 . The system of claim 1 , wherein the computer executable instructions are further operative to cause the processor to:
determine that the second amount of the second data will exceed an available capacity of the selected data store; and
cause a prevention of the second thread from appending the second data to the selected data store.
6 . The system of claim 1 , wherein, upon receipt of the first request, the computer executable instructions are further operative to cause the processor to:
determine that the first amount of the first data exceeds an available capacity of the selected data store; and
cause the selected data store to be closed and a new data store to be selected.
7 . The system of claim 6 , wherein, upon receipt of the second request, the computer executable instructions are further operative to cause the processor, prior to the allocation of space in the newly selected data store for the second data, to:
determine that the previously selected data store is closed and that the newly selected data store is ready; and
allocate space in the newly selected data store sufficient to receive the second data to be appended by the second thread.
8 . The system of claim 6 , wherein, upon receipt of the second request, the computer executable instructions are further operative to cause the processor, prior to the allocation of space in the newly selected data store for the second data, to:
determine that the previously selected data store is not closed and that newly selected data store is not ready; and
cause a prevention of the second thread from appending the second data to the newly selected data store.
9 . The system of claim 6 , wherein, upon receipt of the second request, the computer executable instructions are further operative to cause the processor, prior to the allocation of space in the newly selected data store for the second data, to:
determine that the newly selected data store is ready, and
allocate space in the selected data store sufficient to receive the second data to be appended by the second thread.
10 . The system of claim 6 , wherein, upon receipt of the second request, the computer executable instructions are further operative to cause the processor, prior to the allocation of space in the newly selected data store for the second data, to:
determine that the newly selected data store is not ready, and
cause a prevention of the second thread from appending the second data to the newly selected data store.
11 . The system of claim 1 , wherein at least one of the first and second threads is implemented by another processor.
12 . A method comprising:
receiving, by a processor, subsequent to receipt of a first request, from a first thread, to append a first amount of first data in a selected data store beginning at a first location, a second request, from a second thread, to append a second amount of second data in the selected data store, wherein at a time of receipt of the second request, the first thread has at least begun appending the first data to the selected data store beginning at the first location;
determining, by the processor, upon receiving the second request, that the second amount of the second data does not exceed an available capacity of the selected data store;
computing, by the processor, upon determining that the second amount does not exceed the available capacity of the selected store, based on the first location and the first amount, a second location in the selected data store, offset from the first location by the first amount;
determining, by the processor, that the second location is ready for appending by the second thread;
allocating, by the processor, space in the selected data store beginning at the computed second location sufficient to receive the second amount of the second data to be appended by the second thread; and
causing, by the processor, upon computing the second location and allocation of allocating the space, the second thread to append the second data to the selected data store beginning at the computed second location, whereby, substantially simultaneously, the second thread commences appending the second data to the selected data store beginning at the computed second location before the appending, by the first thread, of the first data to the selected data store is completed.
13 . The method of claim 12 , wherein, the second thread begins appending the second data to the selected data store beginning at the computed second location at least before the appending of the first data to the selected data store by the first thread is completed.
14 . The method of claim 12 , wherein upon receipt of the second request, the first thread has not completed appending the first data to the selected data store.
15 . The method of claim 12 , further comprising, receiving, by the processor, a confirmation of the completion of the appending of the first data from the first thread and the completion of the appending of the second data from the second thread.
16 . The method of claim 12 , further comprising:
determining, by the processor, that the second amount of data will exceed an available capacity of the selected data store; and
causing, by the processor, a prevention of the second thread from appending the second data to the selected data store.
17 . The method of claim 12 , further comprising:
determining, by the processor, upon receipt of the first request, that the first amount of the first data exceeds an available capacity of the selected data store; and
causing, by the processor, the selected data store to be closed and a new data store to be selected.
18 . The method of claim 17 , further comprising:
determining, by the processor, upon receipt of the second request and prior to the allocation of space in the newly selected data store for the second data, that the previously selected data store is closed and that the newly selected data store is ready; and
allocating, by the processor, upon determining that the newly selected data store is ready, space in the newly selected data store sufficient to receive the second data to be appended by the second thread.
19 . The method of claim 17 , further comprising:
determining, by the processor, upon receipt of the second request and prior to the allocation of space in the newly selected data store for the second data, that the previously selected data store is not closed and that the newly selected data store is not ready; and
causing, by the processor, a prevention of the second thread from appending the second data to the newly selected data store.
20 . The method of claim 17 , further comprising, upon receipt of the second request and prior to the allocation of space in the newly selected data store for the second data:
determining, by the processor that the newly selected data store is ready, and
allocating, by the processor, space in the newly selected data store sufficient to receive the second data to be appended by the second thread.
21 . The method of claim 17 , further comprising, upon receipt of the second request and prior to the allocation of space in the newly selected data store for the second data:
determining, by the processor that the newly selected data store is not ready, and
causing, by the processor, a prevention of the second thread from appending the second data to the newly selected data store.
22 . A system comprising:
means for receiving, subsequent to receipt of a first request from a first thread to append a first amount of first data in a selected data store beginning at a first location, a second request from a second thread to append a second amount of second data in the selected data store, wherein at a time of receipt of the second request, the first thread has at least begun appending the first data to the selected data store beginning at the first location;
means for determining, upon receiving the second request, that the second amount of the second data does not exceed an available capacity of the selected data store;
means for computing, upon determining that the second amount does not exceed the available capacity of the selected store, based on the first location and the first amount, a second location in the selected data store, offset from the first location by the first amount;
means for determining that the second location is ready for appending;
means for allocating space in the selected data store beginning at the computed second location sufficient to receive the second amount of the second data to be appended by the second thread; and
means for causing, upon computing the second location and allocating the space, the second thread to append the second data to the selected data store beginning at the computed second location, whereby, substantially simultaneously, the second thread commences appending the second data to the selected data store beginning at the computed second location before the appending, by the first thread, of the first data to the selected data store beginning at the first location is completed.