洗牌算法

-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 downto 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

java 实现

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

public class Shuffle {

	public static void shuffle(int[] arr) {
		int i = arr.length;
		Random random = new Random();
		while (i > 1) {
			i = i - 1;
			int j = random.nextInt(i);
			int temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
		}
		System.out.println(Arrays.toString(arr));
	}

	public static void main(String[] args) {
		int[] arr = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
		for (int i = 0; i < 50; i++)
			shuffle(arr);
	}
}

运行50次结果

[7, 3, 0, 2, 9, 1, 8, 4, 6, 5]
[3, 2, 5, 9, 1, 6, 7, 0, 4, 8]
[7, 8, 6, 1, 4, 2, 0, 9, 5, 3]
[9, 3, 1, 7, 5, 6, 4, 8, 2, 0]
[5, 9, 0, 2, 1, 4, 7, 6, 3, 8]
[4, 8, 3, 9, 6, 1, 5, 0, 2, 7]
[0, 6, 9, 1, 3, 5, 4, 2, 7, 8]
[6, 3, 8, 4, 5, 2, 0, 9, 1, 7]
[8, 9, 3, 1, 4, 7, 6, 2, 0, 5]
[1, 8, 4, 7, 2, 3, 0, 5, 9, 6]
[9, 1, 3, 5, 0, 8, 6, 4, 2, 7]
[1, 7, 9, 4, 6, 3, 8, 0, 5, 2]
[0, 8, 4, 7, 3, 2, 6, 5, 9, 1]
[1, 7, 8, 9, 6, 5, 0, 4, 3, 2]
[5, 4, 1, 8, 0, 7, 3, 2, 9, 6]
[8, 6, 2, 0, 1, 5, 9, 3, 4, 7]
[5, 7, 4, 9, 0, 3, 6, 2, 1, 8]
[8, 9, 5, 4, 7, 0, 1, 3, 2, 6]
[2, 5, 6, 7, 3, 1, 4, 9, 0, 8]
[0, 7, 8, 2, 6, 5, 9, 1, 3, 4]
[4, 3, 6, 0, 5, 1, 2, 9, 8, 7]
[6, 1, 5, 8, 9, 4, 7, 0, 2, 3]
[9, 4, 0, 2, 5, 6, 3, 8, 7, 1]
[5, 2, 7, 0, 4, 3, 9, 6, 1, 8]
[4, 3, 1, 7, 9, 0, 6, 2, 8, 5]
[5, 8, 6, 1, 4, 9, 2, 0, 7, 3]
[3, 0, 2, 6, 1, 5, 8, 7, 9, 4]
[1, 6, 0, 4, 7, 3, 5, 9, 2, 8]
[5, 8, 6, 0, 2, 4, 7, 3, 9, 1]
[8, 7, 3, 6, 4, 1, 0, 9, 2, 5]
[9, 0, 7, 1, 5, 8, 4, 3, 6, 2]
[0, 4, 9, 7, 8, 1, 6, 5, 2, 3]
[5, 0, 4, 2, 1, 7, 9, 8, 3, 6]
[7, 2, 8, 3, 5, 4, 1, 0, 6, 9]
[2, 6, 4, 8, 0, 5, 9, 7, 1, 3]
[0, 2, 9, 7, 8, 6, 1, 4, 3, 5]
[6, 4, 1, 2, 9, 7, 5, 3, 8, 0]
[3, 2, 4, 0, 5, 9, 8, 1, 6, 7]
[9, 0, 8, 7, 6, 2, 3, 4, 1, 5]
[4, 1, 5, 3, 8, 9, 0, 6, 2, 7]
[8, 5, 6, 0, 2, 4, 7, 3, 1, 9]
[1, 4, 9, 6, 3, 2, 8, 7, 0, 5]
[9, 5, 6, 2, 0, 7, 1, 3, 4, 8]
[1, 8, 3, 6, 4, 5, 7, 0, 9, 2]
[8, 3, 7, 5, 1, 9, 0, 2, 4, 6]
[2, 0, 6, 4, 5, 1, 9, 7, 8, 3]
[9, 6, 1, 2, 4, 8, 3, 5, 7, 0]
[6, 3, 4, 0, 2, 1, 8, 9, 5, 7]
[2, 9, 1, 3, 5, 6, 4, 8, 7, 0]
[3, 5, 7, 1, 6, 0, 8, 9, 4, 2]

