baidu / baidu/uid-generator

写入Ringbuffer时,生成的ID会跳过某些时间

Open
#96 1 comment 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

JDK VERSION:openjdk@17.0.11
uid-genertor version: Latest

```java
// com.baidu.fsg.uid.buffer.BufferPaddingExecutor#paddingBuffer()
public void paddingBuffer() {
LOGGER.info("Ready to padding buffer lastSecond:{}. {}", lastSecond.get(), ringBuffer);

// is still running
if (!running.compareAndSet(false, true)) {
LOGGER.info("Padding buffer is still running. {}", ringBuffer);
return;
}

// fill the rest slots until to catch the cursor
boolean isFullRingBuffer = false;
while (!isFullRingBuffer) {
List uidList = uidProvider.provide(lastSecond.incrementAndGet());
for (Long uid : uidList) {
isFullRingBuffer = !ringBuffer.put(uid);
if (isFullRingBuffer) {
break;
}
}
}

// not running now
running.compareAndSet(true, false);
LOGGER.info("End to padding buffer lastSecond:{}. {}", lastSecond.get(), ringBuffer);
}
```

```java
// com.baidu.fsg.uid.buffer.RingBuffer#paddingBuffer()
public synchronized boolean put(long uid) {
long currentTail = tail.get();
long currentCursor = cursor.get();
// 判读ringBuffer是否填满的逻辑在最开始
// tail catches the cursor, means that you can't put any cause of RingBuffer is full
long distance = currentTail - (currentCursor == START_POINT ? 0 : currentCursor);
if (distance == bufferSize - 1) {
rejectedPutHandler.rejectPutBuffer(this, uid);
return false;
}

// 1. pre-check whether the flag is CAN_PUT_FLAG
int nextTailIndex = calSlotIndex(currentTail + 1);
if (flags[nextTailIndex].get() != CAN_PUT_FLAG) {
rejectedPutHandler.rejectPutBuffer(this, uid);
return false;
}

// 2. put UID in the next slot
// 3. update next slot' flag to CAN_TAKE_FLAG
// 4. publish tail with sequence increase by one
slots[nextTailIndex] = uid;
flags[nextTailIndex].set(CAN_TAKE_FLAG);
tail.incrementAndGet();

// The atomicity of operations above, guarantees by 'synchronized'. In another word,
// the take operation can't consume the UID we just put, until the tail is published(tail.incrementAndGet())
return true;
}
```
问题:当填入ID时,预先生成ID,判断ringBuffer是否填满的逻辑在`ringBuffer.put()`最开始。导致总有lastSecond生成了ID,但因为ringBuffer已满,而被废弃。
当`padding-factor = 50`时 每`boost-power + 1` 个 lastSecond,就有一个被废弃
解决:通过配置padding-factor != 50,使每次生成的UID序列不能完整的加入ringbuffer就出发了ringBuffer已满已满的逻辑
优化:修改put()方法, 当填入一个后,再次判断是否填满

```java
// com.baidu.fsg.uid.buffer.RingBuffer#paddingBuffer()
public synchronized boolean put(long uid) {
long currentTail = tail.get();
long currentCursor = cursor.get();
// 判读ringBuffer是否填满的逻辑在最开始
// tail catches the cursor, means that you can't put any cause of RingBuffer is full
long distance = currentTail - (currentCursor == START_POINT ? 0 : currentCursor);
if (distance == bufferSize - 1) {
rejectedPutHandler.rejectPutBuffer(this, uid);
return false;
}

// 1. pre-check whether the flag is CAN_PUT_FLAG
int nextTailIndex = calSlotIndex(currentTail + 1);
if (flags[nextTailIndex].get() != CAN_PUT_FLAG) {
rejectedPutHandler.rejectPutBuffer(this, uid);
return false;
}

// 2. put UID in the next slot
// 3. update next slot' flag to CAN_TAKE_FLAG
// 4. publish tail with sequence increase by one
slots[nextTailIndex] = uid;
flags[nextTailIndex].set(CAN_TAKE_FLAG);
// ++++++++++++++
// 判断buffer是否在加入当前ID之后就满了。
boolean result = distance != bufferSize - 2 ;
tail.incrementAndGet();

// The atomicity of operations above, guarantees by 'synchronized'. In another word,
// the take operation can't consume the UID we just put, until the tail is published(tail.incrementAndGet())
return result;
}
```

Contributor guide

No contributing guide indexed for this repository

Research direction

Start with com.baidu.fsg.uid.buffer.BufferPaddingExecutor#paddingBuffer() and com.baidu.fsg.uid.buffer.RingBuffer#put(), tracing how lastSecond.incrementAndGet() interacts with the full-buffer check. Reproduce the behavior with padding-factor=50, then verify that filling the final available slot does not discard a generated ID or skip a lastSecond sequence.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
backend
Issue type
Bug
Difficulty
3/5
Estimated time
1-2 days
Activity status
Stale
Clarity
Clearly specified
Newbie friendliness
38/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.