Saturday, 23 November 2013

Lock-free data structures


I hope that this article will be the start of a cycle of notes on lock-free data structures. I want to share with habrasoobschestvom their experiences, observations and reflections on what a lock-free data structures, how to implement them to determine whether the concept of the STL containers standard to lock-free containers, and when standing (and whether or not at all) to use lock -free data structures.



Talk about lock-free data structures is meaningless without lighting topics such as atomic operations, the memory model, implemented in a particular programming language (unless, of course, the language is old enough to think about their memory model), the safe release of memory compilers and they use optimization, modern processor architectures - all of these topics will be more or less affected in a given cycle. I take the liberty to talk about all these things, though I do not consider myself an absolute expert in any of them. On the other hand, having no idea about them, I could not write and develop library libcds , - Open Source C + + library of lock-free containers and algorithms for the safe release of memory (safe memory reclamation). Cds - is an abbreviation of Concurrent Data Structure, and the prefix "lib" - is, oddly enough, "library". I'll start with the history of the library. It was back in 2006.



2006
Then I worked in a fairly large company, writing software for one telecommunications operator of the Big Three. We developed a fairly complex server applications for zoo hardware platforms in which the first place was (and will always stand) performance problem. It was decided, inter alia, by parallelizing data processing. As usual, the parallelization led to the emergence of common (shared) data to which access is required to synchronize.


