[Sheepdog] [PATCH 0/3] optimisation patch to make recovery faster.

[Li Wenpeng]

These patches made some optimisation to make the cluster recovering faster.

The first two patches implemented an object list cache, Before the patch,
when the cluster is recovering, every node needs to send a request to
all the other nodes to get their object list, and there's no object list
cache for sheep node, so every time the node needs to walk through the 
object directory to get the list, it costs too much. I added a object list
cache implemented by red-black tree to cache the object id list, when we 
create a new object, we write its oid to the cache, so the get_obj_list() 
function just read the cache instead of read the directory.

In my testing environment there's 2G data in the cluster, without the patch,
it takes 69344.645 us for get_obj_list() to execute which is measured by
"collie debug trace", with the patch it takes at most 15.655 us.

The third patch reduced IO operation in farm when recovering, before the patch,
every time the cluster is recovering, farm writes all the local objects to
snapshot, indeed, it's unnecessary to write all the local object, we just
need to write the object that will not belong to the current node to the 
snapshot, when recovering, we first read the object from the local object
directory, if the object doesn't exist there, then read it from snapshot.

I use the following script to test the patch.

#!/bin/sh

for i in 0 1 2 3; do
	sheep/sheep -d /home/levin/disk/store/$i -z $i -p 700$i;
	sleep 1;
done
collie/collie cluster format -c 3 -b "farm"
qemu-img create -f raw sheepdog:debian 10G
qemu-io -c "write -P 0x1 0 5G" sheepdog:debian
qemu-io -c "write -P 0x1 5G 5G" sheepdog:debian

sheep/sheep -d /home/levin/disk/store/4 -z 4 -p 7004

Before the patch, it takes 58 seconds for recovery, after the patch,
it only takes less than 1 seconds.