带界缓冲区的parEvalMap组合子存在性及实现方案问询

需求场景 #

需要一个parEvalMap的变体，核心规则是缓冲区未满时持续推进流处理，同时保证输出结果严格有序。以并行度4、缓冲区大小6的场景为例，处理流[1,2,3,4,5,6,7,8...]的流程如下：

• 并行启动项1、2、3、4的处理；
• 项1处理完成后直接输出，缓冲区为空，启动项5的处理；
• 项3处理完成后，结果存入缓冲区，启动项6的处理；
• 项5处理完成后，结果存入缓冲区，启动项7的处理；
• 项2处理完成后，依次输出f(2)、f(3)，缓冲区剩余f(5)，启动项8的处理；
• 缓冲区达到上限时，暂停拉取新的流项，直到首个在处理项完成或缓冲区有空闲空间。

现有方案的问题 #

处理流时存在部分项耗时远超平均的情况：

• parEvalMap：受并行度限制，一旦出现慢请求，即便其余N-1个请求已完成，也无法启动新任务，只能等待慢请求结束，整体吞吐量骤降；
• parEvalMapUnordered：能维持最大并行度，但输出结果无序，不符合有序需求。

目标是兼顾最大并行处理能力与有序输出：将提前完成的后续项结果暂存到缓冲区，保持并行度跑满，等慢请求完成后再按顺序输出缓冲区中的结果。

现成组合子现状 #

目前主流函数式流处理库（如Cats Effect、ZIO）中没有直接提供这种带界缓冲区的有序并行映射组合子，需要基于现有原语自行实现。

实现思路 #

核心设计逻辑 #

1. 并行任务调度：依托库内的并行执行器维持设定的并行度，持续从输入流拉取项并启动处理，直到缓冲区满或输入流耗尽；
2. 有序结果缓存：维护一个按输入顺序索引排序的缓冲区，存储已完成但未到输出时机的结果；
3. 批量输出触发：每当任务完成时，检查当前最早待输出的项是否已完成：
   • 若是，直接输出该结果，接着依次检查缓冲区中后续连续完成的项，批量输出；
   • 若否，将结果存入缓冲区；
4. 缓冲区限流：当缓冲区达到设定上限时，暂停拉取新的流项，直到缓冲区有空间释放（即有结果被输出）。

示例实现步骤（以Cats Effect为例） #

• 用Ref维护三个状态：当前待输出的最小索引、按索引映射的结果缓冲区（如Map[Long, A]）、已提交的任务计数；
• 用两个Semaphore分别控制并行度（限制同时运行的任务数）和缓冲区容量（限制缓存的结果数）；
• 遍历输入流时，先获取缓冲区许可（确保有缓存空间），再获取并行度许可，随后启动异步处理任务；
• 任务完成后，将结果存入缓冲区，然后尝试触发批量输出：从当前待输出索引开始，检查缓冲区中是否存在连续的结果，存在则依次输出，并更新待输出索引，同时释放对应的缓冲区许可；
• 输入流遍历完成后，等待缓冲区中剩余结果全部输出完毕。

内容的提问来源于stack exchange，提问作者Ákos Vandra-Meyer