Ring Buffer 如何实现

Ring Buffer 如何实现

Ring Buffer支持的消息传递处理器的实现，它使用异步事件循环实现发布订阅，所以常见于生产者消费者模式。
需要关注的重点，可以按消费者Comsuner，消息存储Broker，生产者Producer三个方面去考虑（这也是MQ的架构）。
RingBuffer 支持的消息传递处理器的实现，它使用异步事件循环实现发布订阅

下面以 reactor.core.publisher.RingBuffer 的实现说明

存储消息

• Ring Buffer 底层是数组 Object[] ，具体类型是Slot[]，Slot 将具体消息封装起来
• Ring Buffer 取出消息，是使用 UNSAFE.getObject 从Object[] 取出
• 使用 Sequence[] 对应多个消费者（辅助类RingBufferProducer ） ，每添加消费者时添加Sequence，用于消费时记录已消费的消息下标，Sequence的具体实现有 Unsafe 和 AtomicLongFieldUpdater 两种，其中AtomicLongFieldUpdater是CAS类
• 消费者辅助类RingBuffer.Reader 记录当前消费者相关信息，已消费的消息下标Sequence 和 RingBufferProducer
• Ring Buffer 存储消息，将消息保存到RingBuffer时会更新 nextValue:long ，作为生产者的进度，然后存储到对应nextValue下标的Object[] 数组中

发送消息

• 发送消息，先保存到 RingBuffer的数组中，再 publish 消息给消费者
• 使用 RingBufferProducer 记录每个生产者下的消费者进度
• 此时使用 Condition.signalAll 唤醒 await 的消费者线程（Condition 的底层是AQS的LockSupport，按线程对象锁）

消费消息

• 提交消费者时，会将业务封装消费者线程TopicInner，提交到线程池中
• 设置初始的消费下标，按最近的消费进度设置，如果时首次加载消费者则从头消费
• 在消费者线程TopicInner 内，先使用 subscriber.onSubscribe 初始化，然后在死循环内不断消息消费
• 待消费的消息，按数组下标取，以RingBuffer的availableSequence为最大值，以nextSequence 为最小值，调用业务逻辑消费消息

其中涉及具体类：TopicProcessor、SingleProducerSequencer、UnsafeRingBuffer、CoreSubscriber

下面是关键代码。

数据存储

数据结构 RingBuffer 的关键变量：使用Object[] 存储具体的消息，bufferSize作为最大容量

private final   Object[]           entries;
protected final int                bufferSize;
protected final RingBufferProducer sequenceProducer;

// 初始化
this.bufferSize = sequenceProducer.getBufferSize();
this.entries   = new Object[sequenceProducer.getBufferSize() + 2 * BUFFER_PAD];
1
2
3
4
5
6
7

生产者辅助类 RingBufferProducer 的关键变量：使用Sequence[]记录每个消费者，AtomicReferenceFieldUpdater用于并发更新

static final AtomicReferenceFieldUpdater<RingBufferProducer, RingBuffer.Sequence[]>
    SEQUENCE_UPDATER = AtomicReferenceFieldUpdater.newUpdater(RingBufferProducer.class, RingBuffer.Sequence[].class, "gatingSequences");

final WaitStrategy waitStrategy;
final    RingBuffer.Sequence   cursor          = RingBuffer.newSequence(RingBuffer.INITIAL_CURSOR_VALUE);
volatile RingBuffer.Sequence[] gatingSequences = new RingBuffer.Sequence[0];
1
2
3
4
5
6

初始化生成数据的方法，从 reactor.core.publisher.TopicProcessor 传入到 reactor.core.publisher.RingBuffer

() -> {
    Slot<E> signal = new Slot<>();
    if (signalSupplier != null) {
        signal.value = signalSupplier.get();
    }
    return signal;
}
1
2
3
4
5
6
7

待消费的消息数量，根据生产者和消费者的之间的下标计算，可以判断消息积压

public long getPending() {
    long nextValue = this.nextValue;

    long consumed = RingBuffer.getMinimumSequence(gatingSequences, nextValue);
    long produced = nextValue;
    return produced - consumed;
}
1
2
3
4
5
6
7