BackOff重试算法

可以使用斐波那契数列计算重试时间,也可以使用指数补偿计算重试时间。

定义一个接口

@FunctionalInterface
public interface ExponentialBackOffFunction <T> {
	T execute();
}

定义重试工具类

import static java.util.Arrays.asList;

import java.net.SocketTimeoutException;
import java.util.List;

import javax.net.ssl.SSLHandshakeException;

import lombok.extern.log4j.Log4j;

@Log4j
public final class ExponentialBackOff {
	
	private static final int[] FIBONACCI = new int[] { 1, 1, 2, 3, 5, 8, 13 };
	private static final List<Class<? extends Exception>> EXPECTED_COMMUNICATION_ERRORS = asList(
			SSLHandshakeException.class, SocketTimeoutException.class);

	private ExponentialBackOff() {
	}

	// E(c) = Math.pow(2, c) - 1
	// 考虑到补偿时间的均匀分布,补偿时间的数学期望是所有可能性的平均值。
	// 也就是说,在c次冲突之后,补偿时隙数量在 [0,1,...,N] 中,其中 [公式] E(c) = Math.pow(2, c) - 1
	// 则补偿时间的数学期望 E(c) = (Math.pow(2, c) - 1)/2
	public static long getWaitTimeExponential(int attempt) {
		double waitTime = (Math.pow(2, attempt) - 1) / 2;
		return Math.round(waitTime * 100);
	}
	
	// 这个地方使用斐波那契数去增加重试时间
	public static long getWaitTimeDefault(int attempt) {
		return FIBONACCI[attempt] * 100;
	}

	public static <T> T execute(ExponentialBackOffFunction<T> fn) {
		for (int attempt = 0; attempt < FIBONACCI.length; attempt++) {
			try {
				return fn.execute();
			} catch (Exception e) {
				handleFailure(attempt, e);
			}
		}
		throw new RuntimeException("Failed to communicate.");
	}

	private static void handleFailure(int attempt, Exception e) {
		if (e.getCause() != null && !EXPECTED_COMMUNICATION_ERRORS.contains(e.getCause().getClass()))
			throw new RuntimeException(e);
		doWait(attempt);
	}

	private static void doWait(int attempt) {
		try {
			long sleepTime = getWaitTimeExponential(attempt);
			System.out.println("attempt " + attempt + " sleep " + sleepTime);
			Thread.sleep(sleepTime);
		} catch (InterruptedException e) {
			throw new RuntimeException(e);
		}
	}
}

测试案例

public class Test {
	public static void main(String[] args) {
		ExponentialBackOff.execute(new Work());
	}
}

class Work implements ExponentialBackOffFunction<String> {

	@Override
	public String execute() {
		int a = 5 / 0;
		return a + "";
	}
}

运行结果

使用指数补偿:
attempt 0 sleep 0
attempt 1 sleep 50
attempt 2 sleep 150
attempt 3 sleep 350
attempt 4 sleep 750
attempt 5 sleep 1550
attempt 6 sleep 3150
使用斐波那契数列
attempt 0 sleep 100
attempt 1 sleep 100
attempt 2 sleep 200
attempt 3 sleep 300
attempt 4 sleep 500
attempt 5 sleep 800
attempt 6 sleep 1300

微服务编排框架

发现一个优秀的微服务编排框架:zeebe

微服务核心研究之–编排

当一个系统采用了微服务架构后,会拆分成很多新的微服务,但原有的业务可能还是没有变化,如何在微服务架构下实现原有的业务?相对于传统架构,微服务架构下更需要通过各微服务之间的协作来实现一个完整的业务流程,可以说服务编排是微服务架构下的必备技能。但是,编排涉及到RPC、分布式事务等等,编排的质量不能仅仅取决于老师傅的手艺,需要有完善的编排框架来支撑。

