3 ms·

Another approach is just to use two stacks, one for writing and one for flushing. User threads write log lines directly to buffers from an allocator usually vi

Another approach is just to use two stacks, one for writing and one for flushing. User threads write log lines directly to buffers from an allocator usually via a TLS mediated stream. The use of an allocator avoids locking on system calls during memory allocation and minimizes copying between user code and eventual flush to disc/network. Buffers are written to the write stack using atomic CAS, if no buffers are available from the allocator the user thread may spin, or force a flush in the same way as the flushing thread. A single flushing thread watches the write stack on a timer and when it reaches some threshold it uses an atomic CAS to switch the head pointer between the flush and write stacks before enumerating the flush stack and writing all buffers to disc/network freeing the buffers back to the allocator (again using atomic operations). It is subtle but if done right user threads and the flushing thread interact optimally in response to demand. This solution is much more flexible than a ring buffer and also much simpler and faster in testing than any complicated patterns like disruptor and competitive with expensive hardware logging solutions. It recognizes the fact that much of the overhead in logging comes from expensive copying of log data in memory, and it also ensures that minimum context switching takes place which is essential if you are not to defeat the entire point of fast lock free algorithms. Unlike a ring bufffer it has no blocking or performance degredation when the buffer gets full and requires no large chunk of memory to be permanently allocated, although the allocator may periodically allocate new temporary memory if its buckets are full or if a log line is too large for a the maximum bucket size. What you end up with is a logging system where user threads are minimally impacted during writes and throughput is able to max out the disc/network.

j_s 12y ago
Thanks for sharing this technique. Are you aware of any existing open source implementations?
- emerson_clarke 12y ago
  Unfortunately no, thus far i have only implemented it in a commercial context as part of a high frequency trading system.
  - zerd 12y ago
    Do you know of any papers/writeups where you can get more details of the technique?
    - emerson_clarke 12y ago
      Im sure im not the first to have done something like this for logging or buffering in general, but im not aware of any writeups. Information on lock free data structures and the caveats (they are extremely difficult to get right) is freely available though: http://www.cs.cmu.edu/~410-s05/lectures/L31_LockFree.pdf http://en.wikipedia.org/wiki/ABA_problem
mortoray 12y ago
The problem with this approach is that it requires coordination on when the swap of the two stacks is done. Using CAS doesn't really help. The consumer doesn't know if the producer is currently writing into the stack or not. It still needs another mechanism to determine when it is safe to read from that stack.
- emerson_clarke 12y ago
  I think you misunderstand the CAS operation. It performs an atomic compare and swap on a pointer (32 or 64 bits), so obviously it requires no coordination to switch out the head pointer of a stack. For example, on an LP64 architecure: Item * first = writers.first; while( CAS((long *)&writers.first,(long)0,*((long*)&first)) != *((long*)&first)) { first = writers.first; } Here first represents the flush stack, and writers represents the write stack. We just swap the first pointer of the write stack with a null pointer, and this only succeeds if no other threads are currently trying to perform the same operation. This works because pushing to the stack is performed using a similar atomic CAS of the head pointer.
  - mortoray 12y ago
    No, I'm saying you have coordinated the writing to the stack. It's not enough to just swap pointers to the stacks themselves, but you have to know how much data has been written to the stack. Perhaps your description is incomplete?
    - emerson_clarke 12y ago
      The stack head pointers can be swapped and flushed without knowing how much data is in it. However, if you need to know the count/size... Then in general you must accept that the count/size of the write stack is dynamic, so even if you use an integer to track the value (and keep updated with atomic exchange or increment), at the point that you read its value on one thread it may have already changed on another. So it doesn't really matter if you reset the value to 0 using an interlocked exchange (this cant be done as an atomic unit with respect to the head pointers unless your platform supports a double CAS). Some loss of count/size information will occur. Alternatively you can safely iterate through the stack to calculate the count/size anytime you need it (provided the next pointers are also treated atomically). Neither option will give you the exact size since as discussed above its always dynamic, but this i no way impedes the functioning of the write/flush stacks as described. In my solution i just set the value of the count/size to 0, and disregard any loss of information since it is not critical.
