线偶的IT笔记

常见的限流算法

线偶发布于 2024-04-12 收录于随笔

固定窗口算法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
type FixedWindowRateLimiter struct {
	// 固定窗口大小, 单位ms
	windowInterval time.Duration
	// 限制
	limit int
	// 窗口开始时间
	prevTime time.Time
	// 当前限制
	curLimit int
}

func (s *FixedWindowRateLimiter) acquire() (bool, error) {
	// 不在一个时间窗口，重置
	if time.Until(s.prevTime) > s.windowInterval {
		s.curLimit = 0
	}
	s.curLimit++
	s.prevTime = time.Now()
	return s.curLimit < s.limit, nil
}

令牌桶算法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
type TokenBucketRateLimiter struct {
	// 桶大小
	bucketSize int
	// 速率，单位ms
	rate int
	// 剩余令牌数
	remainTokens int
	// 时间
	prevTime time.Time
}

func (t *TokenBucketRateLimiter) acquire() (bool, error) {
	// 计算新的令牌数
	newTokens := int(time.Until(t.prevTime).Milliseconds()) * t.rate
	t.remainTokens += newTokens
	if t.remainTokens >= t.bucketSize {
		t.remainTokens = t.bucketSize
	}
	t.remainTokens--
	t.prevTime = time.Now()
	return t.remainTokens > 0, nil
}

漏桶算法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
type LeakyBucketRateLimiter struct {
	// 速率，单位ms
	rate int
	// 剩余令牌数
	remainTokens int
	// 时间
	prevTime time.Time
}

func (l *LeakyBucketRateLimiter) acquire() (bool, error) {
	// 不是同一毫秒，重置令牌数
	if time.Now().UnixMilli() != l.prevTime.UnixMilli() {
		l.remainTokens = l.rate
	}
	l.remainTokens--
	l.prevTime = time.Now()
	return l.remainTokens > 0, nil
}

示例代码

demo-ratelimiter

简单实现 Gossip 协议

线偶发布于 2024-04-12 收录于随笔

gossip 协议是为实现最终一致性提出的。

实现思路

每个节点都有基本属性，如 id, addr, port。
每个节点都有成员列表 members，存储一部分数据 data。
通过定时向随机节点发送请求，同步成员列表给随机节点，这样就能达到成员列表最终一致性。
客户端访问数据，先根据 key 来计算 hash 值，对成员列表取余，确定是哪个节点上，要么返回数据要么转发请求。

04 RedissonSortedSet

线偶发布于 2024-04-11 收录于源码分析 Redisson 系列

redisson 基于 org.redisson:redisson-spring-data-27:3.27.2 版本

在 java 中，操作 redis 一般都会选择 redisson 框架, 我们需要了解常用功能的实现原理, 这次来介绍 RedissonSortedSet。

使用方式

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
@Test
void testOrderedSet() {
    RSortedSet<String> set = redissonClient.getSortedSet("set");
    set.clear();
    set.add("3");
    set.add("2");
    set.add("1");
    for (String s : set.readAll()) {
        System.out.println(s);
    }
}

RedissonSortedSet 是通过 list 数据结构来实现的。但如果 value 是 string 类型的，可以使用 RedissonLexSortedSet 来优化操作。

05 RedissonPriorityQueue

线偶发布于 2024-04-11 收录于源码分析 Redisson 系列

redisson 基于 org.redisson:redisson-spring-data-27:3.27.2 版本

在 java 中，操作 redis 一般都会选择 redisson 框架, 我们需要了解常用功能的实现原理, 这次来介绍 RedissonPriorityQueue。

使用方式

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
@Test
void testPriorityQueue() {
    RPriorityQueue<String> queue = redissonClient.getPriorityQueue("queue");
    queue.clear();
    queue.add("3");
    queue.add("2");
    queue.add("1");
    for (String s : queue.readAll()) {
        System.out.println(s);
    }
}

RedissonPriorityQueue 是通过 list 数据结构来实现的。

03 RedissonMultiLock

线偶发布于 2024-04-10 收录于源码分析 Redisson 系列

redisson 基于 org.redisson:redisson-spring-data-27:3.27.2 版本

在 java 中，操作 redis 一般都会选择 redisson 框架, 我们需要了解常用功能的实现原理, 这次来介绍 RedissonMultiLock。

使用方式

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
@Test
void testMultiLock() {
    RLock lock1 = redissonClient.getLock("lock1");
    RLock lock2 = redissonClient.getLock("lock2");
    RLock lock = redissonClient.getMultiLock(lock1, lock2);
    try {
        lock.lock();
        ThreadUtil.sleep(30, TimeUnit.SECONDS);
        System.out.println("xxx");
    } finally {
        lock.unlock();
    }
} 

在实际使用过程中，可能一次性获取多个锁，那么你应该使用 RedissonMultiLock 来简化你的操作。

02 RedissonSpinLock

线偶发布于 2024-04-09 收录于源码分析 Redisson 系列

redisson 基于 org.redisson:redisson-spring-data-27:3.27.2 版本

在 java 中，操作 redis 一般都会选择 redisson 框架, 我们需要了解常用功能的实现原理, 这次来介绍 RedissonSpinLock。

使用方式

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
@Test
void testSpinLock() {
    RLock lock = redissonClient.getSpinLock("lock");
    try {
        lock.lock();
        ThreadUtil.sleep(30, TimeUnit.SECONDS);
        System.out.println("xxx");
    } finally {
        lock.unlock();
    }
}

lock

源码位置: org.redisson.RedissonSpinLock#lock