Andorid端基于圖的啟動(dòng)框架解決方案

1.背景

1.1 在日常開發(fā)時(shí)經(jīng)常會(huì)在Application的onCreate()方法中對(duì)三方SDK，或者自己封裝的SDK進(jìn)行初始化。

class Application{
   ...
   
    onCreate(){
         initSDKA();
         initSDKB();
         initSDKC();
         ....
    }
    
    ...
}

上面是通常寫法，這里總結(jié)了幾個(gè)信息點(diǎn)

1. 初始化耗時(shí)。整體都在主線程一條線程初始化。部分機(jī)型無法充分利用cpu資源。
2. SDK依賴。部分sdk 存在順序依賴關(guān)系。比如SDKB用到了SDKA 中的服務(wù)。這時(shí)必須保證順序。
3. 代碼開閉原則。對(duì)修改封閉，對(duì)擴(kuò)展開放。如要?jiǎng)h除或者添加一個(gè)SDK，需增加或者刪除對(duì)應(yīng)方法。又或者開發(fā)人員可以隨意刪除，抽取某個(gè)initSDK 方法中的部分內(nèi)容，造成功能的不確定性。

2. 方案解決

2.1 針對(duì)以上總結(jié)的信息點(diǎn)?？梢杂貌⑿卸嗑€程解決耗時(shí)問題。引用指向關(guān)系解決SDK依賴問題。封裝初始化SDK代碼成TASK任務(wù)解決代碼混亂問題。在保證以上條件都成立的情況下，圖論中DAG（有向無環(huán)圖）是剛好符合以上解決問題的數(shù)據(jù)結(jié)構(gòu)。

如何根據(jù)用戶指定的依賴關(guān)系生產(chǎn)有向無環(huán)圖呢？

1. 為了確保遍歷的入口唯一，默認(rèn)在圖中加入根節(jié)點(diǎn)Root
2. 由于可能存在不依賴于任何其他SDK的SDK，而且不止一個(gè)。我們把不依賴于任何sdk 的TASK節(jié)點(diǎn)掛載在Root下。
3. 把有依賴關(guān)系的Task掛在對(duì)應(yīng)依賴的Task后繼幾點(diǎn)后面

假如有如下依賴關(guān)系

1. A,C 不依賴任何其他節(jié)點(diǎn)
2. B依賴于A。E依賴于A，C。D依賴于B，C。

根據(jù)上述依賴關(guān)系，會(huì)生成如下圖的有向圖。

生成圖后，把后繼節(jié)點(diǎn)為空的節(jié)點(diǎn)指向尾節(jié)點(diǎn)，如 圖3->圖4。保證了圖的完整以及出口的唯一，遍歷時(shí)作為圖遍歷結(jié)束的最后一個(gè)節(jié)點(diǎn)

生成圖的過程

TaskNode節(jié)點(diǎn)

public abstract class TaskNode implements Runnable,ITask {

        public short inDegree; // 當(dāng)前 Task 在有向圖中的入度，用于判斷圖中是否有環(huán)
        HashSet<TaskNode> nextList = new HashSet<>(); // 后繼節(jié)點(diǎn)
        List<TaskNode> depended = new ArrayList<>(); 

        OnTaskResult onTaskResult;
}

根據(jù)依賴關(guān)系生成圖

    /**
     * 生成有向圖
    */
    private void generateGraph() {
        for (TaskNode taskNode : taskNodes) {
            // 如果該節(jié)點(diǎn)沒有任何依賴關(guān)系，則直接掛載在 root 下
            if (getPreNodes(taskNode) == null || getPreNodes(taskNode).size() == 0) {
                root.nextList.add(taskNode);
                // 計(jì)算入度
                taskNode.inDegree = 1;
            } else {
                short inDegree = 0;
                List<TaskNode> taskNodeList = getPreNodes(taskNode);
                // 如果該節(jié)點(diǎn)有依賴關(guān)系，則掛載在依賴的Task 之后
                for (TaskNode preNode : taskNodeList) {
                    preNode.nextList.add(taskNode);
                    inDegree++;
                }
                // 計(jì)算入度
                taskNode.inDegree = inDegree;
            }
        }
    }

    /**
     * 獲取該節(jié)點(diǎn)依賴的節(jié)點(diǎn)的集合
     * @param taskNode
     * @return
     */
    private List<TaskNode> getPreNodes(TaskNode taskNode) {
        if (taskNode.depended.isEmpty()) {
            return null;
        }
        List<TaskNode> taskNodeList = new ArrayList<>();
        for (TaskNode clazz : taskNode.depended) {
            taskNodeList.add(node);
        }
        return taskNodeList;
    }

