LFQueue
Zhong Wen Ban READMEQing Wang Xia Fan
1. Introduction
- This is a robust lockless queue used in multi processes through shared memory.
- It can deal with the situation that any programs abort at any line.
- It's not the fastest lockless queue but the most robust one.
- (=*o*=)
- Welcome to show your better ideas.
2. Algorithm
- There are two LFRings and an array with the same size.
- Each element in resource ring or message ring identifies one node in the array. (subscription)
- ID -1 means invalid subscription.
- When a queue created, resource ring and message ring would be initialized like these. Resource ring was full of valid IDs, but message ring is none.
- When enqueuing to the queue, get a subscription from resource ring, modify the data in real resource array with subscription got from resource ring, and insert it into the message ring. If all of the IDs were inserted into the message ring and overwrite mode was set, pop a node from message ring, modify the data, and reinsert into the message ring, which means dequeue from the queue and enqueue it again to implement the overwrite mode.
- When dequeuing, it's the same. Get ID from message ring, copy the data out from real resource array, and insert it into the resource ring.
- All operations on getting ID from or inserting ID into are implemented with CAS.
- If you want to know why it's robust, read the code please or you could try to abort at any line.
Resouce ID Ring
---------------------------
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---------------------------
Message ID Ring
-------------------------------
| -1 | -1 | -1 | -1 | -1 | -1 | -1 |
-------------------------------
Real Resource
------------------------------------
| LFNode | LFNode | LFNode | ... |
------------------------------------
3. Usage
C
#include "queue.h"
int main()
{
// Create a LFQueue.
// You can open the queue with key 1234 in another process or thread.
LFQueue_create(1234, 64, 4096, true);
LFQueue *queue = LFQueue_open(1234); // Open a LFQueue.
char buf[64];
const char *data = "hello, world!";
LFQueue_push(queue, data, strlen(data) + 1, NULL);
LFQueue_pop(queue, buf, NULL);
printf("%s\n", buf);
LFQueue_close(queue);
LFQueue_destroy(1234);
}
int main()
{
// Create a LFQueue.
// You can open the queue with key 1234 in another process or thread.
LFQueue_create(1234, 64, 4096, true);
LFQueue *queue = LFQueue_open(1234); // Open a LFQueue.
char buf[64];
const char *data = "hello, world!";
LFQueue_push(queue, data, strlen(data) + 1, NULL);
LFQueue_pop(queue, buf, NULL);
printf("%s\n", buf);
LFQueue_close(queue);
LFQueue_destroy(1234);
}
Python
import pylfq
pylfq.create(1234, 64, 4096, True)
mq = pylfq.MQ(1234)
msg = b'hello, world!'
msg_out = bytes(64)
pylfq.push(msg)
pylfq.pop(msg_out)
print(msg_out)
pylfq.destroy(1234)
pylfq.create(1234, 64, 4096, True)
mq = pylfq.MQ(1234)
msg = b'hello, world!'
msg_out = bytes(64)
pylfq.push(msg)
pylfq.pop(msg_out)
print(msg_out)
pylfq.destroy(1234)
4. Build
C
mkdir build && cd build
cmake -DCMAKE_BUILD_TYPE=Release ..
make
cmake -DCMAKE_BUILD_TYPE=Release ..
make
Python
cd python/pylfq
python setup.py build_ext --inplace # or python setup.py install
python setup.py build_ext --inplace # or python setup.py install
LFQueue
1. Jie Shao
- Zhe Shi Yi Ge Duo Jin Cheng Jian Zhuang De Ji Yu Gong Xiang Nei Cun De Wu Suo Dui Lie
- Ta Ke Yi Ying Dui Jin Cheng Zai Ren He Yi Xing Dai Ma Beng Kui De Qing Kuang ,Bao Gua Zai queueNei Bu
- Huan Ying Ti Chu Geng Duo You Qu De Xiang Fa
2. Suan Fa
- There are two LFRings and an array with the same size.
- Zhe Ge Dui Lie Li You San Ge Jie Gou ,You Liang Ge LFRing,resource ringHe messageDu Bu Guan Li Shi Ji De Zi Yuan ,Ta Men Dang Zhong Bao Cun De Shi Zi Yuan De Xia Biao ,Ling Wai Yi Ge Jie Gou Shi Shi Ji Zi Yuan De Shu Zu ,Liang Ge LFRingZhong De Nei Cun Du He Shu Zu De Suo Yin Yi Yi Dui Ying .
- Xia Biao Wei -1Biao Shi Zhe Shi Yi Ge Wu Xiao De Suo Yin
- Dang Dui Lie Bei Chuang Jian Shi ,Dui Lie Jiang Chu Shi Hua Wei Xia Tu Suo Shi ,resource ringChu Shi Shi Shi Bei Tian Man De ,Er message ringChu Shi Shi Shi Kong De .
- Ru Dui Shi ,Xian Cong resource ringZhong Dan Chu Yi Ge Xia Biao ,Ru Guo Cheng Gong Huo De Yi Ge You Xiao De Xia Biao ,Ze Qu Shu Zu Zhong Zhao Dao Gai Xia Biao Dui Ying De Yuan Su ,Jiang Shu Ju Kao Bei Dao Zhe Ge Yuan Su Zhong ,Ran Hou Jiang Zhe Ge Xia Biao Ru Dui Dao message ringZhong ,Wan Cheng Yi Ci Ru Dui Cao Zuo . Ru Guo Cong resource ringHuo Qu Shi Bai ,Ze You Liang Chong Qing Kuang ,Yi Shi Kai Qi Liao Fu Xie Mo Shi ,Er Shi Fei Fu Xie Mo Shi . Zai Fu Xie Mo Shi Xia ,Dui Lie Zhong Zui Lao De Jie Dian Ying Gai Bei Fu Gai ,Suo Yi Hui Cong message ringZhong Dan Chu Yi Ge Xia Biao ,Dui Gai Xia Biao De Nei Rong Jin Xing Fu Xie ,Ran Hou Zhong Xin Jiang Xia Biao Ru Dui Dao message ringZhong Wan Cheng Fu Xie . Ruo Wei Fei Fu Xie Mo Shi ,Cong resource ringHuo Qu Shi Bai Ze Zhi Jie Fan Hui Yi Ge Ru Dui Shi Bai De Cuo Wu Zhi .
- Chu Dui Shi Tong Li ,Xian Cong message ringChu Dui Yi Ge Xia Biao ,Zai Ba Shu Zu Zhong Suo Yin Wei Gai Xia Biao De Yuan Su Li De Shu Ju Kao Bei Chu Lai ,Ran Hou Jiang Gai Xia Biao Ru Dui Dao resource ringZhong ,Gui Huan Zi Yuan .
- Suo You De LFRingCao Zuo Jun Shi You CASCao Zuo Shi Xian De .
- Wei Shi Yao Shuo Gai Dui Lie Neng Rong Ren Cheng Xu Zai Ren Yi Yi Xing Dai Ma Beng Kui Ni ,Qing Kan Yue Du Dai Ma .
Resouce ID Ring
---------------------------
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---------------------------
Message ID Ring
-------------------------------
| -1 | -1 | -1 | -1 | -1 | -1 | -1 |
-------------------------------
Real Resource
------------------------------------
| LFNode | LFNode | LFNode | ... |
------------------------------------