baidu / baidu/uid-generator

Concurrency Problem

Open
#105 0 comments 0 reactions 0 assignees View on GitHub
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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.