2.2 判斷圖中是否有環(huán)

2.2.1拓補(bǔ)排序的特性

如果圖中有環(huán)，Task之間存在循環(huán)依賴，會(huì)造成遍歷無法結(jié)束，尾節(jié)點(diǎn)無法添加。

在圖論中，拓?fù)渑判蚴且粋€(gè)有向無環(huán)圖（DAG）的所有頂點(diǎn)的線性序列。且該序列必須滿足下面兩個(gè)條件：

1. 每個(gè)頂點(diǎn)出現(xiàn)且只出現(xiàn)一次。
2. 若存在一條從頂點(diǎn) A 到頂點(diǎn) B 的路徑，那么在序列中頂點(diǎn) A 出現(xiàn)在頂點(diǎn) B 的前面。

那也就意味著如果一個(gè)圖的拓補(bǔ)排序無法輸出所有頂點(diǎn)，那么這個(gè)圖中必定存在環(huán)，或者循環(huán)依賴。

2.2.2拓補(bǔ)排序的算法實(shí)現(xiàn)

1. 從 DAG 圖中選擇一個(gè) 沒有前驅(qū)（即入度為0）的頂點(diǎn)并輸出，同時(shí)把該節(jié)點(diǎn)的后繼節(jié)點(diǎn)都減1，然后查找后繼節(jié)點(diǎn)中入度為0的節(jié)點(diǎn)，找到后加入臨時(shí)棧中（臨時(shí)棧中都是入度為0的節(jié)點(diǎn)）。上圖4中只有一個(gè)入度0的節(jié)點(diǎn)，就是Root節(jié)點(diǎn)
2. 從臨時(shí)棧中拿到入度為0的節(jié)點(diǎn)彈出元素加入拓補(bǔ)排序集合中，然后重復(fù)步驟1。直到臨時(shí)棧中元素為空。拓補(bǔ)排序結(jié)束

代碼如下

/**
 * 判斷圖中是否有環(huán)
 * 
 */
private void isThereARing() {
    // 臨時(shí)棧，用于存放入度為0的節(jié)點(diǎn)
    Stack<TaskNode> nodeStack = new Stack<>();
    nodeStack.push(root);

    // 存放拓補(bǔ)排序排序的集合
    ArrayList<TaskNode> topologicalSort = new ArrayList<>();
    while (!nodeStack.isEmpty()) {
        TaskNode taskNode = nodeStack.pop();
        topologicalSort.add(taskNode);
        if (taskNode.nextList.size() != 0) {
            for (TaskNode nextNode : taskNode.nextList) {
                // 當(dāng)前節(jié)點(diǎn)指向下一節(jié)點(diǎn)，將下一節(jié)點(diǎn)的入度 減1
                nextNode.inDegree--;
                // 如果下一節(jié)點(diǎn)的入度是0，將入度為 0 的節(jié)點(diǎn)入棧，用于下一次遍歷
                if (nextNode.inDegree == 0) {
                    nodeStack.push(nextNode);
                }
            }
        }
    }

    // 拋出異常中斷程序異常信息中提示 存在環(huán)的相關(guān) Task
    if (taskCount != topologicalSort.size()) {
        taskNodes.removeAll(topologicalSort);
        StringBuilder builder = new StringBuilder();
        builder.append(" [");
        for (TaskNode taskNode : taskNodes) {
            builder.append(taskNode.getClass().getSimpleName());
            builder.append(",");
        }
        builder.append(" ]");
        throw new RuntimeException("there is a ring among" + builder.toString());
    }
}

拓補(bǔ)排序排序過程

上圖是一個(gè)有向無環(huán)圖，輸出的拖布排序序列為[1,2,4,3,5],如果 3，5 是循環(huán)依賴關(guān)系，則排序只會(huì)輸出[1,2,4]就結(jié)束了。圖中的元素?zé)o法全部遍歷完成。

2.3 多線程遍歷圖

因?yàn)闋砍蹲泳€程初始化任務(wù)，必須確保在跳轉(zhuǎn)第一個(gè)業(yè)務(wù)頁(yè)面時(shí)，所有的Task都初始化完成了。也就是說從遍歷開始到結(jié)束，主線程是不可以跳轉(zhuǎn)到閃屏頁(yè)面的，而且部分初始化會(huì)在主線程進(jìn)行。阻塞主線程就成了必需要做的事。

