Non-Balance磨损平衡算法：提升固态硬盘3倍以上寿命
为了让闪存拥有更长久的生命周期，避免一些块（block）被频繁擦除而迅速成为坏块，而另一些块则因极少擦除这样不均衡的擦写而导致ssd整体生命周期缩短的弊端，闪存从业者提出了多种磨损平衡算法（wear-levelling）和垃圾回收（garbage collection）策略来规避这些问题的产生。
磨损平衡算法产生的背景
磨损平衡算法是基于闪存的基本特征而产生：
1、不支持本地更新（outplace-update，即不能在原数据位置进行覆盖写入或者直接更改，更改数据需要将更改后的数据搬迁至新的可用的page，原有位置的page被标示为无效页，必须要先擦除无效页才能在原位置重新写入数据）；
2、以page为单位写入，以block为单位擦除，擦除block需要先将可用page中的数据搬迁，那么，当有大量的block可以被选择擦除时，搬迁哪些block中的page并重新利用就关系到对不同block的擦除次数；
3、每个block有擦除次数限制，经常被擦除的block会很快成为“坏块（bad block）”因此，只有均衡每个block的擦除次数，才能让闪存具有更长的使用寿命。
ftl通常将page分为三种类型：有效页（valid page）、无效页（invilid page）、可用页（free page）,若物理页有逻辑地址相对应则表明该页的数据是有效的，称为有效页，反之，称为无效页，当垃圾回收运行后，无效页被erase，成为可用页，此时，才可以重新被写入数据。
举例来说，当逻辑地址a（假设对应物理地址1）数据需要被修改，无法直接对a地址的数据修改，需要将a地址数据读取到cache中进行修改，然后将修改好的数据写入新的物理地址（假设物理地址6），同时将逻辑地址a对应到物理地址6，trim将物理地址1标为无效页，当可用页越来越少时，就会启动垃圾回收（garbage collection）,将无效页进行erase，重新变成可用页，此时，问题就来了：
由于erase是以block为单位，如果需要擦除的block中仍然包含有效页，那么就需要先将有效页进行搬迁，然后才能擦除，那么，是对包含有效页最少的block进行擦除还是对虽然包含有效页较多但擦除次数较少的block进行擦除？是否考虑有效块冷数据所在block的擦除次数？还是有他条件的对某些block进行擦除？由于这些垃圾回收直接关系到block的擦除次数，因此，如何做到每个block都能够被平均的擦除，而不是对某些包含热点数据的block经常被擦除，而另一些block则极少被擦除，磨损平衡算法正是在此背景下产生。
垃圾回收策略
所谓的磨损平衡是指在执行垃圾回收的过程中，对哪些block执行垃圾回收，用什么样的机制进行回收才能保证每个block被擦除的次数接近均衡。简单的回收策略可以缩短计算回收block所需的时间，但会导致每个block磨损的不均衡。复杂的回收策略均衡了算法，但导致系统效能降低，因此，好的回收策略需要平衡系统效能和磨损次数之间的微妙关系。
垃圾回收策略从最基本的greedy算法（选择包含最少有效页的block来回收）到逐步演进的cost-benefit算法（考虑的block的擦除频率，也就是冷热数据的影响），公式如下：
再到cat回收算法，在cost-benefit的基础上考虑了block的擦除次数因素，需要回收的block由决定，选择所得值最小的block来回收）。公式如下：
进而cicl算法则更进一步进行了优化，需要回收的block由block中的有效page数与所有block擦除次数是否平均两个因素来决定，l为决定这两个因素的权重，如果所有block的平均擦除次数相同，则l为0，选择需要回收的block时只需要考虑block中的有效page数即可，否则，就需要考虑此两种因素。公式如下：
基于上述垃圾回收策略的基础思想，各家controller厂商演变出多种多样的各不相同垃圾回收算法，以及冷热数据的分析方法。
被动回收策略和主动回收策略
垃圾回收有两个重要的问题需要考虑：回收无效block的时机以及每次回收的数量。因此，又关系到两种回收策略：主动回收策略与被动回收策略。被动回收策略是当接收到写入请求时，系统根据目前状况判断是否执行垃圾回收，此策略模式下，系统通常会对可用空间设定一个临界值，当可用空间小于临界值时开始执行垃圾回收。每次需要回收多少空间则有firmware工程师自己定义。
这种磨损的弊端在于：当执行垃圾回收时，写入请求会被延迟，每次需要执行回收的block数量越多，延迟的时间就越长，外在表现为写入性能急速下降。对于普通用户而言，会感觉系统卡顿或者假死现象，对于数据采集用户而言，在执行垃圾回收过程中将会出现大量的丢帧现象。
下图：被动垃圾回收机制下的性能表现：
主动回收策略则是利用系统空闲时间执行垃圾回收，通过固件设定周期性任务，定时检查可用块的剩余情况，如有需要就执行垃圾回收。主动回收策略等同于利用空闲时间提前进行垃圾回收，避免了被动策略所造成的性能波动。单一利用系统空闲时间执行主动垃圾回收同样存在弊端，假设系统一直没有空闲时间，垃圾回收同样无法有效执行，例如：城市道路视频监控，闪存会一直有文件写入，此种情形下垃圾回收与被动策略基本雷同。
领存在主动回收策略中采用了更加优化的方式：pr-latency技术，同时，根据不同的应用场景，配合自动可调的op空间，可以使ssd即使在100%写/读负荷的情况下都可以保持同样的性能，使用iometer 设置2mb pattern，100%写模式进行不间断的测试，一周后直接测试性能曲线，仍然可以表现为一条直线。
静态磨损平衡和动态磨损平衡
动态磨损平衡是指当需要更改某个page中的数据时，将新的数据写入擦除次数较少的物理页上，同时将原页标为无效页，动态磨损平衡算法的缺点在于，如果刚刚写入的数据很快又被更新，那么，刚刚更新过的数据块很快又变成无效页，如果频繁更新，无疑会让保存冷数据的block极少得到擦除，对闪存整体寿命产生不利影响。早期的ssd主控多用动态磨损平衡算法，现在则更多是研究动态和静态共同使用。
静态磨损平衡则是考虑了那些更新频率很低的block（冷数据），例如：系统数据所在的block，或者某些只读数据，这些冷数据所在的block被更新的频率比热数据所在的block明显低很多，静态磨损平衡算法就是把这些冷数据所在的block也加入磨损平衡中，增加了闪存的总体寿命。静态磨损平衡的算法非常多，没有那种算法是绝对的完美，后人的算法总是在前人算法的基础上更进一步，不同应用场景、不同需求都会导致不同的算法产生。
一种寿增三倍的算法：领存non-blance磨损平衡算法
目前垃圾回收算法基本都是围绕如何更加平均的擦除每个block这种思想进行设计，这些算法是基于block耐磨度完全一致的“假设”基础之上，但事实上，每个page和block的耐磨状态是不同的，当对一个闪存上的所有block进行平均擦除时，必然会有一些block先成为bad block，而另一些block则会有更长时间的耐磨度。这是由晶圆设计工艺所决定的，在目前的工艺条件下，尚无法确保每个block完全一致，而且晶圆一定会存在一些错误，不可控制的是这些错误是随机分布的。
下图为全新nand flash（型号：js29f16b08ccme2，intel 16gb mlc）做10次p/e后的情形，结果显示每个block的erase时间是不同的，不同的操作时间反应了每个block的原始状态不同，操作时间短的block健康状态理论上好于操作时间长的block。
如果每个block的耐磨度本来是不均衡的，人为通过算法保持每个block擦除一致的结果，不是延长了闪存整体寿命，恰恰是损害了闪存最佳使用寿命。
领存 non-blance算法思想是：能者多劳。打破前人假设“每个block寿命一致”基础上的平衡算法，在使用过程中对每个page和block真实耐磨度进行评估，让耐磨度强的block得到更多的擦写次数，而耐磨度差的则得到相应的保护。只有每个block都不成为坏块，才能最大程度上减少对每个block的擦除次数，举例来说：100个block写入1tb数据和1000个block写入1tb数据，假设100个block写入1tb数据需要被擦除10次，那么，1000个block只需要被擦除1次。
non-blance算法的另一个精要是：当block的不可纠正误码率（uber，uncorrectable bit error rate）达到一定的阈值时，将mlc模式转自动换为slc模式。non-blance算法涉及到重要的技术难题是：如何判断闪存的真实耐磨度（如：page1为3000p/e cycle，page3为5000p/e cycle）。测试page真实耐磨度的方法有很多，可以通过某个关键指标或者多个指标综合判断，也可以通过高温或者低温条件下的加速测试事先做好某一型号nand flash的耐磨度关键指标测试，具体做法有如下思路：
通过对某一个型号的nand flash做破坏性测试，对nand flash做最彻底的p/e测试，记录原始误码率变化、不可纠正误码率和操作时间的精准数据，建立三者之间的数学模型，定义不同误码率（原始误码率及低强度ecc下的误码率）及操作时间对应page真实的耐磨度，通过高温条件下的加速测试修正此数学模型。
尽管从实际的操作过程上看，会增加很高的复杂度（测试是个非常耗费时间的过程，且需要对数学模型不断的修正使其更加精准），但实际的效果会远远好于不考虑page实际耐磨度的做法，技术的进步往往是从细节和耐心开始。
ssd是木桶理论的最佳践行者，ssd的整体寿命取决于最差的那片闪存，因此，如何筛选出耐磨度一致的闪存才决定了ssd到底可以使用多久，否则，无论多么优秀的算法，终究会败给最孱弱的那片闪存。
fqj
电容自举电路电路图大全（六款电容自举电路设计原理图详解）
最新的AMD Ryzen 5000处理器和新的Intel系列保证了出色的性能
中国联通与首都博物馆打造的5G+智慧博物馆联合实验室正式揭牌成立
电机启动电流到底有多大_减小电动机启动电流的方法
武汉AI基因组检测平台识别准确率达99%以上
Non-Balance磨损平衡算法：提升固态硬盘3倍以上寿命
I2C总线控制的高性能音频处理电路设计
rs485通信OSI模型网络层
不同种类的损失函数以及它们的作用
本土IC制造业发展:探求特色之路
你对于哪几种嵌入式处理器有所了解
小米Mix还在加价？高屏占比手机三百多块就能体验？
苹果证实，已经收购了自动驾驶汽车企业Drive. ai
各类传动方式的优缺点
电源管理与使用的高速微控制器-Using Power Man
到2023年印度输配电设备需求将达158亿美元，为全球需求增长贡献33％
现在区块链最火热的场景在哪里
单片机教程二十:单片机串行口介绍
鸿蒙和LiteOS的内核都是一样的名字，可它们究竟有什么不同呢？
2020年手机柔性OLED面板出货量预计将年增50%
磨损平衡算法产生的背景
磨损平衡算法是基于闪存的基本特征而产生：
1、不支持本地更新（outplace-update，即不能在原数据位置进行覆盖写入或者直接更改，更改数据需要将更改后的数据搬迁至新的可用的page，原有位置的page被标示为无效页，必须要先擦除无效页才能在原位置重新写入数据）；
2、以page为单位写入，以block为单位擦除，擦除block需要先将可用page中的数据搬迁，那么，当有大量的block可以被选择擦除时，搬迁哪些block中的page并重新利用就关系到对不同block的擦除次数；
3、每个block有擦除次数限制，经常被擦除的block会很快成为“坏块（bad block）”因此，只有均衡每个block的擦除次数，才能让闪存具有更长的使用寿命。
ftl通常将page分为三种类型：有效页（valid page）、无效页（invilid page）、可用页（free page）,若物理页有逻辑地址相对应则表明该页的数据是有效的，称为有效页，反之，称为无效页，当垃圾回收运行后，无效页被erase，成为可用页，此时，才可以重新被写入数据。
举例来说，当逻辑地址a（假设对应物理地址1）数据需要被修改，无法直接对a地址的数据修改，需要将a地址数据读取到cache中进行修改，然后将修改好的数据写入新的物理地址（假设物理地址6），同时将逻辑地址a对应到物理地址6，trim将物理地址1标为无效页，当可用页越来越少时，就会启动垃圾回收（garbage collection）,将无效页进行erase，重新变成可用页，此时，问题就来了：
由于erase是以block为单位，如果需要擦除的block中仍然包含有效页，那么就需要先将有效页进行搬迁，然后才能擦除，那么，是对包含有效页最少的block进行擦除还是对虽然包含有效页较多但擦除次数较少的block进行擦除？是否考虑有效块冷数据所在block的擦除次数？还是有他条件的对某些block进行擦除？由于这些垃圾回收直接关系到block的擦除次数，因此，如何做到每个block都能够被平均的擦除，而不是对某些包含热点数据的block经常被擦除，而另一些block则极少被擦除，磨损平衡算法正是在此背景下产生。
垃圾回收策略
所谓的磨损平衡是指在执行垃圾回收的过程中，对哪些block执行垃圾回收，用什么样的机制进行回收才能保证每个block被擦除的次数接近均衡。简单的回收策略可以缩短计算回收block所需的时间，但会导致每个block磨损的不均衡。复杂的回收策略均衡了算法，但导致系统效能降低，因此，好的回收策略需要平衡系统效能和磨损次数之间的微妙关系。
垃圾回收策略从最基本的greedy算法（选择包含最少有效页的block来回收）到逐步演进的cost-benefit算法（考虑的block的擦除频率，也就是冷热数据的影响），公式如下：
再到cat回收算法，在cost-benefit的基础上考虑了block的擦除次数因素，需要回收的block由决定，选择所得值最小的block来回收）。公式如下：
进而cicl算法则更进一步进行了优化，需要回收的block由block中的有效page数与所有block擦除次数是否平均两个因素来决定，l为决定这两个因素的权重，如果所有block的平均擦除次数相同，则l为0，选择需要回收的block时只需要考虑block中的有效page数即可，否则，就需要考虑此两种因素。公式如下：
基于上述垃圾回收策略的基础思想，各家controller厂商演变出多种多样的各不相同垃圾回收算法，以及冷热数据的分析方法。
被动回收策略和主动回收策略
垃圾回收有两个重要的问题需要考虑：回收无效block的时机以及每次回收的数量。因此，又关系到两种回收策略：主动回收策略与被动回收策略。被动回收策略是当接收到写入请求时，系统根据目前状况判断是否执行垃圾回收，此策略模式下，系统通常会对可用空间设定一个临界值，当可用空间小于临界值时开始执行垃圾回收。每次需要回收多少空间则有firmware工程师自己定义。
这种磨损的弊端在于：当执行垃圾回收时，写入请求会被延迟，每次需要执行回收的block数量越多，延迟的时间就越长，外在表现为写入性能急速下降。对于普通用户而言，会感觉系统卡顿或者假死现象，对于数据采集用户而言，在执行垃圾回收过程中将会出现大量的丢帧现象。
下图：被动垃圾回收机制下的性能表现：
主动回收策略则是利用系统空闲时间执行垃圾回收，通过固件设定周期性任务，定时检查可用块的剩余情况，如有需要就执行垃圾回收。主动回收策略等同于利用空闲时间提前进行垃圾回收，避免了被动策略所造成的性能波动。单一利用系统空闲时间执行主动垃圾回收同样存在弊端，假设系统一直没有空闲时间，垃圾回收同样无法有效执行，例如：城市道路视频监控，闪存会一直有文件写入，此种情形下垃圾回收与被动策略基本雷同。
领存在主动回收策略中采用了更加优化的方式：pr-latency技术，同时，根据不同的应用场景，配合自动可调的op空间，可以使ssd即使在100%写/读负荷的情况下都可以保持同样的性能，使用iometer 设置2mb pattern，100%写模式进行不间断的测试，一周后直接测试性能曲线，仍然可以表现为一条直线。
静态磨损平衡和动态磨损平衡
动态磨损平衡是指当需要更改某个page中的数据时，将新的数据写入擦除次数较少的物理页上，同时将原页标为无效页，动态磨损平衡算法的缺点在于，如果刚刚写入的数据很快又被更新，那么，刚刚更新过的数据块很快又变成无效页，如果频繁更新，无疑会让保存冷数据的block极少得到擦除，对闪存整体寿命产生不利影响。早期的ssd主控多用动态磨损平衡算法，现在则更多是研究动态和静态共同使用。
静态磨损平衡则是考虑了那些更新频率很低的block（冷数据），例如：系统数据所在的block，或者某些只读数据，这些冷数据所在的block被更新的频率比热数据所在的block明显低很多，静态磨损平衡算法就是把这些冷数据所在的block也加入磨损平衡中，增加了闪存的总体寿命。静态磨损平衡的算法非常多，没有那种算法是绝对的完美，后人的算法总是在前人算法的基础上更进一步，不同应用场景、不同需求都会导致不同的算法产生。
一种寿增三倍的算法：领存non-blance磨损平衡算法
目前垃圾回收算法基本都是围绕如何更加平均的擦除每个block这种思想进行设计，这些算法是基于block耐磨度完全一致的“假设”基础之上，但事实上，每个page和block的耐磨状态是不同的，当对一个闪存上的所有block进行平均擦除时，必然会有一些block先成为bad block，而另一些block则会有更长时间的耐磨度。这是由晶圆设计工艺所决定的，在目前的工艺条件下，尚无法确保每个block完全一致，而且晶圆一定会存在一些错误，不可控制的是这些错误是随机分布的。
下图为全新nand flash（型号：js29f16b08ccme2，intel 16gb mlc）做10次p/e后的情形，结果显示每个block的erase时间是不同的，不同的操作时间反应了每个block的原始状态不同，操作时间短的block健康状态理论上好于操作时间长的block。
如果每个block的耐磨度本来是不均衡的，人为通过算法保持每个block擦除一致的结果，不是延长了闪存整体寿命，恰恰是损害了闪存最佳使用寿命。
领存 non-blance算法思想是：能者多劳。打破前人假设“每个block寿命一致”基础上的平衡算法，在使用过程中对每个page和block真实耐磨度进行评估，让耐磨度强的block得到更多的擦写次数，而耐磨度差的则得到相应的保护。只有每个block都不成为坏块，才能最大程度上减少对每个block的擦除次数，举例来说：100个block写入1tb数据和1000个block写入1tb数据，假设100个block写入1tb数据需要被擦除10次，那么，1000个block只需要被擦除1次。
non-blance算法的另一个精要是：当block的不可纠正误码率（uber，uncorrectable bit error rate）达到一定的阈值时，将mlc模式转自动换为slc模式。non-blance算法涉及到重要的技术难题是：如何判断闪存的真实耐磨度（如：page1为3000p/e cycle，page3为5000p/e cycle）。测试page真实耐磨度的方法有很多，可以通过某个关键指标或者多个指标综合判断，也可以通过高温或者低温条件下的加速测试事先做好某一型号nand flash的耐磨度关键指标测试，具体做法有如下思路：
通过对某一个型号的nand flash做破坏性测试，对nand flash做最彻底的p/e测试，记录原始误码率变化、不可纠正误码率和操作时间的精准数据，建立三者之间的数学模型，定义不同误码率（原始误码率及低强度ecc下的误码率）及操作时间对应page真实的耐磨度，通过高温条件下的加速测试修正此数学模型。
尽管从实际的操作过程上看，会增加很高的复杂度（测试是个非常耗费时间的过程，且需要对数学模型不断的修正使其更加精准），但实际的效果会远远好于不考虑page实际耐磨度的做法，技术的进步往往是从细节和耐心开始。
ssd是木桶理论的最佳践行者，ssd的整体寿命取决于最差的那片闪存，因此，如何筛选出耐磨度一致的闪存才决定了ssd到底可以使用多久，否则，无论多么优秀的算法，终究会败给最孱弱的那片闪存。
fqj
电容自举电路电路图大全（六款电容自举电路设计原理图详解）
最新的AMD Ryzen 5000处理器和新的Intel系列保证了出色的性能
中国联通与首都博物馆打造的5G+智慧博物馆联合实验室正式揭牌成立
电机启动电流到底有多大_减小电动机启动电流的方法
武汉AI基因组检测平台识别准确率达99%以上
Non-Balance磨损平衡算法：提升固态硬盘3倍以上寿命
I2C总线控制的高性能音频处理电路设计
rs485通信OSI模型网络层
不同种类的损失函数以及它们的作用
本土IC制造业发展:探求特色之路
你对于哪几种嵌入式处理器有所了解
小米Mix还在加价？高屏占比手机三百多块就能体验？
苹果证实，已经收购了自动驾驶汽车企业Drive. ai
各类传动方式的优缺点
电源管理与使用的高速微控制器-Using Power Man
到2023年印度输配电设备需求将达158亿美元，为全球需求增长贡献33％
现在区块链最火热的场景在哪里
单片机教程二十:单片机串行口介绍
鸿蒙和LiteOS的内核都是一样的名字，可它们究竟有什么不同呢？
2020年手机柔性OLED面板出货量预计将年增50%