Smart Delay with Fibonacci

In the past few weeks I have been cleaning and optimizing some operations in a storage server. After running millions of operations I noticed an interesting condition and decided to use a different approach. Did a quick Internet search using Google Chrome for “smart delays” and nothing related seemed to come up. I thought using it for a title for this post would be fine.

As background, when you have a heavy multithreaded server there is the possibility that some threads might be attempting to use a single resource at the same time. One could allow access to the resource by one of the threads and the rest would remain in a queue until some delay expires to try again. That works in many cases.

What is one has multiple threads accessing a database and / or the file system and are interested in determine if a record has been inserted in a database and / or if a file was been written to the file system. Now allowing single access would not make much difference given that all what the threads need is confirmation that the database has been updated and / or a file has been written to the file system.

In this last case we could delay for a few milliseconds and then try again. That seems to work but many threads might repeatedly attempt to access the database and / or file system at the same time producing additional consumption of resources making the two original tasks to take a lithe longer.

As an example, the Ethernet (not to confuse with the Internet) protocol implements a mechanism to back off when a collision on the wire is detected. If all clients attempt to continue to access the medium at the same time, the problem would just persist. Because of such issue, clients backup with different delay intervals. By using such approach the result is to allow access by a client faster.

Most software developers know and understand the Fibonacci sequence or numbers. You can read more about it from a previous post or in Wikipedia. In a nutshell the sequence starts with 0 and 1 or 1 and 1. The next entry in the sequence is generated by adding the two previous entries. In the first case it would be 0 + 1 = 1 or 1 + 1 = 2. As you can tell, once past zero, you get the same sequence of numbers.

What is interesting is that the sequence is found all over nature. So why not implement a mechanism to delay bases on such sequence. You could also use a random number seed, and produce a sequence of numbers as delays. Let’s try the Fibonacci approach.

Please note that we should be able verify that the code works from a programmatically point of view. The issue is to verify that the SmartDelay code makes a difference in the actual storage server.

Let’s start by taking a look at a couple screen captures of the Eclipse IDE:

setFibRand <<< random.nextInt(): 3
main <<< SmartDelay [i=0, count=1, fibSeq=[1, 1], wait=1]
main <<< SmartDelay [i=1, count=2, fibSeq=[1, 2], wait=2]
main <<< SmartDelay [i=0, count=3, fibSeq=[3, 2], wait=3]
main <<< SmartDelay [i=1, count=4, fibSeq=[3, 5], wait=5]
main <<< SmartDelay [i=0, count=5, fibSeq=[8, 5], wait=8]
main <<< SmartDelay [i=1, count=6, fibSeq=[8, 13], wait=13]
main <<< SmartDelay [i=0, count=7, fibSeq=[21, 13], wait=21]
main <<< SmartDelay [i=1, count=8, fibSeq=[21, 34], wait=34]
main <<< SmartDelay [i=0, count=9, fibSeq=[55, 34], wait=55]
main <<< SmartDelay [i=1, count=10, fibSeq=[55, 89], wait=89]
main <<< SmartDelay [i=0, count=11, fibSeq=[144, 89], wait=144]
main <<< SmartDelay [i=1, count=12, fibSeq=[144, 233], wait=233]
main <<< SmartDelay [i=0, count=13, fibSeq=[377, 233], wait=377]
main <<< done

The second console capture follows:

setFibRand <<< random.nextInt(): 7
main <<< SmartDelay [i=0, count=1, fibSeq=[2, 1], wait=2]
main <<< SmartDelay [i=1, count=2, fibSeq=[2, 3], wait=3]
main <<< SmartDelay [i=0, count=3, fibSeq=[5, 3], wait=5]
main <<< SmartDelay [i=1, count=4, fibSeq=[5, 8], wait=8]
main <<< SmartDelay [i=0, count=5, fibSeq=[13, 8], wait=13]
main <<< SmartDelay [i=1, count=6, fibSeq=[13, 21], wait=21]
main <<< SmartDelay [i=0, count=7, fibSeq=[34, 21], wait=34]
main <<< SmartDelay [i=1, count=8, fibSeq=[34, 55], wait=55]
main <<< SmartDelay [i=0, count=9, fibSeq=[89, 55], wait=89]
main <<< SmartDelay [i=1, count=10, fibSeq=[89, 144], wait=144]
main <<< SmartDelay [i=0, count=11, fibSeq=[233, 144], wait=233]
main <<< SmartDelay [i=1, count=12, fibSeq=[233, 377], wait=377]
main <<< SmartDelay [i=0, count=13, fibSeq=[610, 377], wait=610]
main <<< done

