需求分析

兩張?jiān)紨?shù)據(jù)表如下：

station （站點(diǎn)表）

站點(diǎn)表用于記錄所有分拔與網(wǎng)點(diǎn)的信息

route （路徑表）

路由信息的基礎(chǔ)數(shù)據(jù)表练对，用于記錄從當(dāng)前網(wǎng)點(diǎn)（station）前往目前網(wǎng)點(diǎn)（destination_station）的下一網(wǎng)點(diǎn)(next_station)酿联。以及這個(gè)路由的啟動(dòng)狀態(tài)（status ,1，啟動(dòng)究西，2關(guān)閉）

要生成一條完整的路由锄列。為了緩解數(shù)據(jù)庫(kù)壓力图云，加快查詢(xún)速度。決定將原數(shù)據(jù)庫(kù)查詢(xún)更換成純算法實(shí)現(xiàn)邻邮。

解決思跑路

以前實(shí)現(xiàn)是在數(shù)據(jù)庫(kù)中查找竣况，現(xiàn)在想所有數(shù)據(jù)加載到內(nèi)存中，得用數(shù)據(jù)結(jié)構(gòu)與算法筒严，實(shí)現(xiàn)路由查找丹泉。實(shí)現(xiàn)起來(lái)也不復(fù)雜，比起最短路徑或最優(yōu)路徑這個(gè)功能就很簡(jiǎn)單

數(shù)據(jù)結(jié)構(gòu)

public class Station<T> implements Serializable {
    
    private Serializable id;
    private String name;
    private T extra;
    private final Map<Serializable,Path> pathMap = new HashMap<>();
    
    ....getter and setter...
    
    
       /**
     * 連接兩個(gè)station
     * @param destination
     * @param next
     * @param extra
     * @param <E>
     */
    public  <E>  void linkTo(Station destination, Station next, E extra){


        Path p = pathMap.get(destination.getId());
        if(p==null){
            p = new Path<>(this);
        }else{
            detach(destination);
        }


        p.setExtra(extra);
        p.setDestination(destination);
        p.setNext(next);
        pathMap.put(destination.getId(),p);
        Path nextPath = next.getPath(destination);
        if(nextPath==null){
            nextPath = new Path(next);
            nextPath.setDestination(destination);
            next.pathMap.put(destination.getId(),nextPath);
        }
        nextPath.addPrevious(this);
    }

    /**
     * 獲聚首當(dāng)前路是徑
     * @param des
     * @return
     */
    public Path getPath(Station des){
       return pathMap.get(des.getId());
    }



    public void detach(Station des){
        Path path = pathMap.get(des.getId());
        if(path!=null){
            path.removePrevious(this);
        }
        if(path.getPrevious().size()==0) {
            pathMap.remove(des.getId());
        }else{
            path.setNext(null);
        }
    }
}

@Data
public class Path<T> {
    private T extra;
    private Station destination;
    private Station cur;
    private Station next;
    private List<Station> previous = new ArrayList<>();

    public Path(Station cur) {
        this.cur = cur;
    }

    public void addPrevious(Station station){
        if(!previous.contains(station)){
            previous.add(station);
        }
    }

    public void removePrevious(Station station){
        previous.remove(station);
    }

    @Override
    public String toString() {

        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (Station station : previous) {
            sb.append(",");
            sb.append(station.getId());
        }
        sb.append("]");


        return "Path{" +
                " cur=" + cur.getId() +
                ", destination=" + (destination!=null?destination.getId():"") +
                ", next=" + (next!=null ? next.getId():"") +
                ", previous=" + sb.toString() +

                '}';
    }
}

解決并發(fā)問(wèn)題加鎖方案

PathFinder類(lèi)主要是用來(lái)存儲(chǔ)所有站點(diǎn)的集合鸭蛙，以及提供所有路徑想著的操作（可能我要重新命名）摹恨，因?yàn)闃I(yè)務(wù)中要根據(jù)網(wǎng)點(diǎn)id查詢(xún)網(wǎng)點(diǎn)（或路由信息），所以用map來(lái)存儲(chǔ)網(wǎng)點(diǎn)娶视。路徑信息可能隨時(shí)會(huì)出變動(dòng)晒哄，而每段路徑的變動(dòng)，都會(huì)影響到整個(gè)路由肪获。所以我在此處用到了讀寫(xiě)鎖寝凌，每段路徑的變動(dòng)，只會(huì)影響到與其相同終點(diǎn)的路徑孝赫，我讓每個(gè)Station都持有一個(gè)讀鎖和寫(xiě)鎖较木。在做讀取或更改操作時(shí)，我獲取目的結(jié)點(diǎn)上的鎖青柄，并對(duì)其進(jìn)行加鎖操作（這種不鎖全部伐债，只鎖部門(mén)的思想在LongAdapter和ConcurrentMap中都有應(yīng)用）。

@Service
public class PathFinder<T,E> {
    ConcurrentSkipListMap<Serializable,Station<T>> stationMap = new ConcurrentSkipListMap();
    
     public  void link(Station curt, Station des, Station next, E extra){
        if(curt == next){
            throw new IllegalStateException("當(dāng)前網(wǎng)點(diǎn)與下一網(wǎng)點(diǎn)不可以相同");
        }

        ReentrantReadWriteLock.WriteLock lock = des.writeLock();
        lock.lock();
        try {
            /**
             * 驗(yàn)證是否存在死循環(huán)
             */
            List<Path<E>> route = findRoute(next, des);
            for (Path<E> p : route) {
                if(p.getNext()==curt||p.getCur() == curt){
                    throw new IllegalStateException("網(wǎng)點(diǎn)存在死循環(huán)致开。");
                }
            }
            curt.linkTo(des, next, extra);
        }finally {
            lock.unlock();
        }
    }
    
