Ktor DefaultPool的pop、push实现原理及简化可能性咨询

这段代码是Ktor对象池实现里的无锁并发栈核心逻辑，用来管理池中空闲对象的索引，核心设计是把版本号和栈顶索引打包到同一个64位volatile变量top中，既解决了无锁场景的ABA问题，又保证了一次CAS就能完成原子更新。其中next是预分配的数组，每个位置存储对应索引的下一个栈元素索引，用来构造栈的链式结构，返回值0是特殊标记，代表栈为空、没有可用索引。

pushTop 操作逻辑 #

pushTop的作用是把一个空闲对象的索引压入栈顶：

private fun pushTop(index: Int) {
    require(index > 0) { "index should be positive" }
    while (true) { // lock-free loop on top
        val top = this.top // volatile read
        val topVersion = (top shr 32 and 0xffffffffL) + 1L 
        val topIndex = (top and 0xffffffffL).toInt() 
        val newTop = topVersion shl 32 or index.toLong() 
        next[index] = topIndex
        if (Top.compareAndSet(this, top, newTop)) return
    }
}

执行流程：

• 首先校验传入的索引必须大于0，0是空栈标记不能作为有效索引
• 进入无锁重试循环，直到操作成功
• 读取最新的top值（volatile读保证可见性），把64位的top拆分为两部分：高32位是当前栈的版本号，低32位是当前栈顶的索引
• 版本号加1得到新版本号，构造新的top值：高32位存新版本号，低32位存当前要压入的新索引
• 把新索引对应的next值指向原来的栈顶索引，完成新节点的链式挂载
• 用CAS操作把原来的top替换为新的top，如果CAS成功说明没有其他线程并发修改栈顶，操作结束；如果CAS失败说明其他线程已经改了栈顶，回到循环开头重试。

popTop 操作逻辑 #

popTop的作用是从栈顶弹出一个空闲对象的索引：

private fun popTop(): Int {
    // lock-free loop on top
    while (true) {
        // volatile read
        val top = this.top
        if (top == 0L) return 0
        val newVersion = (top shr 32 and 0xffffffffL) + 1L
        val topIndex = (top and 0xffffffffL).toInt()
        if (topIndex == 0) return 0
        val next = next[topIndex]
        val newTop = newVersion shl 32 or next.toLong()
        if (Top.compareAndSet(this, top, newTop)) return topIndex
    }
}

执行流程：

• 进入无锁重试循环，直到操作成功
• 读取最新的top值，如果top为0说明栈为空，直接返回0标记
• 拆分top得到当前版本号和栈顶索引，版本号加1得到新版本号
• 如果栈顶索引为0也返回空标记
• 读取当前栈顶索引对应的next值，也就是弹出之后新的栈顶索引
• 构造新的top值：高32位存新版本号，低32位存新的栈顶索引
• CAS替换top，成功就返回弹出的栈顶索引，失败说明有并发修改，回到循环开头重试。

分两种场景看：

• 如果不需要无锁高并发的特性，完全可以用更简单的实现：比如用普通栈加同步锁，或者直接用JDK自带的并发集合，代码量少、易读性高，并发不高的场景性能差距也很小，示例实现如下：

// 带锁的简易实现，适用于并发要求不高的场景
private val idleStack = ArrayDeque<Int>()
private val lock = Any()

private fun pushTop(index: Int) {
    require(index > 0)
    synchronized(lock) {
        idleStack.addFirst(index)
    }
}

private fun popTop(): Int {
    synchronized(lock) {
        return if (idleStack.isEmpty()) 0 else idleStack.removeFirst()
    }
}

• 如果要求和原实现一致的无锁高并发、规避ABA问题的特性，原实现已经是比较精简的工业级实现了：无锁算法本身就需要处理并发冲突、版本校验、失败重试这些逻辑，原实现把版本号和索引打包到同一个变量里，只用一次CAS就能完成原子更新，反而比分开存两个变量做两次CAS的实现更高效，没有大幅简化的空间。

内容的提问来源于stack exchange，提问作者sheu