The output was generated by the following code:

package canessa.smartdelay;

/*
 * 
 */
public class Solution {

	public static void main(String[] args) {
		
		// **** instantiate / initialize the smart delay ****
		SmartDelay smartDelay = new SmartDelay();
		smartDelay.setFibRand();
		
		// **** loop using smart delays ****
		for (int i = 0; i < 13; i++) {
			smartDelay.delay();
			System.out.println("main <<< " + smartDelay.toString());
		}
		
		// **** ****
		System.out.println("main <<< done");
	}

}

The code is quite simple and attempts to simulate a client thread attempting to check the availability of a file in the storage server. If the caller determines that the file is not found it would return an error. Typically the client makes a storage request which spawns a thread that stores the data, updates the database and then checks both the database and the file in the file system. In this case we can assume that the expected data was not available until the 13th pass.

The code for the SmartDelay class follows:

package canessa.smartdelay;

import java.util.Arrays;
import java.util.Random;

/*
 * 
 */
public class SmartDelay {

	int		i;
	long 	count;
	long[] 	fibSeq;
	long 	wait;
	
	public SmartDelay() {
		this.fibSeq 	= new long[2];
		this.fibSeq[0] 	= 1;
		this.fibSeq[1] 	= 1;
		this.i 			= 1;
		this.wait 		= 0;
	}
	
	public void delay() {
		
		// **** update wait (in ms) ****
		long sum 		= this.fibSeq[0] + this.fibSeq[1];
		this.wait 		= sum;
		
		this.i++;
		this.i			%= 2;
		this.fibSeq[i] 	= sum;
		
		this.count 		+= 1;
		
		// **** actual wait ****
		try {
			Thread.sleep(this.wait);
		} catch (InterruptedException e) {
			e.printStackTrace();
		}
	}

	@Override
	public String toString() {
		return "SmartDelay [i=" + i + ", count=" + count + ", fibSeq=" + Arrays.toString(fibSeq) + ", wait=" + wait
				+ "]";
	}

	// **** ****
	public SmartDelay setI(int i) {
		this.i = i;
		return this;
	}

	public SmartDelay setCount(long count) {
		this.count = count;
		return this;
	}

	public SmartDelay setFibSeq(long fibSeq, int i) {
		
		if (i < 0) i = 0; else if (i > 1)
			i = 1;
		
		this.fibSeq[i]= fibSeq;
		return this;
	}
	
	public SmartDelay setFibRand() {
//		Thread currentThread = Thread.currentThread();
//		long threadID = currentThread.getId();
//		System.out.println("setFibRand <<< threadID: " + threadID);
//		this.setFibSeq((threadID % 16), 0);
		
		Random random = new Random();
		System.out.println("setFibRand <<< random.nextInt(): " + random.nextInt(10));
		this.setFibSeq(random.nextInt(10), 0);

		return this;
	}

	public SmartDelay setWait(long wait) {
		this.wait = wait;
		return this;
	}
}

The code is in the SmartDelay.java file. As you can see there are the members, the constructor and a few setter methods.  I tend to experiment while thinking what needs to be done in order to get to the desired solution. Please note that the code here shown was the product of such process. The actual code will be written in a combination of C/C++.

Hope you enjoyed this post. If you have comments or questions, please leave me a note following the post. I will respond as soon as possible.

Happy software development;

John

Follow me on Twitter: @john_canessa

PS: Will update this post in a few days and let you know if the SmartDelay implementation eliminated most / all of the messages generated by the previous delay implementation.

One thought on “Smart Delay with Fibonacci”

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.