发送消息

发送消息关键有两步，保存到RingBuffer，以及唤醒生产者对应的消费者线程去消费消息

发送消息，比如 io.lettuce.core.event.EventBus.publish 就会调用 TopicProcessor.onNext

相关方法如下，会将消息按seqId保存到对应的数组元素Slot

final public void onNext(IN o) {
    Objects.requireNonNull(o, "onNext");
    final long seqId = ringBuffer.next();
    final Slot<IN> signal = ringBuffer.get(seqId);
    signal.value = o;
    ringBuffer.publish(seqId);
}
1
2
3
4
5
6
7

获取RingBuffer中可用数据的下标，调用方向是 RingBuffer.next -> SingleProducerSequencer.next

long next() {
    return next(1);
}


@Override
long next(int n) {
    long nextValue = this.nextValue;

    long nextSequence = nextValue + n;
    long wrapPoint = nextSequence - bufferSize;
    long cachedGatingSequence = this.cachedValue;

    if (wrapPoint > cachedGatingSequence || cachedGatingSequence > nextValue)
    {
        long minSequence;
        while (wrapPoint > (minSequence = RingBuffer.getMinimumSequence(gatingSequences, nextValue)))
        {
            if(spinObserver != null) {
                spinObserver.run();
            }
            LockSupport.parkNanos(1L); // TODO: Use waitStrategy to spin?
        }

        this.cachedValue = minSequence;
    }

    this.nextValue = nextSequence;

    return nextSequence;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

发送消息，调用方式实际是调用RingBufferProducer， RingBuffer.publish -> SingleProducerSequencer.publish

void publish(long sequence) {
    cursor.set(sequence);
    waitStrategy.signalAllWhenBlocking();
}
1
2
3
4

线程的通知，使用的是waitStrategy， 默认实现 LiteBlocking 如下，封装了Lock

final static class LiteBlocking extends WaitStrategy {

    private final Lock          lock                     = new ReentrantLock();
    private final Condition     processorNotifyCondition = lock.newCondition();
    private final AtomicBoolean signalNeeded             = new AtomicBoolean(false);

    @Override
    public void signalAllWhenBlocking()
    {
        if (signalNeeded.getAndSet(false))
        {
            lock.lock();
            try
            {
                processorNotifyCondition.signalAll();
            }
            finally
            {
                lock.unlock();
            }
        }
    }

    @SuppressWarnings("UnusedAssignment") //for availableSequence
    @Override
    public long waitFor(long sequence, LongSupplier cursorSequence, Runnable barrier)
        throws InterruptedException
    {
        long availableSequence;
        if ((availableSequence = cursorSequence.getAsLong()) < sequence)
        {
            lock.lock();

            try
            {
                do
                {
                    signalNeeded.getAndSet(true);

                    if ((availableSequence = cursorSequence.getAsLong()) >= sequence)
                    {
                        break;
                    }

                    barrier.run();
                    processorNotifyCondition.await();
                }
                while ((availableSequence = cursorSequence.getAsLong()) < sequence);
            }
            finally
            {
                lock.unlock();
            }
        }

        while ((availableSequence = cursorSequence.getAsLong()) < sequence)
        {
            barrier.run();
        }

        return availableSequence;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

消费消息

定义了CoreSubscriber，业务逻辑需要实现CoreSubscriber，创建消费者

具体的消息消费

创建消费者线程

public void subscribe(final CoreSubscriber<? super E> actual) {
    Objects.requireNonNull(actual, "subscribe");

    if (!alive()) {
        coldSource(ringBuffer, null, error, minimum).subscribe(actual);
        return;
    }

    //create a unique eventProcessor for this subscriber
    final RingBuffer.Sequence pendingRequest = RingBuffer.newSequence(0);
    final TopicInner<E> signalProcessor =
        new TopicInner<>(this, pendingRequest, actual);

    //bind eventProcessor sequence to observe the ringBuffer

    //if only active subscriber, replay missed data
    if (incrementSubscribers()) {

        signalProcessor.sequence.set(minimum.getAsLong());
        ringBuffer.addGatingSequence(signalProcessor.sequence);
        //set eventProcessor sequence to minimum index (replay)
    }
    else {
        //otherwise only listen to new data
        //set eventProcessor sequence to ringbuffer index
        signalProcessor.sequence.set(ringBuffer.getCursor());
        ringBuffer.addGatingSequence(signalProcessor.sequence);


    }

    try {
        //start the subscriber thread
        executor.execute(signalProcessor);

    }
    catch (Throwable t) {
        ringBuffer.removeGatingSequence(signalProcessor.sequence);
        decrementSubscribers();
        if (!alive() && RejectedExecutionException.class.isAssignableFrom(t.getClass())){
            coldSource(ringBuffer, t, error, minimum).subscribe(actual);
        }
        else{
            Operators.error(actual, t);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

消费者线程，具体逻辑 TopicInner.run

public void run() {
    try {
        Thread.currentThread()
            .setContextClassLoader(processor.contextClassLoader);
        subscriber.onSubscribe(this);

        if (!EventLoopProcessor
            .waitRequestOrTerminalEvent(pendingRequest, processor.barrier, running, sequence, waiter)) {
            if(!running.get()){
                return;
            }
            if(processor.terminated == SHUTDOWN) {
                if (processor.ringBuffer.getAsLong() == -1L) {
                    if (processor.error != null) {
                        subscriber.onError(processor.error);
                        return;
                    }
                    subscriber.onComplete();
                    return;
                }
            }
            else if (processor.terminated == FORCED_SHUTDOWN) {
                return;
            }
        }

        Slot<T> event;
        long nextSequence = sequence.getAsLong() + 1L;
        final boolean unbounded = pendingRequest.getAsLong() == Long.MAX_VALUE;

        while (true) {
            try {

                final long availableSequence = processor.barrier.waitFor(nextSequence, waiter);
                while (nextSequence <= availableSequence) {
                    event = processor.ringBuffer.get(nextSequence);

                    //if bounded and out of capacity
                    while (!unbounded && getAndSub(pendingRequest, 1L) ==
                           0) {
                        //Todo Use WaitStrategy?
                        if(!running.get() || processor.isTerminated()){
                            WaitStrategy.alert();
                        }
                        LockSupport.parkNanos(1L);
                    }

                    //It's an unbounded subscriber or there is enough capacity to process the signal
                    subscriber.onNext(event.value);
                    nextSequence++;

                }
                sequence.set(availableSequence);

                if (Operators.emptySubscription() !=
                    processor.upstreamSubscription) {
                    processor.readWait.signalAllWhenBlocking();
                }
            }
            catch (Throwable ex) {
                if(WaitStrategy.isAlert(ex) || Exceptions.isCancel(ex)) {

                    if (!running.get()) {
                        break;
                    }
                    else {
                        if (processor.terminated == SHUTDOWN) {
                            if (processor.error != null) {
                                subscriber.onError(processor.error);
                                break;
                            }
                            if (nextSequence > processor.ringBuffer.getAsLong()) {
                                subscriber.onComplete();
                                break;
                            }

                            LockSupport.parkNanos(1L);
                        }
                        else if (processor.terminated == FORCED_SHUTDOWN) {
                            break;
                        }
                        processor.barrier.clearAlert();
                    }
                }
                else {
                    throw Exceptions.propagate(ex);
                }
            }
        }
    }
    finally {
        processor.ringBuffer.removeGatingSequence(sequence);
        processor.decrementSubscribers();
        running.set(false);
        processor.readWait.signalAllWhenBlocking();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

查询消息 ，使用 UNSAFE.getObject 获取

E get(long sequence)
{
    return elementAt(sequence);
}

final E elementAt(long sequence)
{
    return (E) UNSAFE.getObject(entries, REF_ARRAY_BASE + ((sequence & indexMask) << REF_ELEMENT_SHIFT));
}
1
2
3
4
5
6
7
8
9