Design And Implementation Of Lock-free Data Structures In High-performance Message Queue

In recent years,the development trend of processors has shifted from high frequency to multi-core,so it is practically significant to make use of multithreading to exert the computing power of multi-core processors.Message queues are widely used in operating systems and applications.Message queues based on lock synchronization mechanisms cannot take advantage of multi-core processors,at the same time the use of locks increases the risk of serious problems such as data competition and deadlock.Therefore,researchers have conducted in-depth researches on Lock-Free data structures.Lock-free data structures using compare and swap synchronization primitives can get rid of problems such as data competition and deadlock,but most of Lock-Free data structures are not scalable enough to give full play to performance advantages of multi-core processors.The core data structures of message queue are queue and filter,so it is importantly significant to improve performance of message queues using well-scalable queues and filters.Aimed to improve existing message queues,this thesis studies the realization of message queue middleware based on Lock-Free data structure technologies.The main works are as follows:(1)This thesis proposes a Lock-Free queue DQueue based on fetch and add.Each producer uses a local buffer to temporarily store enqueue request.When the buffer is full,data is written to shared queue in batches.When a consumer reads the data temporarily stored in buffers,DQueue uses ordinary access statements instead of expensive atomic instruments.DQueue improves efficiency by reducing cache misses and write buffer refresh.(2)This thesis proposes two Cuckoo hash tables based on compare and swap.When writers are greater than readers,the Load-Balance Cuckoo hash table improves writing efficiency by limiting the load rate of each bucket in real time.When readers are greater than writers,the good locality Cuckoo hash table improves positive query efficiency by storing data items in a certain area of hash table.(3)This thesis proposes message queue CDMQ.The Cuckoo hash table based on compare and swap is improved into a concurrent Cuckoo filter CCF.CDMQ is based on CCF and DQueue.Multiple producers write data,and a consumer reads data filtered by CCF.Experiments show that CDMQ has high throughput and good scalability.