# concurrent_queue

**Repository Path**: kangdan0404/concurrent_queue

## Basic Information

- **Project Name**: concurrent_queue
- **Description**: 设计一个并发等待队列
- **Primary Language**: Go
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2022-11-18
- **Last Updated**: 2022-12-05

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 目标 
实现一个基于内存的并发安全队列
提高你们的并发编程能力。p6 +
## 讨论
1. 并发安全队列使用场景：生产者-消费者模型，延时队列
	a. channel，多个协程从 channel 取数据
		i. 考虑协程拿不到数据要退出
		ii. 容量估计
	b. AQS：跟线程池一起用，Java
		i. 容量估计：峰值的 50%
		ii. 拒绝策略：通知拒绝了新数据
	c. Redis 的 List 来实现优先级队列，左边取，右边插入数据，高优先级的就插入左边
		i. sorted set 来做延迟队列，将value值作为时间，按时间排序
		ii. 用延迟队列来解决打款（异步场景），30 分钟没支付自动关闭订单
		iii. 可以利用 Redis 来控制 TPS
		iv. Redis 服务不可用怎么办？

## 场景分析
（我要设计一个并发队列，我要考虑什么因素）
    1. 要不要考虑阻塞调用者的问题：
        a. 如果队列没有元素，应该阻塞拿数据的人
        b. 如果队列满了，是不是要考虑阻塞放数据的人
        c. 如果阻塞住了，要不要考虑只能阻塞一段时间，然后就超时
    2. 扩容：如果队列满了，或者容量快不够了，要不要扩容
        a. 考虑大容量对 GC 的影响（对内存的影响）
    3. 元素优先级问题
    4. 线程安全问题：
        a. 有没有可能导致死锁
    5. 持久化的问题：应用关闭的时候，持久化数据，重启就恢复
    6. 支持订阅模式
    7. 公平性问题：是不是先到先得（尤其是阻塞的情况下）
    8. 考虑性能问题

## 功能需求
1. 用户可以控制最大容量（或者无限容量）：
	a. 防止占用很多内存，影响 GC
	b. 要不要支持扩容的机制。比如说最大容量是 10000，初始容量是 100，后续会扩容或者缩容
2. 控制住阻塞：
	a. 没有数据阻塞拿数据的人，并且要控制住超时，比如说最多阻塞 1s
	b. 队列满了，阻塞住放数据的人，并且控制出超时
	c. 如果你考虑扩容缩容，你怎么阻塞？

## 非功能需求
1. 性能问题
2. 公平性, channel和mutx都不是公平的，所以mutex里有一个饥饿模式！


## 知识点
Go 基础差的同学要去复习一下 context.Context 和 sync 包的 API
1. sync.Cond
if 改 for

2. 进 select-case 之前，一定要释放锁，不然就会死锁（面试例子）
3. 使用 context.Context 来控制超时的理由：
    1). context 天然支持，而且能够做到级联控制
    2). context 本身承载链路元数据，所以 context 必不可少

# 练习
支持一个类似于 sync.Cond.Wait(timeout) 的调用。
github 我找过，谷歌我也找过，不要指望太多。

// 被唤醒的信号
WaitChan() chan struct
// 返回 error 就是超时，没有 error 就是被唤醒
Wait(timeout time.Duration) error