缓存流水线

缓存滑动窗口(理想情况)

Stage1
Stage1
0-N
0-N
N-2N
N-2N
2N-3N
2N-3N
3N-4N
3N-4N
4N-5N
4N-5N
5N-6N
5N-6N
文件写入线程滑窗
文件写入线程滑窗
缓存写入线程滑窗
缓存写入线程滑窗
磁盘1
磁盘1
磁盘2
磁盘2
5N-6N
5N-6N
6N-7N
6N-7N
Stage2
Stage2
0-N
0-N
N-2N
N-2N
2N-3N
2N-3N
3N-4N
3N-4N
4N-5N
4N-5N
5N-6N
5N-6N
文件写入线程滑窗
文件写入线程滑窗
缓存写入线程滑窗
缓存写入线程滑窗
磁盘1
磁盘1
磁盘2
磁盘2
5N-6N
5N-6N
6N-7N
6N-7N
Stage N (环形滑窗)
Stage N (环形滑窗)
0-N
0-N
N-2N
N-2N
2N-3N
2N-3N
3N-4N
3N-4N
4N-5N
4N-5N
5N-6N
5N-6N
文件写入线程滑窗
文件写入线程滑窗
缓存写入线程滑窗
缓存写入线程滑窗
磁盘1
磁盘1
磁盘2
磁盘2
5N-6N
5N-6N
6N-7N
6N-7N
Text is not SVG - cannot display

差分多路缓存滑动窗口(优化方案,完全独立并行)

理想情况下,原则上应该是多个子窗口同步(构成一组大滑窗),然后滑动向后。实践中,由于不同磁盘速度不稳定,这样会导致强制同步,导致性能浪费。因此本方案使用改良的差分滑动窗口算法设计,确保速度在极限下无限接近多个磁盘的速度和,尽可能避免强制同步导致速度损失。

Stage1
Stage1
0-N
0-N
N-2N
N-2N
2N-3N
2N-3N
3N-4N
3N-4N
4N-5N
4N-5N
5N-6N
5N-6N
文件写入线程滑窗
文件写入线程滑窗
缓存写入线程滑窗a1
缓存写入线程滑窗a1
500MB/s
500MB/s
磁盘1
磁盘1
1GB/s
1GB/s
磁盘2
磁盘2
5N-6N
5N-6N
6N-7N
6N-7N
缓存写入线程滑窗b1
缓存写入线程滑窗b1
缓存写入线程滑窗b2
缓存写入线程滑窗b2
缓存写入线程滑窗b3
缓存写入线程滑窗b3
差分滑动窗口
差分滑动窗口
Stage2
Stage2
0-N
0-N
N-2N
N-2N
2N-3N
2N-3N
3N-4N
3N-4N
4N-5N
4N-5N
5N-6N
5N-6N
文件写入线程滑窗(等待) 
[假设写出速度理想] <不理想就等着>
文件写入线程滑窗(等待)...
磁盘2
磁盘2
5N-6N
5N-6N
6N-7N
6N-7N
磁盘1
磁盘1
缓存写入线程滑窗b1
缓存写入线程滑窗b1
缓存写入线程滑窗b2
缓存写入线程滑窗b2
缓存写入线程滑窗b3
缓存写入线程滑窗b3
Stage3
Stage3
0-N
0-N
N-2N
N-2N
2N-3N
2N-3N
3N-4N
3N-4N
4N-5N
4N-5N
5N-6N
5N-6N
文件写入线程滑窗 
[开始执行写出]
文件写入线程滑窗...
磁盘2
磁盘2
5N-6N
5N-6N
6N-7N
6N-7N
磁盘1
磁盘1
缓存写入线程滑窗b4
缓存写入线程滑窗b4
缓存写入线程滑窗b1
缓存写入线程滑窗b1
缓存写入线程滑窗b2
缓存写入线程滑窗b2
缓存写入线程滑窗a1
缓存写入线程滑窗a1
窗口编号为 a1 a2 a3 a4
b1 b2 b3 b4
为了看清楚,部分省略
窗口编号为 a1 a2 a3 a4...
Text is not SVG - cannot display

线段划分与多线程设计

