sofa - rpc 폴 링 알고리즘 총화

26018 단어 sofa-rpc
sofa 폴 링 알고리즘 총화
유형
알고리즘 이름
묘사 하 다.
RandomLoadBalancer
부하 균형 랜 덤 알고리즘
LocalPreferenceLoadBalancer
로 컬 우선 순위 랜 덤 알고리즘
ConsistentHashLoadBalancer
일치 성 hash 알고리즘
RoundRobinLoadBalancer
폴 링 알고리즘
WeightRoundRobinLoadBalancer
폴 링 알고리즘
부하 균형 랜 덤 알고리즘
public class RandomLoadBalancer extends AbstractLoadBalancer {
    private final Random random = new Random();

    public RandomLoadBalancer(ConsumerBootstrap consumerBootstrap) {
        super(consumerBootstrap);
    }

    public ProviderInfo doSelect(SofaRequest invocation, List providerInfos) {
        ProviderInfo providerInfo = null;
        int size = providerInfos.size();
        int totalWeight = 0;
        boolean isWeightSame = true;

        int offset;
        int i;
        for(offset = 0; offset < size; ++offset) {
            i = this.getWeight((ProviderInfo)providerInfos.get(offset));
            totalWeight += i;
            if (isWeightSame && offset > 0 && i != this.getWeight((ProviderInfo)providerInfos.get(offset - 1))) {
                isWeightSame = false;
            }
        }

        if (totalWeight > 0 && !isWeightSame) {
            offset = this.random.nextInt(totalWeight);

            for(i = 0; i < size; ++i) {
                offset -= this.getWeight((ProviderInfo)providerInfos.get(i));
                if (offset < 0) {
                    providerInfo = (ProviderInfo)providerInfos.get(i);
                    break;
                }
            }
        } else {
            providerInfo = (ProviderInfo)providerInfos.get(this.random.nextInt(size));
        }

        return providerInfo;
    }
}
  • 가중치 계산 방식 은 정리 할 가치 가 있 고 전체적인 가중치 에 따라 무 작위 가중치 를 얻 을 수 있다.
  • 그리고 채널 을 옮 겨 다 니 며 무 작위 가중치 offset 에서 현재 가중치 를 뺀 다.
  • 예전 에 가중치 수량 에 따라 반복 채널 을 List 에 넣 었 고 무 작위 Array List 의 index 는 너무 무 거 웠 다.
  • 예전 에 문자 채널 은 가중치 구간 에 따라 채널 from Offset, toOffset 를 정 의 했 는데 위의 이 알고리즘 과 비슷 했다.offset 도 List 의 0 채널 누적
  • 폴 링 알고리즘
    @Extension("roundRobin")
    public class RoundRobinLoadBalancer extends AbstractLoadBalancer {
        private final ConcurrentMap sequences = new ConcurrentHashMap();
    
        public RoundRobinLoadBalancer(ConsumerBootstrap consumerBootstrap) {
            super(consumerBootstrap);
        }
    
        public ProviderInfo doSelect(SofaRequest request, List providerInfos) {
            String key = this.getServiceKey(request);
            int length = providerInfos.size();
            PositiveAtomicCounter sequence = (PositiveAtomicCounter)this.sequences.get(key);
            if (sequence == null) {
                this.sequences.putIfAbsent(key, new PositiveAtomicCounter());
                sequence = (PositiveAtomicCounter)this.sequences.get(key);
            }
    
            return (ProviderInfo)providerInfos.get(sequence.getAndIncrement() % length);
        }
    
        private String getServiceKey(SofaRequest request) {
            StringBuilder builder = new StringBuilder();
            builder.append(request.getTargetAppName()).append("#").append(request.getMethodName());
            return builder.toString();
        }
    }
    
    
    
    public class PositiveAtomicCounter {
        private static final int MASK = 2147483647;
        private final AtomicInteger atom = new AtomicInteger(0);
    
        public PositiveAtomicCounter() {
        }
    
        public final int incrementAndGet() {
            return this.atom.incrementAndGet() & 2147483647;
        }
    
        public final int getAndIncrement() {
            return this.atom.getAndIncrement() & 2147483647;
        }
    
        public int get() {
            return this.atom.get() & 2147483647;
        }
    }
    
    
  • 윤 문의 핵심 사상 은 바로 AtomicInteger 가 증 가 했 고 그 다음 에 채널 size 와 나머지 를 취 하 는 것 이다.
  • PositiveAtomicCounter 는 가장 대체적인 연산 과 연산 을 가 입 했 고 연산 의 목적 은 Max 값 을 초과 하지 않 는 것 이다.

  • 로 컬 우선 순위 랜 덤 알고리즘
    
    @Extension("localPref")
    public class LocalPreferenceLoadBalancer extends RandomLoadBalancer {
        public LocalPreferenceLoadBalancer(ConsumerBootstrap consumerBootstrap) {
            super(consumerBootstrap);
        }
    
        public ProviderInfo doSelect(SofaRequest invocation, List providerInfos) {
            String localhost = SystemInfo.getLocalHost();
            if (StringUtils.isEmpty(localhost)) {
                return super.doSelect(invocation, providerInfos);
            } else {
                List localProviderInfo = new ArrayList();
                Iterator i$ = providerInfos.iterator();
    
                while(i$.hasNext()) {
                    ProviderInfo providerInfo = (ProviderInfo)i$.next();
                    if (localhost.equals(providerInfo.getHost())) {
                        localProviderInfo.add(providerInfo);
                    }
                }
    
                if (CommonUtils.isNotEmpty(localProviderInfo)) {
                    return super.doSelect(invocation, localProviderInfo);
                } else {
                    return super.doSelect(invocation, providerInfos);
                }
            }
        }
    }
    
    

    일치 성 hash 알고리즘 (값 학습)
  • 물론 모든 것 이 완벽 할 수 없습니다. 일치 성 Hash 알고리즘 은 일반적인 나머지 Hash 알고리즘 보다 신축성 이 있 지만 그 알고리즘 의 실현 도 더욱 복잡 합 니 다. 본 고 는 자바 코드 를 어떻게 이용 하여 일치 성 Hash 알고리즘 을 실현 하 는 지 연구 하고 자 합 니 다.시작 하기 전에 일치 성 Hash 알고리즘 중의 몇 가지 핵심 문 제 를 탐구 합 니 다.
  • 알고리즘 의 구체 적 인 원 리 는 여기에 다시 붙인다.
             2^32    (         Hash ),       Hash (    [0, 2^32-1])           Hash  ,
            Key      Hash (     [0, 232-1]),
        Hash           Key  Hash         ,  Key         。
    
  • 모든 node 의 hash 값 이 [0, 2 ^ 32 - 1] 인 것 을 이해 하고 하나의 링 모양 을 유지 하기 위해 hash 는 데이터 구 조 를 질서 있 게 저장 하여 hash 값 과 NodeObject 의 매 핑 을 형성 해 야 합 니 다.우 리 는 TreeHash 를 선택 하고 빨간색 과 검은색 나 무 를 사용 하면 찾 는 시간 복잡 도 를 O (logN) 로 낮 출 수 있 으 며 위의 두 가지 해결 방안 보다 효율 이 크게 향상 된다.
  • Hash 의 계산 은 링 에 고 르 게 분포 하 는 필수 조건 이다.예 를 들 어 FNV 132_HASH 알고리즘 은 계산 효율 이 좀 높 아 집 니 다.
  • 가상 노드 를 추가 하여 HashServer 의 분 포 를 향상 시킨다.
  • 
    
    /**
     *    hash  ,     (    )        
     *
     * @author GengZhang
     */
    @Extension("consistentHash")
    public class ConsistentHashLoadBalancer extends AbstractLoadBalancer {
    
        /**
         * {interface#method : selector}
         */
        private ConcurrentMap<String, Selector> selectorCache = new ConcurrentHashMap<String, Selector>();
    
        /**
         *     
         *
         * @param consumerBootstrap        
         */
        public ConsistentHashLoadBalancer(ConsumerBootstrap consumerBootstrap) {
            super(consumerBootstrap);
        }
    
        @Override
        public ProviderInfo doSelect(SofaRequest request, List<ProviderInfo> providerInfos) {
            String interfaceId = request.getInterfaceName();
            String method = request.getMethodName();
            String key = interfaceId + "#" + method;
            int hashcode = providerInfos.hashCode(); //            
            Selector selector = selectorCache.get(key);
            if (selector == null //     
                ||
                selector.getHashCode() != hashcode) { //           
                selector = new Selector(interfaceId, method, providerInfos, hashcode);
                selectorCache.put(key, selector);
            }
            return selector.select(request);
        }
    
        /**
         *    
         */
        private static class Selector {
    
            /**
             * The Hashcode.
             */
            private final int                         hashcode;
    
            /**
             * The Interface id.
             */
            private final String                      interfaceId;
    
            /**
             * The Method name.
             */
            private final String                      method;
    
            /**
             *     
             */
            private final TreeMap<Long, ProviderInfo> virtualNodes;
    
            /**
             * Instantiates a new Selector.
             *
             * @param interfaceId the interface id
             * @param method      the method
             * @param actualNodes the actual nodes
             */
            public Selector(String interfaceId, String method, List<ProviderInfo> actualNodes) {
                this(interfaceId, method, actualNodes, actualNodes.hashCode());
            }
    
            /**
             * Instantiates a new Selector.
             *
             * @param interfaceId the interface id
             * @param method      the method
             * @param actualNodes the actual nodes
             * @param hashcode    the hashcode
             */
            public Selector(String interfaceId, String method, List<ProviderInfo> actualNodes, int hashcode) {
                this.interfaceId = interfaceId;
                this.method = method;
                this.hashcode = hashcode;
                //         (    provider   128     ,      )
                this.virtualNodes = new TreeMap<Long, ProviderInfo>();
                int num = 128;
                for (ProviderInfo providerInfo : actualNodes) {
                    for (int i = 0; i < num / 4; i++) {
                        byte[] digest = HashUtils.messageDigest(providerInfo.getHost() + providerInfo.getPort() + i);
                        for (int h = 0; h < 4; h++) {
                            long m = HashUtils.hash(digest, h);
                            virtualNodes.put(m, providerInfo);
                        }
                    }
                }
            }
    
            /**
             * Select provider.
             *
             * @param request the request
             * @return the provider
             */
            public ProviderInfo select(SofaRequest request) {
                String key = buildKeyOfHash(request.getMethodArgs());
                byte[] digest = HashUtils.messageDigest(key);
                return selectForKey(HashUtils.hash(digest, 0));
            }
    
            /**
             *         hash key
             *
             * @param args the args
             * @return the string
             */
            private String buildKeyOfHash(Object[] args) {
                if (CommonUtils.isEmpty(args)) {
                    return StringUtils.EMPTY;
                } else {
                    return StringUtils.toString(args[0]);
                }
            }
    
            /**
             * Select for key.
             *
             * @param hash the hash
             * @return the provider
             */
            private ProviderInfo selectForKey(long hash) {
                Map.Entry<Long, ProviderInfo> entry = virtualNodes.ceilingEntry(hash);
                if (entry == null) {
                    entry = virtualNodes.firstEntry();
                }
                return entry.getValue();
            }
    
            /**
             * Gets hash code.
             *
             * @return the hash code
             */
            public int getHashCode() {
                return hashcode;
            }
        }
    }
    
    
    
    
  • Selector 구조 방법 은 ServerNode 와 virtualNode 방법, 128 개의 node 인 자 를 추가 하 는 것 이다.
  • selectForKey 방법 은 현재 key 보다 큰 맵 을 얻 고 첫 번 째 맵 을 가 져 옵 니 다.

  • 응용 장면
  • 문제
  • 부하 경로 알고리즘 입 니 다. ServerNode 가 신축 할 때 모든 요청 경로 변 화 를 일 으 킬 수 있 기 때문에 라 이브 러 리 의 지속 적 인 데이터 조회 에 적합 하지 않 습 니 다.
  • 요청 경로, cache 등 디자인 장면 을 조회 하기에 적합 하 다.
  • 참조https://blog.csdn.net/u010412301/article/details/52441400
  • 좋은 웹페이지 즐겨찾기