线程安全令牌桶算法

Question

我有以下代码

public class TokenBucketRateLimiter implements RateLimiter {
    // Maximum number of tokens that can be accumulated in the bucket.
    private final long threshold;
    // Time unit for the token refill (in milliseconds).
    private final long windowUnit = 1000;
    // Current number of available tokens.
    private final AtomicLong tokens = new AtomicLong(0);
    // Timestamp of the last refill operation.
    private volatile long lastRefillTimestamp = System.currentTimeMillis();

    /**
     * Constructs a TokenBucketRateLimiter with the specified threshold.
     *
     * @param threshold the maximum number of tokens that can be accumulated.
     */
    public TokenBucketRateLimiter(long threshold) {
        this.threshold = threshold;
        // Initialize the bucket to full capacity.
        this.tokens.set(threshold);
    }

    /**
     * Attempts to acquire a token from the bucket.
     *
     * @return true if a token was successfully acquired; false otherwise.
     */
    @Override
    public boolean tryAcquire() {
        long currentTime = System.currentTimeMillis();
        // Calculate the number of tokens to add based on elapsed time since the last refill.
        long tokensToAdd = ((currentTime - lastRefillTimestamp) / windowUnit) * threshold;

        // Refill the bucket with the calculated number of tokens.
        if (tokensToAdd > 0) {
            // Ensure the bucket does not exceed its capacity.
            tokens.set(Math.min(threshold, tokens.addAndGet(tokensToAdd)));
            // Update the refill timestamp.
            lastRefillTimestamp = currentTime;
        }

        // Attempt to acquire a token.
        if (tokens.get() > 0) {
            // Decrement the token count and grant access.
            tokens.decrementAndGet();
            return true;
        }

        // Token bucket is empty; deny access.
        return false;
    }
}

这是一个简单的单节点令牌桶实现。当我检查下面的代码时，这不是真的吗

        // Attempt to acquire a token.
        if (tokens.get() > 0) {
            // Decrement the token count and grant access.
            tokens.decrementAndGet();
            return true;
        }

如果代币数量为

1

，

tokens.get()

将返回

1

。两个线程仍然可以通过此检查，并且可以在另一个线程之后递减它，使

tokens

为负并允许第二个调用通过，尽管它不应该被允许？

这里使用同步是唯一的方法吗？或者说

Reentrant lock

api？

Answer 1

你是对的，存在竞争条件的危险，并且synchronized或ReentrantLock可以修复它。 然而，你可以做类似的事情

long prevTokens = tokens.getAndUpdate(t -> Math.max(t-1, 0));
if (prevTokens > 0) { ... }