关于微服务的组合(协调):
编制(Orchestration)—— 面向可执行的流程:通过一个可执行的流程来协同内部及外部的服务交互。通过中心流程来控制总体的目标,涉及的操作,服务调用顺序。
编排(Choreography)—— 面向合作:通过消息的交互序列来控制各个部分资源的交互。参与交互的资源都是对等的,没有集中的控制。

哲学家就餐问题 [go/java 实现练习并发编程]

java

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.locks.ReentrantLock;

class Philosopher implements Runnable{
	private final String name;
	private final ReentrantLock left;
	private final ReentrantLock right;
	private final AtomicInteger hunger = new AtomicInteger(3);
	public Philosopher(String name, ReentrantLock left, ReentrantLock right) {
		this.name = name;
		this.left = left;
		this.right = right;
	}
	@Override
	public void run() {
		while (this.hunger.get() > 0) {
			System.out.println(name + " Hungry");
			this.left.lock();
			this.right.lock();
			System.out.println(name + " Eating");
			try {
				Thread.sleep(500);
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
			this.right.unlock();
			this.left.unlock();
			System.out.println(name + " Thinking");
			this.hunger.decrementAndGet();
			try {
				Thread.sleep(500);
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
		}
	}	
}

public class DiningPhilosopher {
	public static void main(String[] args) {
		ExecutorService executor = Executors.newCachedThreadPool();
		String[] philosophers = new String[] {"Mark", "Russell", "Rocky", "Haris", "Root"};
		ReentrantLock fork0 = new ReentrantLock();
		ReentrantLock forkLeftLock = fork0;
		List<Philosopher> philosopherList = new ArrayList<Philosopher>();
		for(int i=1;i<philosophers.length;i++) {
			String name = philosophers[i];
			ReentrantLock forkRightLock = new ReentrantLock();
			philosopherList.add(new Philosopher(name, forkLeftLock, forkRightLock));
			forkLeftLock = forkRightLock;
		}
		philosopherList.add(new Philosopher(philosophers[0], fork0, forkLeftLock));
		for (Philosopher philosopher : philosopherList) {
			executor.submit(philosopher);
		}
		executor.shutdown();
	}
}

go

package main

import (
	"hash/fnv"
	"log"
	"math/rand"
	"os"
	"sync"
	"time"
)

// 初始化5个人
var ph = []string{"Mark", "Russell", "Rocky", "Haris", "Root"}

const hunger = 3                // 每个哲学家吃几次饭
const think = time.Second / 100 // 思考时间
const eat = time.Second / 100   // 吃饭时间

var fmt = log.New(os.Stdout, "", 0)

var dining sync.WaitGroup

func diningProblem(phName string, dominantHand, otherHand *sync.Mutex) {
	fmt.Println(phName, "Seated")
	h := fnv.New64a()
	h.Write([]byte(phName))
	rg := rand.New(rand.NewSource(int64(h.Sum64())))
	rSleep := func(t time.Duration) {
		time.Sleep(t/2 + time.Duration(rg.Int63n(int64(t))))
	}
	for h := hunger; h > 0; h-- {
		fmt.Println(phName, "Hungry")
		dominantHand.Lock() // 获取资源
		otherHand.Lock()
		fmt.Println(phName, "Eating")
		rSleep(eat)
		dominantHand.Unlock() // 释放资源
		otherHand.Unlock()
		fmt.Println(phName, "Thinking")
		rSleep(think)
	}
	fmt.Println(phName, "Satisfied")
	dining.Done()
	fmt.Println(phName, "Left the table")
}

func main() {
	fmt.Println("Table empty")
	dining.Add(5)
	fork0 := &sync.Mutex{}
	forkLeft := fork0
	for i := 1; i < len(ph); i++ {
		forkRight := &sync.Mutex{}
		go diningProblem(ph[i], forkLeft, forkRight)
		forkLeft = forkRight
	}
	go diningProblem(ph[0], fork0, forkLeft)
	dining.Wait() // 等待结束
	fmt.Println("Table empty")
}