(i - j + t)* N - ( i + t ) * N
0 - N
(i - j + t)* N - ( i + t ) * N...
(i - j + t)* N - ( i + t ) * N
N - 2N
(i - j + t)* N - ( i + t ) * N...
(i - j + t)* N - ( i + t ) * N
2N - 3N
(i - j + t)* N - ( i + t ) * N...
第一缓存数组
开一个大数组即可,无线程安全问题
其中 i 表示第 i 轮条带
j 表示条带顺序
t 表示驻留区编号(本示例为0-1,即2个驻留区
N 表示条带大小

本示例中正确只有两个驻留区数组,某个容量都为3N
第一缓存数组开一个大数组即可,无线程安全问题其中 i 表示第 i 轮条带...
线程1
线程1
线程2
线程2
线程3
线程3
磁盘1
磁盘1
磁盘2
磁盘2
磁盘3
磁盘3
当且仅当所有子缓存区(一个窗口)全部写满,放行
输出数据流 (否则锁定其他子线程,木桶效应化)
从 数组 0 - K*N(其中K表示总条带数)
写入文件 ( a - 1 ) * ( K * N ) -  a * ( K * N ) 位置
(其中 a 表示批次),例如本示例表示:
 [ 0 - 3N ], [ 3N - 6N ],...
当且仅当所有子缓存区(一个窗口)全部写满,放行输出数据流 (否则锁定其他子线程,木桶效应化)...
输出文件
输出文件
滑动窗口向后进行,写其他窗口
如果里面的子窗口写完,向后继续,不阻塞
但是文件写出窗口不能和里面任何一个
子窗口重合
滑动窗口向后进行,写其他窗口如果里面的子窗口写完,向后继续,不阻塞但是文件写出窗口不能和里面任何一个子窗口重合...
(i - j + t)* N - ( i + t ) * N
3N - 4N
(i - j + t)* N - ( i + t ) * N...
(i - j + t)* N - ( i + t ) * N
4N - 5N
(i - j + t)* N - ( i + t ) * N...
(i - j + t)* N - ( i + t ) * N
5N - 6N
(i - j + t)* N - ( i + t ) * N...
线程1
线程1
线程2
线程2
线程3
线程3
磁盘1
磁盘1
磁盘2
磁盘2
磁盘3
磁盘3
Text is not SVG - cannot display

术语名词定义与统一化

Stage1 (阶段,一个时序内的相关事务组合,原子化、一致化、阶段事务性)[弱一致性特点,只能保证一个阶段的最终一致性]
Stage1 (阶段,一个时序内的相关事务组合,原子化、一致化、阶段事务性)[弱一致性特点,只能保证一个阶段的最终一致性]
0-N
0-N
N-2N
N-2N
2N-3N
2N-3N
3N-4N
3N-4N
4N-5N
4N-5N
5N-6N
5N-6N
缓存写入线程滑窗a1
缓存写入线程滑窗a1
500MB/s
500MB/s
磁盘1
条带
磁盘1...
1GB/s
1GB/s
磁盘2
条带
磁盘2...
5N-6N
5N-6N
6N-7N
6N-7N
缓存写入线程滑窗b1
缓存写入线程滑窗b1
缓存写入线程滑窗b2
缓存写入线程滑窗b2
缓存写入线程滑窗b3
缓存写入线程滑窗b3
差分滑动窗口
DifferentialSlidingWindow
差分滑动窗口DifferentialSlidingWindow...
文件写入线程滑窗
文件写入线程滑窗
驻留区缓存(ResidentCache)
表示真实使用的缓存
已经写入完成的缓存区域,可直接写出
驻留区缓存(ResidentCache)...
缓存帧(CacheFrame)
表示驻留区缓存中一个原子单位
缓存帧(CacheFrame)...
缓存窗口(CacheWin)
表示一个单位的缓存组
写到外部磁盘的最小单位
缓存窗口(CacheWin)...
滞留区缓存(RetentionCache)
临界滞留缓存区域,全部缓存
表示待写入磁盘的临界内存区域
滞留区缓存(RetentionCache)...
Text is not SVG - cannot display

任务与作业设计

多阶段事务性模型

Stage1
Stage1
缓存写入线程1
缓存写入线程1
缓存写入线程2
缓存写入线程2
缓存写入线程3
缓存写入线程3
文件写入线程1
文件写入线程1
缓存段1
缓存段1
缓存段2
缓存段2
缓存段3
缓存段3
缓存窗口1
缓存窗口1
写入
写入
Stage2
Stage2
缓存写入线程1
缓存写入线程1
缓存写入线程2
缓存写入线程2
缓存写入线程3
缓存写入线程3
文件写入线程1
文件写入线程1
缓存段1
缓存段1
缓存段2
缓存段2
缓存段3
缓存段3
缓存窗口2
缓存窗口2
写入
写入
Stage3
Stage3
缓存写入线程1
缓存写入线程1
缓存写入线程2
缓存写入线程2
缓存写入线程3
缓存写入线程3
文件写入线程1
文件写入线程1
缓存段1
缓存段1
缓存段2
缓存段2
缓存段3
缓存段3
缓存窗口3
缓存窗口3
写入
写入
Stage4 (滑动窗口 = 3)
Stage4 (滑动窗口 = 3)
缓存写入线程1
缓存写入线程1
缓存写入线程2
缓存写入线程2
缓存写入线程3
缓存写入线程3
文件写入线程1
文件写入线程1
缓存段1
缓存段1
缓存段2
缓存段2
缓存段3
缓存段3
缓存窗口1
缓存窗口1
写入
写入
Text is not SVG - cannot display

确定的有限状态自动机模型(DFA)

(老方案,考古)

写缓存
写缓存
摸鱼等待
摸鱼等待
退出
退出
监工形态
监工形态
如果写完
如果写完
写文件
写文件
摸鱼等待
摸鱼等待
如果所有条带写完
如果所有条带写完
退出
退出
如果仅当前流水线完成
如果仅当前流水线完成
被唤醒
被唤醒
被唤醒
被唤醒
切换缓存窗口编号
切换缓存窗口编号
唤醒其他所有缓存写入线程
唤醒其他所有缓存写入线程
唤醒文件写入线程(放行)
唤醒文件写入线程(放行)

缓存写入作业状态机

缓存写入作业状态机

文件写入作业状态机

文件写入作业状态机
`击鼓传花`
最慢的当接盘侠
`击鼓传花`...
文件窗口是否与本窗口重合

或所有缓存窗口写满
文件窗口是否与本窗口重合或所有缓存窗口写满...
缓存写入处于 状态
缓存写入处于 写 状态
缓存窗口是否与本窗口重合
缓存窗口是否与本窗口重合
文件窗口不与本窗口重合
且在摸鱼
文件窗口不与本窗口重合 且在摸鱼
1. 摸鱼与唤醒使用 Semaphore(信号量)同步
2. 状态机使用原子变量确保状态一致性
3.系统奉承无锁化编程,非必要不用锁
4. 优先使用原子变量(需证明状态安全),乐观场景使用自旋设计,
再CAS锁
1. 摸鱼与唤醒使用 Semaphore(信号量)同步...
Text is not SVG - cannot display

新方案:

写缓存
写缓存
摸鱼等待
摸鱼等待
退出
退出
同步状态
同步状态
如果写完
如果写完
写文件
写文件
摸鱼等待
摸鱼等待
如果所有条带写完
如果所有条带写完
退出
退出
如果仅当前流水线完成
如果仅当前流水线完成
被唤醒
被唤醒
被唤醒
被唤醒
切换缓存窗口编号
切换缓存窗口编号
唤醒其他摸鱼的缓存写入线程
(需要先检查对应作业的状态)
唤醒其他摸鱼的缓存写入线程 (需要先检查对应作业的状态)
如果文件写入在摸鱼
唤醒文件写入线程(放行)
如果文件写入在摸鱼 唤醒文件写入线程(放行)

缓存写入作业状态机

缓存写入作业状态机

文件写入作业状态机

文件写入作业状态机
文件窗口是否与本窗口重合

或所有缓存窗口写满
文件窗口是否与本窗口重合或所有缓存窗口写满...
缓存写入处于 状态
缓存写入处于 写 状态
检查
检查
缓存窗口是否与本窗口重合
缓存窗口是否与本窗口重合
文件窗口不与本窗口重合
且在摸鱼
文件窗口不与本窗口重合 且在摸鱼
1. 摸鱼与唤醒使用 Semaphore(信号量)同步
2. 状态机使用原子变量确保状态一致性
3.系统奉承无锁化编程,非必要不用锁
4. 优先使用原子变量(需证明状态安全),乐观场景使用自旋设计,
再CAS锁
1. 摸鱼与唤醒使用 Semaphore(信号量)同步...
检查
检查
文件窗口是否与本窗口重合

或所有缓存窗口写满
文件窗口是否与本窗口重合或所有缓存窗口写满...
缓存帧状态机
缓存帧状态机
写入
写入
可写入
可写入
写出
写出
Text is not SVG - cannot display

死锁风险的、脏读可能的、又读又写

  1. 获取多个线程间状态转换,出现状态非一致性同步问题

缓存bug

第一次
第一次
线程1写入10mb,counter++
线程1写入10mb,counter++
30mb
30mb
线程2写入10mb,counter++
线程2写入10mb,counter++
35mb
35mb
第二次
第二次
线程1写入10mb,counter++
线程1写入10mb,counter++
线程2写入10mb,counter++
线程2写入10mb,counter++
20mb
20mb
25mb
25mb
线程1写入10mb,counter++
线程1写入10mb,counter++
线程2写入10mb,counter++
线程2写入10mb,counter++
第三次
第三次
10mb
10mb
15mb
15mb
线程一结束
线程一结束
第四次
第四次
5mb
5mb
线程2写入5mb,counter++
线程2写入5mb,counter++
counter不会等于2了,不再向缓存区写入
counter不会等于2了,不再向缓存区写入
Text is not SVG - cannot display
Author:undefined  Create time:2024-11-13 01:00
Last editor:undefined  Update time:2024-11-16 00:32