Concurrency Problem
- Dominant language
- Java
- Stars
- 5.6k
- Forks
- 1.5k
- PR merge metrics
- No merged PRs in 30d
Description
There seems to be a concurrency problem in RingBuffer.take():
public long take() {
// spin get next available cursor
long currentCursor = cursor.get(); // Point A
long nextCursor = cursor.updateAndGet(old -> old == tail.get() ? old : old + 1); // Point B
// check for safety consideration, it never occurs
Assert.isTrue(nextCursor >= currentCursor, "Curosr can't move back");
// trigger padding in an async-mode if reach the threshold
long currentTail = tail.get();
if (currentTail - nextCursor < paddingThreshold) {
LOGGER.info("Reach the padding threshold:{}. tail:{}, cursor:{}, rest:{}", paddingThreshold, currentTail,
nextCursor, currentTail - nextCursor);
bufferPaddingExecutor.asyncPadding();
}
// cursor catch the tail, means that there is no more available UID to take
if (nextCursor == currentCursor) { // Point C
rejectedTakeHandler.rejectTakeBuffer(this);
}
// 1. check next slot flag is CAN_TAKE_FLAG
int nextCursorIndex = calSlotIndex(nextCursor);
Assert.isTrue(flags[nextCursorIndex].get() == CAN_TAKE_FLAG, "Curosr not in can take status");
// 2. get UID from next slot
// 3. set next slot flag as CAN_PUT_FLAG.
long uid = slots[nextCursorIndex]; // Point D
flags[nextCursorIndex].set(CAN_PUT_FLAG);
// Note that: Step 2,3 can not swap. If we set flag before get value of slot, the producer may overwrite the
// slot with a new UID, and this may cause the consumer take the UID twice after walk a round the ring
return uid;
}
0. cursor=N, tail=N+1
1. two threads (X,Y) calls take() at almost same time, and cursor.get() (at Point A) returns N for both of them
2. Thread X calls cursor.updateAndGet(old -> old == tail.get() ? old : old + 1); at Point B, and get N+1. now cursor=N+1, tail=N+1
3. Thread Y calls cursor.updateAndGet(old -> old == tail.get() ? old : old + 1); at Point B, and get N+1. not cursor=N+1, tail=N+1 (cursor not change, since it equals to tail)
4. Thread X/Y reaches Point C, and nextCursor == currentCursor is false for both of them (nextCursor=N+1, currentCursor=N)
5. Thread X/Y get uid=slots[N+1] at Point D
6. Thread X/Y returns duplicated uid
I let codex to analyze and here is the report
[concurrency-problem.md](https://github.com/user-attachments/files/26955883/concurrency-problem.md)
Contributor guide
No contributing guide indexed for this repository
Research direction
Read the linked concurrency-problem.md report, then inspect RingBuffer.take() around Points A-D. Reproduce the two-thread interleaving described in the issue and trace cursor and slot-flag ownership. Done means concurrent take() calls cannot return the same UID while preserving the stated slot-read and flag-update ordering.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java
- Domain
- distributed-systems
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 55/100