多線程遍歷

runTask(root); // 開始遍歷
waitMain();

private void runTask(final TaskNode taskNode) {
    // 只有入度為0的節(jié)點(diǎn)才能開始運(yùn)行
    if (taskNode.backupInDegree.get() == 0) {
        // 當(dāng)前Task運(yùn)行完成回掉
        taskNode.setOnTaskResult(new OnTaskResult() {
            @Override
            public void OnTaskEnd(HashSet<TaskNode> nextList) {
                // 遍歷結(jié)束條件，尾節(jié)點(diǎn)遍歷完成
                if (taskNode instanceof TaskTail) {
                    return;
                }
                
                // 尋找下一節(jié)點(diǎn)，嘗試運(yùn)行。
                for (TaskNode nextNode : taskNode.nextList) {
                    // 遞減入度，直到為0的時(shí)候，該Task 才可以執(zhí)行
                    nextNode.backupInDegree.decrementAndGet(); 
                    runTask(nextNode);
                }
            }
        });

        if (taskNode.isMainThread()) {
            // 主線程任務(wù)放入消費(fèi)隊(duì)列，由主線程消費(fèi)
            try {
               // 阻塞隊(duì)列，會(huì)阻塞主線程 
               // blockingQueueMain = new ArrayBlockingQueue<TaskNode>();
               blockingQueueMain.put(taskNode);
            } catch (InterruptedException e) {
               e.printStackTrace();
            }
        } else {
            // 子線程任務(wù)直接由線程池運(yùn)行
            executorService.execute(taskNode);
        }
    }
}

主線程阻塞代碼

/**
 * 遍歷開始時(shí)，主線程阻塞，直到尾節(jié)點(diǎn)遍歷結(jié)束。
 */
private void waitMain() {
    long startTime = SystemClock.uptimeMillis();
    // 超時(shí)邏輯，防止主線程阻塞超時(shí)
    while (SystemClock.uptimeMillis() - startTime < timeOut) {
        try {
            TaskNode taskNode = blockingQueueMain.poll(timeOut, TimeUnit.MILLISECONDS);
            taskNode.run();
            // 到達(dá)尾節(jié)點(diǎn)直接跳出循環(huán)，放開主線程
            if (taskNode instanceof TaskTail) {
                break;
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

遍歷完成，整個(gè)初始化結(jié)束。

3.時(shí)間對(duì)比

1. 不使用圖組織關(guān)系，串行執(zhí)行時(shí)。使用上文提到的A,B,C,D,E， 每個(gè)Task模擬耗時(shí)2s，依賴關(guān)系保持不變。

```
class Application{
   ...
   
    onCreate(){
        new TaskA().run();
        new TaskC().run();
        new TaskB().run();
        new TaskD().run();
        new TaskE().run();
         ....
    }
    
    ...
}
```

2. 使用圖組織依賴關(guān)系，開啟兩個(gè)子線程進(jìn)行遍歷。

TasksManager.getInstance(this).addTask(new TaskA())
              .addTask(new TaskB())
              .addTask(new TaskC())
              .addTask(new TaskC())
              .addTask(new TaskE()).start();

時(shí)間對(duì)比

初始化時(shí)間在實(shí)際項(xiàng)目中也會(huì)因?yàn)橐蕾囮P(guān)系不同造成圖的關(guān)系的不同。最差情況下，所有的Task會(huì)形成一個(gè)鏈表。最好的情況下所有的Task之間沒有依賴關(guān)系。所以優(yōu)化的百分比時(shí)間還要根據(jù)具體的業(yè)務(wù)場(chǎng)景來進(jìn)行比對(duì)總結(jié)。

后續(xù)接入公司項(xiàng)目后，項(xiàng)目中有大概30+ sdk數(shù)量，初始化速度提升大概在30%-40%之間

4.總結(jié)

1. 使用圖的數(shù)據(jù)結(jié)構(gòu)組織SDK之間的關(guān)系，更加合理有效。
2. 多線程遍歷圖。在保證所有SDK在使用前初始化完成，SDK的初始化效率更高。
3. 將SDK的初始化封裝抽象成Task的形式。插拔更加便利，代碼整體性更高，管理SDK更加便利。
4. 后期可以通過添加xml配置文件的形式配置進(jìn)程，線程，依賴關(guān)系的方式配置Task信息。統(tǒng)一管理

項(xiàng)目demo地址