基于斐波那契数驱动的重试机制和算法

斐波那契数列 Fibonacci Sequence (FBS)

斐波那契数列，由意大利数学家莱奥纳多·皮萨号（Leonardo of Pisa，也被称为Fibonacci，下图）在1202年撰写的《算数书》( Liber Abaci)中引入。他通过思考兔子繁殖的方式，抽象并构造了斐波那契数列的定义和形式：

F(0) = F(1) = 1; F(n) = F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）

这是一个可以无限扩展和延申的整数序列，其中前两个数字都是1，而后的数字都是前两个数字之和。给定数量限制n，我们可以获得一个n个元素的有序整数集合，就是基于n的FNS。

关于兔子繁殖的问题并不是真实的生物学意义上的，只是一个引发的数学思想实验。其设定是这样的：有一对新生的兔子(一公一母)，它们需要生长一个月，并在第二个月末尾可以生产一对小兔(也是一公一母)。斐波那契提出的问题是：假设这个过程可以不断持续，而且所有兔子都不会死亡，一年后会有多少对兔子(下图)？显然，这个问题其实就是FBS数列的计算方式。

斐波那契数列有许多有趣的数学特性，并能够形象的体现在数学和自然科学的许多不同领域中。例如，它与黄金分割比例(Golden Ratio）密切相关，这是一个数学常数，大约为1.618。黄金分割比在许多自然和人工结构中都可以找到，例如海螺的螺旋模式和巴斯坦农的比例(下图)，它们其实是和FBS构造的几何图形刚好是符合的，可以看成是FBS的一种可视化形式。

FBS计算程序

本文的重点并不是讨论各种语言的FBS计算，只是简单的阐述一下它的一般和JS实现方式，这个会在后面的讨论中遇到。在很多算法教材中，都会提到可以使用递归的方式，来进行FBS的计算，这也是递归概念和应用的一个典型案例；此外，笔者觉得所有的开发者还应该有一个概念，就是所有的递归操作，都可以转换成为等效的循环操作。因为本质而言，递归操作，就是一个自调用的，可变参数和具有结束机制的循环操作。

关于这两种操作的实现方式，都可以参考下面的JS示例代码：

// FBS 递归实现
const fib1 = (n)=> n <= 2 ? 1 : (fib1(n-2) + fib1(n-1));

// FBS 循环实现
const fib2 = (n)=> Array(n-2).fill().reduce(c=>(c.sum = c.i1+c.i2, c.i1= c.i2, c.i2 = c.sum,c), {sum:0, i1:1, i2:1}).sum;

// 测试 48
const nfb = 48;
console.time("fib1");
console.log("result:", fib1(nfb));
console.timeEnd("fib1");

console.time("fib2");
console.log("result:", fib2(nfb));
console.timeEnd("fib2");


// 执行 
node .\f.js
result: 4807526976
fib1: 30.101s
result: 4807526976
fib2: 0.266ms

代码中可以看到：

• 测试使用的FBS数列长度是48，就是四年后兔子的对数
• 使用循环算法的速度，远高于递归算法(0.266ms vs 30.101s)

另外，从上面的示例可以看到，递归虽然看起来非常巧妙而简洁，但应用到实际的开发中，需要非常注意它的执行效率。从计算机程序的执行原理来看，深度的递归操作会制造大量的调用堆栈操作，并进行很多上下文环境的切换，反而会影响执行效率。所以，真实的编程环境中，应当避免使用递归操作，除非编译器有优化机制，可以将递归自动转换为循环。

操作故障重试机制

前面我们已经看到，FBS在数学上和图形上，具有某种形式的优雅和美感。正是这些，让笔者觉得可以将其应用到程序的故障后重试操作过程中的时间间隔计算的机制当中。

例如，一个网络请求，由于某种原因(如对方系统故障)失败了，我们期望在一段时间后重新尝试。关键就是这个时间，多长是比较合理的。时间过短，增加计算和操作的负担，时间过长，又影响操作的及时性。一个简单的办法都是固定时间重试，但这个操作看起来就不够“聪明”。一个简单的认知和构想，就是在初始的时候，可以适当的使用较短的重试周期，如果多次尝试都不成功，我们就可以认为可能短期内系统不能快速恢复，可以逐渐加大重试间的间隔，直到达到一个比较合理的最大间隔。

这样一个由小到大的时间间隔，是不是可以考虑使用FBS数列中的某一个值即斐波那契数来提供呢？

但需要说明，这个构想确实比较美妙，但在笔者没有看到理论和科学上的依据，也许有概率论和数理逻辑方面的证明，但笔者的数学水平有限，还不能给出这个论断。但基于逻辑概念的感觉，其有其合理性，我们也不妨将其应用到实际开发和业务当中。

补充一下，上面的假设，转换为数学的描述，也许可以是这样的。假设故障恢复的时间在一定范围内是随机的，需要证明，使用FBS来控制重试操作，则相对于其他方式，FBS的效率最高。这个效率可以使用下面的方式来度量(越小越好):

重试次数 x 距离上次重试的时间

不一定科学合理哈，只是提出这个设定，有兴趣的读者欢迎参与讨论。但不管怎么样，我们都可以先用这个设想，来实现这个控制机制。

重试机制的FBS实现

下面就是基于上面的理论，笔者编写的FBS重试时间间隔控制机制的示例代码和配套的应用测试代码。

const EventEmitter = require('events').EventEmitter;

class fbnotify extends EventEmitter {
    constructor(maxInterval = 3600) {
        super();
        this.maxInterval = maxInterval;
        this.reset();
    };

    _startCount(){
        // notifi
        if (this.fvalue) this.emit("notify", "Should Retry:"+this.fvalue);

        // current value 
        if (this.fvalue < this.maxInterval) {
            this.fvalue = this.fvalue1 + this.fvalue2;
            
            // check time
            setTimeout(()=>this._startCount(), this.fvalue * 1000);
            
            // next round value 
            this.fvalue1 = this.fvalue2;
            this.fvalue2 = this.fvalue;
        } else { // just check 
            setTimeout(()=>this._startCount(), this.fvalue * 1000);
        }
    };

    reset(){
        this.fvalue1 = 1;
        this.fvalue2 = 1;
        this.fvalue  = null;

        this._startCount();
    };
}


const test = ()=>{
    const n1 = new fbnotify();

    n1.on("notify",(msg)=>{
        // random check 
        if (Math.random()*1000 < 500) {
            n1.reset();
            console.log("Retry OK and Reset");
        } else {
            console.log("Retrying...", msg, 0|Date.now()/1000);
        }
    });
}; test();

这段代码的要点是：

• 笔者希望它的实现是一个计时器之类的东西，会以FBS数列作为时间间隔，发出一个通知，来控制重试操作的执行
• 这个机制尽量能够和业务系统解除耦合并，不使用外部依赖，简单易用，结合上面的构想，就考虑使用扩展Event类
• 使用了一个扩展的Event类，封装了FBS计算和重试消息通知的发送
• 在使用的时候，基于这个类创建一个通知器，并按照业务需求，重写通知时的处理方法
• 通知信息内包括了当前的重试间隔，帮助业务应用可以选择的判断当前重试状态
• 构建通知器时，可以设置最大的重试间隔，这里默认为一小时
• 通知器可以复用，在复用前可以调用reset方法重置状态
• 通知和执行是解耦的，业务应用只是接受重试通知，自行决定是否进行重试操作

在明确了基本原理之后，可以根据业务系统，比较容易的就可以在这个基础上进行扩展。比如直接在构造方法中设置重试操作，增加start、pause等方法来更精细的控制发生过程等等。

小结

本文从斐波那契数列的由来和定义出发，例举了其基本的计算和实现方法，探讨了其使用递归方式进行计算的性能问题，并进一步研究了它在操作重试间隔时间的控制机制中的应用，给出了示例的实现和代码。