Live data from Hacker News

Wait-free queueing and ultra-low latency logging

mortoray.com

21–30 of 56 posts

Re: Wait-free queueing and ultra-low latency logging

#21
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.

Re: Wait-free queueing and ultra-low latency logging

#22
> Profiling revealed that copying the format string was a significant part of the overall time.

Not surprising. In general, memory allocations and copying are to be avoided unless absolutely necessary, if you want efficient code. I've made huge performance improvements to systems simply by getting rid of a memory copy that was located in a tight loop. As the saying goes, "the fastest way to do something is to not do it at all."

Also, does anyone find the term "wait-free queueing" somewhat oxymoronic? A queue is usually something to wait in.

Re: Wait-free queueing and ultra-low latency logging

#24

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 avail…

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

Re: Wait-free queueing and ultra-low latency logging

#25
post #3

Earlier quoted context omitted.

In this particular case you should be able to use no-op instructions to spin without consuming much power. Since the consumer only spins when the queue is empty we know there will be space on the ring buffer and producers won't be impacted. When the consumer wakes from a no-op loop and finds work on the queue it can switch back to a hot loop for a certain amount of time before returning to a no-op cold loop. My under…

I think your colleague is talking about the PAUSE instruction (which is also known as REP NOP, since they encode to the same bytes). It's a special instruction that hints to the processor that it's in a spin-loop waiting on a synchronisation variable to change. It's used in tight wait loops like this: wait_loop: pause cmp eax, sync_var jne wait_loop The PAUSE instruction introduces a small delay to synchronise the sp…

How would there be many requests? Wouldn't it load the cache line once into the shared state and then spin waiting for the line to be invalidated before reloading?

Re: Wait-free queueing and ultra-low latency logging

#26

Earlier quoted context omitted.

I'm going on what wikipedia describes as [lock-free]( https://en.wikipedia.org/wiki/Lock-free ). In that theoretical sense there is no difference between a mutex lock and a spin-lock. But, they may both be "lock-free". By the definition presented there virtually all programs are lock-free... that would be better termed "deadlock-free". Most people I've meet though assume lock-free just implies not using mutexes, but…

The definition for lock free written there is the same as the one I wrote above. The crucial sentence is found in the second paragraph. Where non-blocking is the umbrella term covering both lock, wait and obstruction free algorithms. "In modern usage, therefore, an algorithm is non-blocking if the suspension of one or more threads will not stop the potential progress of the remaining threads" Neither spin locks nor O…

I think I better understand what "lock-free" means now, thank you for the explanation.

I will review what I said in my article and ensure I'm not spreading any misinformation. When I learned of lock-free I was presented with a spin-lock like system as an example, but that is clearly incorrect.

The key I guess is that any thread could halt at any point and the other threads are not blocked (within obvious practical limitations). This doesn't mean other works may not have to redo some work, such as finding a new terminal node in a lock-free list.

In practice lock-free is likely sufficient, even in real-time systems. One would need a very high level of contention to render lock-free incapable (though with a high number of cores it's definitely possible).

Re: Wait-free queueing and ultra-low latency logging

#27

> Profiling revealed that copying the format string was a significant part of the overall time. Not surprising. In general, memory allocations and copying are to be avoided unless absolutely necessary, if you want efficient code. I've made huge performance improvements to systems simply by getting rid of a memory copy that was located in a tight loop. As the saying goes, "the fastest way to do something is to not do…

Well, only one side of the queue was wait-free. The other side, the consumer, was a whole mess of queues and buffers. It's simply the process of putting something in the queue that is fast. Getting out of that queue is a terribly slow operatino.

Re: Wait-free queueing and ultra-low latency logging

#28

Earlier quoted context omitted.

I think your colleague is talking about the PAUSE instruction (which is also known as REP NOP, since they encode to the same bytes). It's a special instruction that hints to the processor that it's in a spin-loop waiting on a synchronisation variable to change. It's used in tight wait loops like this: wait_loop: pause cmp eax, sync_var jne wait_loop The PAUSE instruction introduces a small delay to synchronise the sp…

How would there be many requests? Wouldn't it load the cache line once into the shared state and then spin waiting for the line to be invalidated before reloading?

Honestly, I don't know how this interacts with cache lines.

As far as I know, Intel has not released any official details about what the PAUSE instruction does other than that it slows down spin loops to a reasonable rate. The best source I know of for this information is the Intel® 64 and IA-32 Architectures Optimization Reference Manual (http://www.intel.com/content/dam/www/public/us/en/documents/...). It is fairly vague about what the instruction does, but gives some useful information in 13.5.3 "Spin-Wait Loops", as well as 8.4 "Thread Synchronization", and in particular 8.4.2 "Synchronization for Short Periods" which says:

"On a modern microprocessor with a superscalar speculative execution engine, [a spin loop] results in the issue of multiple simultaneous read requests from the spinning thread. These requests usually execute out-of-order with each read request being allocated a buffer resource. On detection of a write by a worker thread to a load that is in progress, the processor must guarantee no violations of memory order occur. The necessity of maintaining the order of outstanding memory operations inevitably costs the processor a severe penalty that impacts all threads."

So it seems that the concern here is that (without a PAUSE) the speculative execution engine effectively unrolls the spin loop and executes a sequence of reads on the sequence variable. This queues up a list of pending memory operations that need to be unrolled in order to ensure that the result is the same as if they were executed sequentially -- even though in this case it wouldn't make any difference.

Re: Wait-free queueing and ultra-low latency logging

#29
post #3

Earlier quoted context omitted.

In this particular case you should be able to use no-op instructions to spin without consuming much power. Since the consumer only spins when the queue is empty we know there will be space on the ring buffer and producers won't be impacted. When the consumer wakes from a no-op loop and finds work on the queue it can switch back to a hot loop for a certain amount of time before returning to a no-op cold loop. My under…

I think your colleague is talking about the PAUSE instruction (which is also known as REP NOP, since they encode to the same bytes). It's a special instruction that hints to the processor that it's in a spin-loop waiting on a synchronisation variable to change. It's used in tight wait loops like this: wait_loop: pause cmp eax, sync_var jne wait_loop The PAUSE instruction introduces a small delay to synchronise the sp…

I was unaware of the PAUSE function. It certainly did belong inside my spin-loop. The other recommendation of cache-line alignment I was following, and it does make a difference.

Re: Wait-free queueing and ultra-low latency logging

#30
> A key requirement for logging is to write statements, from any thread, in order, to a single log-file.

I do not agree that it's a necessary requirement that all threads must write to a single log-file.

> Formatting strings, required by a log system, is a slow operation.

I also do not agree that it's a necessary requirement that a log system must format strings. Binary log files have their uses. I've used Google Protocol Buffers quite happily. They may not be appropriate for extremely high-speed logs, like a low-latency trading system implies, but they have their uses. I'd be tempted to try something like Cap'n Proto, if I were taking a whack at it.

Post reply on HN