 public List<Path<E>> findRoute(Station begin,Station des){
        int len = 0;

        List<Path<E>> list = new ArrayList<>();
        ReentrantReadWriteLock.ReadLock lock = des.readLock();
        lock.lock();
        try{
            Path p;
            Station station =begin;
          while((p=station.getPath(des))!=null && (station=p.getNext())!=null){
              list.add(p);
              if((len++)==100){
                  throw new IllegalStateException("鏈路太長(zhǎng)峰锁，可能出現(xiàn)死路:"+list);
              }
          }
        }finally {
            lock.unlock();
        }
        return list;
    }
    
    
}

數(shù)據(jù)全加載時(shí)遇到的問(wèn)題

原計(jì)劃是在程序啟動(dòng)時(shí)，加載整張表數(shù)據(jù)喇喉。但測(cè)試之后祖今，2000萬(wàn)條數(shù)據(jù)，加載速度很慢拣技，之少要20分鐘之久千诬。

延遲加載及并行加載

數(shù)據(jù)全加載保證了用戶(hù)訪(fǎng)問(wèn)時(shí)的查詢(xún)速度，以及線(xiàn)程安全等問(wèn)題膏斤。但確增長(zhǎng)系統(tǒng)啟動(dòng)時(shí)間徐绑。

懶加載不影響系統(tǒng)啟動(dòng)時(shí)間。但可能會(huì)帶來(lái)兩個(gè)問(wèn)題：

1. 多線(xiàn)程下數(shù)據(jù)重復(fù)加載問(wèn)題莫辨，比如有幾個(gè)請(qǐng)求同時(shí)請(qǐng)求上海南京的結(jié)點(diǎn)傲茄，可能造成兩個(gè)線(xiàn)程同時(shí)加載數(shù)據(jù)。
2. 可能會(huì)降代查詢(xún)速度沮榜，用戶(hù)第一次請(qǐng)求查詢(xún)某路徑時(shí)盘榨，因?yàn)橐獜臄?shù)據(jù)庫(kù)加載數(shù)據(jù)，可能會(huì)出現(xiàn)延遲蟆融。

• 狀態(tài)控制及加鎖

  為了避免數(shù)據(jù)重復(fù)加載草巡，可以對(duì)每個(gè)接點(diǎn)添加一個(gè)狀態(tài)，表示以此接點(diǎn)為目的接點(diǎn)的數(shù)據(jù)是否已加載型酥，如果未加裁山憨，可以使用tryLock試獲此接點(diǎn)的鎖，如果獲取成功弥喉，則加載數(shù)據(jù)據(jù)郁竟，否則進(jìn)行自旋，不斷獲取加載狀態(tài)由境。一旦數(shù)據(jù)另載成功棚亩，便返回。

• 并行加載
  懶加載是指在在需要數(shù)據(jù)時(shí)再加載數(shù)據(jù)（從數(shù)據(jù)庫(kù)中讀取所有目的網(wǎng)點(diǎn)的數(shù)據(jù)）虏杰，在訪(fǎng)問(wèn)峰值時(shí)讥蟆，會(huì)造成類(lèi)似于緩存的雪崩現(xiàn)像。所以采用預(yù)加載與懶加載并行的方式嘹屯，在程序啟動(dòng)地攻询，另開(kāi)一線(xiàn)程加載數(shù)據(jù)，這樣不會(huì)影響到項(xiàng)目的啟動(dòng)時(shí)間州弟。同時(shí)由于上面的狀判斷及懶加載的方案钧栖，也能在數(shù)據(jù)未能加載完成時(shí)，對(duì)外提供服務(wù)婆翔。

后繼方案

目前2000個(gè)網(wǎng)點(diǎn)拯杠，生成的結(jié)點(diǎn)數(shù)所約500萬(wàn)條，得用jmap查看內(nèi)存發(fā)現(xiàn)啃奴，總共占用內(nèi)存不到一個(gè)G, 如果以后再增加網(wǎng)點(diǎn)數(shù)潭陪，可以考慮LRU策略進(jìn)行淘汰，目前我存儲(chǔ)網(wǎng)點(diǎn)用的的是ConcurrentSkipListMap，如果要實(shí)現(xiàn)LRU策略依溯，可能要換成HashLinkedMap實(shí)現(xiàn)老厌。當(dāng)然我也可以用數(shù)據(jù)分片，不管是LRU或數(shù)據(jù)分片黎炉，都可以利用目的網(wǎng)點(diǎn)對(duì)數(shù)據(jù)進(jìn)行分割枝秤。這要比傳統(tǒng)的那種尋找最小路徑算法簡(jiǎn)單多了（因?yàn)槿绻莻鹘y(tǒng)的圖，我想不到什么好的辦法慷嗜，對(duì)數(shù)據(jù)進(jìn)行分割）淀弹。因?yàn)椴幌朐黾訌?fù)雜性，我只對(duì)該服務(wù)進(jìn)行單節(jié)點(diǎn)部署（多節(jié)點(diǎn)部署要考慮數(shù)據(jù)一致性問(wèn)題庆械，而且當(dāng)前擁有有的服務(wù)器資源也不適做多接點(diǎn)部署）薇溃，以后如果要做接點(diǎn)部署，可以考慮應(yīng)用數(shù)據(jù)一致性算法缭乘，加樂(lè)觀(guān)鎖機(jī)制沐序。

總結(jié)

算法很簡(jiǎn)單，應(yīng)用的技術(shù)也不算太復(fù)雜忿峻，關(guān)鍵是選擇合適的方案來(lái)解決當(dāng)前的問(wèn)題薄啥。