Once in one of the discussions, my colleague casually asked, "have you heard anything about the lock-free queue?" At that time I did not know anything about it. But by asking google, found a few articles that cited pseudo lock-free queue. Reading them several times, I did not understand. More precisely, I switched to "did not understand" after rolling up their sleeves and saying "right now!" Worldwide (say, all you fools, I've been a smart one), I tried to "simplify" algorithms, bringing them in line with common sense. A month later, the fight against segmentation fault, my common sense capitulate. That's when I "did not understand". I do not understand how it works at all, and even if it somehow works, how it can be implemented in C + +. But somehow it should work, otherwise intelligent people would not write these articles, and other smart people they would not invoke (scientific articles were, and at the end of each, as usual in the scientific community, cited reference lists). Following these links, for a year, I read dozens of megabytes and not very useful information from the software developer guide for processor architectures and ending with review articles on general approaches implement lock-free algorithms. Along the way I was writing something (in C + +, of course) on this topic, implementing these or other primitives. It should be noted that at this time (year 2006-2007) standard C + +11 more optimistically called C + +0 x, in the STL does not have atomic primitives, and the interface has yet to be scheduled, and sometimes capricious compilers on my atomic primitives and issued a non-working code particularly critical areas. By 2008, I began to outline the contours of the misty library libcds. First tests on different platforms yielded encouraging, sometimes astonishing ("it was 50 times faster!"), The results and I fully immersed in the world of lock-free. In 2010 I published the first on SourceForge (0.5.0) version of the library. Today the freshest version of the library - 1.4.0, we are working on version 1.5.0. proceed to the general review of the lock-free data structures. Thus, the main task of the programmer in designing and developing complex software projects, especially server - the most effective use of all available resources target platform. Modern computer, even a smartphone or tablet - is a multiprocessor hardware, so one way of improving performance is to parallelize programs. Parallel streams (threads) treated some shared data (shared data); hence our main task is to organize concurrent access to shared data such. During the 80-ies of the last century, it was popular so-called structured programming, positioned as a way to write good programs. Apologist structured programming was Nicholas Wirth, author of the language Pascal, who wrote the bestseller "Algorithms + data structures = programs." Interestingly, this old formula indicates a weak point of modern API type pthreads, Win32 API, the proposed operating systems: API provide a vehicle for constructing parallel programs (it means - threads, threads), but do not provide tools for building parallel data structures that provide shared access. Instead API provide means limiting access to data in the form of synchronization primitives. However, synchronization - the bottleneck of parallel programs. Inherently synchronization - an antipode Parallelism: rasparallelivaya algorithms, we are working with consistent data structures, providing them with job synchronization primitives - critical sections, mutexes (mutex), dummy variables (condvar); as a result, we build all of our streams for the next available a data structure, thereby killing the parallelism. Synchronization primitives are sometimes kernel objects, so an appeal to such an object can be very expensive: you may need a context switch, the transition to the level of OS kernel support queues access to protected data synchronization primitive, etc. And all this is, perhaps, only To change the data value of a single indicator, ie to perform one or two assembler instructions. Overheads can be (and in fact is) very large. Also, do not forget that to the kernel - is limited by the number of resource. Another drawback is the weak synchronization scalability. As the number of streams synchronized access to data becomes the bottleneck of the program, often with increasing degree of parallelism rather than proportional increase in productivity we get it deterioration in conditions of heavy load (high contention). Guided by Wirth's "Algorithms + data structures = programs" in their work over libcds I focused only on data structures in the library, you will not find a parallel sorting algorithms or parallel for-each. The library contains only competitive data structures - all, list, map, set, etc. - and the necessary algorithms to support lock-free data, primarily algorithms safe release of memory (safe memory reclamation). Often, one or another data structure is represented by several implementations. So was originally intended: as a rule, there are several interesting algorithms that implement all or map, and I do not know in general which one is "better": first, the concept of "better" or "worse" is relative and depends on the iron and specific task, and secondly, until realizuesh algorithm and compare it with others, you can not tell it better or not. But if the algorithm is implemented and debugged, then why does not he take his place in the library (and give the user a tough choice)? ..
In an academic environment to study ways to implement competitive data structures that provide simultaneous access to shared data, led to the creation of several key areas:
  • Lock-free data structures;
  • Fine-grained algorithms;
  • Transactional memory (transactional memory)


In libcds no implementations based on transactional memory.Transactional memory - it is a vast area of research aimed mainly for the future. Algorithms based on transactional memory, mean, roughly speaking, that the memory supports atomic transactions that can take atomically (commit) or reject (rollback). Obviously, this memory must be implemented in hardware, by software existing implementation, according to the researchers themselves do not have sufficient capacity. In fairness it should be noted that Intel's Haswell architecture already have transactional support in their system commands, so we should expect that the heyday of algorithms based on the principles of transactional memory, just around the corner. Fine-grained algorithms - it's sophisticated synchronization methods usually constructed not use synchronization primitives provided OC, and by applying the "light" atomic primitives, such as spin-lock. Based on these primitives constructed data structure allows parallel read or write in parallel, in which synchronization is performed at the node (node) or page (page, bucket), and a data structure built into the algorithms operations over the structure. Often fine-grained containers show performance comparable to that of lock-free containers at a relatively low load. Library libcds not squeamish such data structures. Lock-Free data structures I'll call data structures that do not require external synchronization access. It's casual, purely technical definition that reflects the internal structure of the container and the operation on them. The word "foreign" here deliberately allocated: we must understand that even without the use of special support from the processor lock-free data structures to build, most likely will not succeed. But support for such a lock-free containers provided not synchronized access to consistent methods of the container, and the mechanism of atomic modifications , hard-wired into the methods of the container, or internal clock at the level of the container components (nodes, buckets, pages). formal definition of lock-free object sounds [Her91]: shared object called lock-free object (unblockable, non-blocking object) if it ensures that some flow finishes executing operations on the object in a finite number of steps regardless of the outcome of the other threads (even if these other flows resulted in the collapse). More rigorous notion of wait-free object reads the object is wait-free, if each thread completes an operation on an object in a finite number of steps.Lock-free condition ensures the promotion of at least any one stream, while the stronger condition wait-free guarantees the successful execution of all threads. In the theory of competitive data structures, there is also the notion of linearizability [Her90], which plays an important role in formal proofs of correctness lock-free algorithms. Roughly speaking, the algorithm is linearizable (linearizable), if the result of his work can be seen at the end of the algorithm. For example, the result list can be seen in the inset at the end of the function insert. Sounds like an idiot, but maybe come up with an algorithm that makes the list box and is not linearizable. For example, any kind of buffering may lead to a breach of this property: instead of inserting we can put a new element into a buffer, a command to another thread "Paste item from the clipboard into the list" and not wait until the item is inserted, or whether we will only insert when the buffer accumulate a sufficient number of elements. Then at the end of the insert function in the list, we can not guarantee that the item is in the list, all that we can to ensure that this element is sure to be(future!) is inserted into the list now or later. These concepts are widely used in research works, and my article does not pretend to research, so I'll use the term lock-free in the "narrow-minded" sense to refer to a class of competitive containers constructed without the use of traditional patterns of synchronization, or do not require external synchronization.

What is characterized by lock-free algorithms? Perhaps the first thing that catches your eye - it is their complexity. Can you imagine what a regular turn, implemented on a linked list? Very simple code:
Show a very simple code
struct Node {
        Node * m_pNext;
};
class  queue {
        Node * m_pHead;
        Node * m_pTail;
Public :
        queue (): m_pHead ( NULL ), m_pTail ( NULL ) {}
         void enqueue (Node * P)
        {
            p-> m_pNext = m_pTail;
            m_pTail = p;
            if (! m_pHead)
                m_pHead = p;
        }
        Node * dequeue ()
        {
            if (! m_pHead) return  NULL ;
            Node * p = m_pHead;
            m_pHead = p-> m_pNext;
            if (! m_pHead)
                m_pTail = NULL ;
             return P;
        }
};

You can write and even shorter. And this is what the methods enqueue / dequeue (synonyms push / pop) implementation classical algorithm lock-free queue of Michael & Scott ([Mic96], the code is taken from the class of minimal cuts cds :: intrusive :: MSQueue library libcds):

Show the same, but written very cumbersome
bool enqueue (value_type & val)
{
      * = NODE_TYPE pnew node_traits :: to_node_ptr (Val)   ;

      GC :: typename Guard guard     ; 
      back_off bkoff   ;

      NODE_TYPE * t     ;
       while (true) {
           t = guard . protect (m_pTail, node_to_value ())   ;

           NODE_TYPE pNext * = t-> m_pNext . load (memory_model :: memory_order_acquire)   ;
           if (pNext! = null_ptr <node_type *> ()) {
                / / Tail is misplaced, advance it
                m_pTail . compare _exchange_weak (t, pNext, memory_model :: memory_order_release,
                                                                                 CDS_ATOMIC :: memory_order_relaxed) ; 
                Continue     ;
           }

          NODE_TYPE * tmp = null_ptr <node_type *> () ; 
          if (t-> m_pNext . compare _exchange_strong (tmp, pnew, memory_model :: memory_order_release,
                   CDS_ATOMIC :: memory_order_relaxed))
          {
                    Break     ;
          }
          bkoff ()     ;
     }
    + + M_ItemCounter     ;

     m_pTail . compare _exchange_strong (t, pnew, memory_model :: memory_order_acq_rel,
                                                                        CDS_ATOMIC :: memory_order_relaxed) ;

     return true ;      
}

value_type * dequeue ()
{
     * NODE_TYPE pNext    ; 
     back_off bkoff       ; 
     typename GC :: template GuardArray < 2 > Guards   ;

      NODE_TYPE * H        ;
      while (true) {
           H = Guards . protect ( 0 , m_pHead, node_to_value ())            ; 
           pNext = Guards . protect ( 1 , H-> m_pNext, node_to_value ())     ; 
           if (m_pHead . load (memory_model :: memory_order_relaxed)! = H)
                Continue     ;

           if (pNext == null_ptr <node_type *> ())
                 return NULL   ; / / empty queue

           NODE_TYPE * t = m_pTail . load (memory_model :: memory_order_acquire) ;
           if (h == t) {
                / / It is needed to help enqueue
               m_pTail . compare _exchange_strong (t, pNext, memory_model :: memory_order_release,
                                                                                  CDS_ATOMIC :: memory_order_relaxed) ; 
               Continue     ;
           }

           if (m_pHead . compare _exchange_strong (H, pNext,
                     memory_model :: memory_order_release, CDS_ATOMIC :: memory_order_relaxed))
           {
                    Break     ;
           }
           bkoff ()     ;
     }

     - M_ItemCounter           ;

     dispose_node (H)    ; 
     pNext return ;
}


Complex algorithm. The same linked list, but even a simple visual comparison of conventional and lock-free queue is saying something. In the lock-free queue, we see:
  • endless loop - we're trying to perform an operation not yet out. This is a typical pattern of use atomic operationcompare_exchange ;
  • protection of local variables ( Guards ) using one of the methods of safe working memory (pointers) in lock-free algorithms, in this case - is a method of Hazard Pointers;
  • use atomic primitives C + +11 - load, compare_exchange , memory barriers memory_order_xxx ;
  • helping - a very common technique in lock-free algorithms, when one thread helps another to make it work;
  • use back-off strategies (functor bkoff ), which are not required, but can in some cases significantly relieve the CPU under heavy load when many threads are accessing the queue at the same time


Now I will not explain anything, because all these things are very extensive and require a separate discussion. Let keep the intrigue. I hope to discuss these topics in future articles. following article will focus on the concept of a cornerstone, on which all lock-free data structures - atomicity and atomic primitives. And finally - a useful book (not paper), in which, from my point of view, more fully address the issues of competitive programming. At the moment I know of two good works: 1. Nir Shavit, Maurice HerlihyThe Art of Multiprocessor Programming . Russian translation, as far as I know, no. The book is very well-known in the world of lock-free authors describe a set of parallel algorithms and methods of their construction. All the examples in Java, so the authors do not have to worry about freeing memory, the memory model C + + (in the Java memory model more severe) and other things that are embedded in the Java language itself, but in C + + you have to write it all yourself. Despite this, the book is very useful. 2.Anthony Williams C + + Concurrency in Action (have a Russian translation ). The book is well-known in the world of C + + website devoted to issues of multithread programming is in C + +, available describes a new C + +11 standard and the new opportunities provided by the standard for the implementation of parallel algorithms. It is highly recommended for those. Links: [Her90] M. Herlihy, JM Wing Linearizability: A Correctness Condition for Concurrent Objects , ACM Transactions on Programming Languages ​​and Systems, 1990 [Her91] M. Herlihy A Methodology for Implementing Highly Concurrent Data Object , 1991 [Mic96] M.Michael, M.Scott Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms

No comments:

Post a Comment