xenadu02 12y ago
When I read the OP I was thinking exactly along these lines. There are a lot of nifty tricks you can use with atomic compare-exchange. The Mac/iOS equivalent is the OSAtomicCompareAndSwap family of functions. For C# users, I wrote about Interlocked.CompareExchange here: http://www.russbishop.net/interlocked-compareexchange http://www.russbishop.net/interlocked-compareexchange. It's one of the few high-level language operations that maps directly to a processor instruction. If you have side-effect-free mutation functions you can use compexch to merge mutations among multiple threads without locking or blocking, which I've used with immutable snapshots to provide transactional consistency to in-memory objects (without having to pre-check all conditions before mutation or having to create inverses for all operations that can 'roll back' the object mutations). Combined with immutable collections using AVL trees you can get copy-on-write immutable snapshots which is the only real way to deal with massive (50GB+) in-memory datasets that need highly concurrent reads, what-if temporary writes, and permanent writes.

j_s 12y ago

Thanks for sharing this technique. Are you aware of any existing open source implementations?

emerson_clarke 12y ago
Unfortunately no, thus far i have only implemented it in a commercial context as part of a high frequency trading system.
- zerd 12y ago
  Do you know of any papers/writeups where you can get more details of the technique?
  - emerson_clarke 12y ago
    Im sure im not the first to have done something like this for logging or buffering in general, but im not aware of any writeups. Information on lock free data structures and the caveats (they are extremely difficult to get right) is freely available though: http://www.cs.cmu.edu/~410-s05/lectures/L31_LockFree.pdf http://en.wikipedia.org/wiki/ABA_problem

mortoray 12y ago

The problem with this approach is that it requires coordination on when the swap of the two stacks is done. Using CAS doesn't really help. The consumer doesn't know if the producer is currently writing into the stack or not. It still needs another mechanism to determine when it is safe to read from that stack.

emerson_clarke 12y ago
I think you misunderstand the CAS operation. It performs an atomic compare and swap on a pointer (32 or 64 bits), so obviously it requires no coordination to switch out the head pointer of a stack. For example, on an LP64 architecure: Item * first = writers.first; while( CAS((long *)&writers.first,(long)0,*((long*)&first)) != *((long*)&first)) { first = writers.first; } Here first represents the flush stack, and writers represents the write stack. We just swap the first pointer of the write stack with a null pointer, and this only succeeds if no other threads are currently trying to perform the same operation. This works because pushing to the stack is performed using a similar atomic CAS of the head pointer.
- mortoray 12y ago
  No, I'm saying you have coordinated the writing to the stack. It's not enough to just swap pointers to the stacks themselves, but you have to know how much data has been written to the stack. Perhaps your description is incomplete?
  - emerson_clarke 12y ago
    The stack head pointers can be swapped and flushed without knowing how much data is in it. However, if you need to know the count/size... Then in general you must accept that the count/size of the write stack is dynamic, so even if you use an integer to track the value (and keep updated with atomic exchange or increment), at the point that you read its value on one thread it may have already changed on another. So it doesn't really matter if you reset the value to 0 using an interlocked exchange (this cant be done as an atomic unit with respect to the head pointers unless your platform supports a double CAS). Some loss of count/size information will occur. Alternatively you can safely iterate through the stack to calculate the count/size anytime you need it (provided the next pointers are also treated atomically). Neither option will give you the exact size since as discussed above its always dynamic, but this i no way impedes the functioning of the write/flush stacks as described. In my solution i just set the value of the count/size to 0, and disregard any loss of information since it is not critical.

xenadu02 12y ago

When I read the OP I was thinking exactly along these lines. There are a lot of nifty tricks you can use with atomic compare-exchange. The Mac/iOS equivalent is the OSAtomicCompareAndSwap family of functions. For C# users, I wrote about Interlocked.CompareExchange here: http://www.russbishop.net/interlocked-compareexchange http://www.russbishop.net/interlocked-compareexchange. It's one of the few high-level language operations that maps directly to a processor instruction. If you have side-effect-free mutation functions you can use compexch to merge mutations among multiple threads without locking or blocking, which I've used with immutable snapshots to provide transactional consistency to in-memory objects (without having to pre-check all conditions before mutation or having to create inverses for all operations that can 'roll back' the object mutations). Combined with immutable collections using AVL trees you can get copy-on-write immutable snapshots which is the only real way to deal with massive (50GB+) in-memory datasets that need highly concurrent reads, what-if temporary writes, and permanent writes.