Оригинал: Miss Sister Taste (идентификатор публичной учетной записи WeChat: xjjdog), добро пожаловать, пожалуйста, сохраните источник для перепечатки.
С приближением Нового года рекрутеры и соискатели заняты друг другом.
Сегодняшний день отличается от прошлого, продажа несчастных стала основной мелодией, и это также усугубило беспокойство практикующих. Многим людям, не прикасавшимся к алгоритму более десяти лет, приходится читать его, словно сидя на корточках в кабинете.
Вуху.
Недавно я общался со многими небольшими партнерами, участвовавшими в интервью, и обнаружил, что появилась проблема с относительно высокочастотным алгоритмом. В отличие от связанного списка, дерева, динамического программирования и других задач с обычными алгоритмами, алгоритм взвешенного опроса имеет много мелких навыков, и многие из них используются в практических приложениях. Самый плавный алгоритм опроса Nginx, если вы его не видели, то никогда не сможете его написать.
Алгоритм так называемого взвешенного кругового перебора на самом деле является взвешенным круговым перебором, или сокращенно wrr. Когда мы настраиваем апстрим Nginx, то опрос с весом на самом деле wrr.
upstream backend {
ip_hash;
server 192.168.1.232 weight=4;
server 192.168.1.233 weight=3;
server 192.168.1.234 weight=1;
}
1. Основные структуры данных
Чтобы облегчить кодирование, для каждой запланированной единицы мы абстрагируем класс под названием Element. в,peerОтносится к определенным запланированным ресурсам, таким как IP-адреса, в то время какweightОтносится к относительному весу этого ресурса.
public class Element {
protected String peer;
protected int weight;
public Element(String peer, int weight){
this.peer = peer;
this.weight = weight;
}
}
Тогда наш конкретный интерфейс планирования будет напрямую возвращать адрес однорангового узла.
public interface IWrr {
String next();
}
Мы проверим планирование интерфейса IWrr непосредственно в коде. Например, тестовый код для назначения трех ресурсов с весами 7, 2 и 1 выглядит следующим образом.
Element[] elements = new Element[]{
new Element("A", 7),
new Element("B", 2),
new Element("C", 1),
};
int count = 10;
IWrr wrr = new WrrSecurityLoopTreeMap(elements);
for (int i = 0; i < count; i++) {
System.out.print(wrr.next() + ",");
}
System.out.println();
Приведенный выше код вызывает интерфейс 10 раз, и мы надеемся, что код будет отправлен в соотношении 7, 2 и 1.
2. Версия со случайным числом
Самый простой способ сделать это — использовать случайные числа. Конечно, только когда объем запросов относительно велик, случайное распределение будет приближаться к соотношению 7, 2 и 1. Обычно это не проблема.Например, компонент SpringCloud Robion использует случайный опрос.
Сначала мы вычисляем общее значение веса, обозначаемое какtotal, а затем каждый вызов берет случайное число в общем интервале, а затем по очереди проходит все данные веса.
Временная сложность следующего метода составляет O(n) в худшем случае.
Порядок вызовов, полученный при случайном планировании, также является случайным, что удобно для таких сценариев, как опрос узла микрослужбы. Но для некоторых сервисов с относительно небольшим объемом вызовов некоторые узлы могут умереть от голода, ведь это случайные числа.
public class WrrRnd implements IWrr {
final int total;
final Element[] elements;
final Random random = new SecureRandom();
public WrrRnd(Element[] elements) {
this.total = Arrays.stream(elements)
.mapToInt(ele -> ele.weight)
.sum();
this.elements = elements;
}
@Override
public String next() {
final int n = elements.length;
int index = n - 1;
int hit = random.nextInt(total);
for(int i = 0; i < n; i++){
if(hit >= 0) {
hit -= elements[i].weight;
}else{
index = i - 1;
break;
}
}
return elements[index].peer;
}
}
3. Инкрементная версия
Случайные числа в основном хороши, но иногда нам действительно нужны очень точные результаты планирования. В этом случае обычно используется счетчик с атомарным увеличением для хранения текущего количества расписаний.
Итак, логика относительно ясна, мы можем напрямую использовать атомарный класс для реализации этого счетчика.
Код аналогичен приведенному выше, за исключением того, что при получении переменной попадания мы заменяем метод получения случайных чисел на метод самоинкрементирования.
//原来的
int hit = random.nextInt(total);
настоящее время. Конечно, у него также есть небольшая проблема, то есть значение int, вероятно, будет израсходовано Эта небольшая проблема исправлена в следующем коде.
int hit = count.getAndIncrement() % total;
4. Красно-черная версия дерева
Будь то случайное число или опрос по порядку, их временная сложность относительно высока, потому что каждый раз необходимо проходить все элементы конфигурации, пока не будет достигнуто нужное нам значение. Чтобы повысить эффективность работы, мы можем использовать TreeMap Java для обмена временем в пространстве.
Ниже представлена поточно-безопасная версия реализации, использующая физическое хранилище для решения проблемы временных затрат. Нижний слой TreeMap представляет собой красно-черное дерево, в котором реализована функция сортировки по размеру ключа, его средняя временная сложность равна log(n).
Мы напрямую конвертируем логику приведенного выше кода в хранилище TreeMap, мы можем передатьceilingEntryметод для получения самой последней единицы планирования.
При параллелизме примитив CAS используется напрямую. В настоящее время мы больше не используем автоинкремент, но строго контролируем максимальное значение ниже общего и разрешаем конфликты с помощью прокрутки.
public class WrrSecurityLoopTreeMap implements IWrr {
final int total;
final AtomicInteger count = new AtomicInteger();
final TreeMap<Integer, Element> pool = new TreeMap<>();
public WrrSecurityLoopTreeMap(Element[] elements) {
int total = 0;
for (Element ele : elements) {
total += ele.weight;
pool.put(total - 1, ele);
}
this.total = total;
}
@Override
public String next() {
final int modulo = total;
for (; ; ) {
int hit = count.get();
int next = (hit + 1) % modulo;
if (count.compareAndSet(hit, next) && hit < modulo) {
return pool.ceilingEntry(hit).getValue().peer;
}
}
}
}
5. Версия ЛВС
Вышеупомянутые версии (кроме random) имеют одну из самых больших проблем, то есть планирование не сбалансировано. Когда наше отношение равно 7, 2, 1, его результат планированияA,A,A,A,A,A,A,B,B,C,.
Мы надеемся, что планирование может быть более плавным, а не нажимать на узел A сразу. Ниже приведен алгоритм в коде LVS, который использует наибольший общий делитель для реализации опроса. Хотя он не может обеспечить очень плавный опрос, он, по крайней мере, намного сильнее, чем код автоинкремента выше.
Процесс выполнения этого кода состоит из двух частей: одна — вычисление наибольшего общего делителя НОД, а другая — алгоритм опроса.
Для весов 7, 2 и 1 результатом планирования являетсяA,A,A,A,A,A,B,A,B,C,, по сравнению со способом последовательного опроса есть некоторые улучшения. Когда значения веса этих узлов схожи, версия LVS покажет лучший эффект балансировки нагрузки.
Сначала мы вычисляем НОД наибольшего общего делителя в конструкторе. Затем на основе этого наибольшего общего делителя выполняется работа алгоритма опроса.
По введенному адресу легко записывается соответствующий алгоритм.
http://kb.linuxvirtualserver.org/wiki/Weighted_Round-Robin_Scheduling
Ниже приведен конкретный код.
public class WrrGcd implements IWrr {
final int gcd;
final int max;
final Element[] elements;
public WrrGcd(Element[] elements) {
Integer gcd = null;
int max = 0;
for (Element ele : elements) {
gcd = gcd == null ? ele.weight : gcd(gcd, ele.weight);
max = Math.max(max, ele.weight);
}
this.gcd = gcd;
this.max = max;
this.elements = elements;
}
int i = -1;
int cw = 0;
@Override
public String next() {
for (; ; ) {
final int n = elements.length;
i = (i + 1) % n;
if (i == 0) {
cw = cw - gcd;
if (cw <= 0) {
cw = max;
if (cw == 0) {
return null;
}
}
}
if(elements[i].weight >= cw){
return elements[i].peer;
}
}
}
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}
6. Версия Nginx
Эта версия nginx выводит его на новый уровень и позволяет достичьA,A,B,A,A,C,A,A,B,A,Эффект. С целью обеспечения точного веса вызовы максимально рассредоточены.
Этот алгоритм относительно изобретателен, и можно сказать, что это очень гениальный алгоритм. Если вы не коснулись этого, вы не можете написать это.
Хотя алгоритм относительно прост, доказать его точность непросто. Конкретный процесс сертификации можно найти по следующей ссылке.
https://tenfy.cn/2018/11/12/smooth-weighted-round-robin/
Глядя на наш код, мы инкапсулируем класс с именем Wrr. Этот класс добавляет текущее значение веса к исходному весу. current будет меняться при каждом вызове.
В каждом раунде вызовов значение веса соответствующего узла добавляется к текущему, а затем узел с наибольшим текущим значением выбирается в качестве узла планирования для этого раунда.
Выбранный узел вычтет все значения веса из суммы, а затем перейдет к следующему планированию. Единственная проблема заключается в том, что когда узлов много, его временная сложность всегда равна O(n), и эффективность выполнения нужно обесценивать.
public class WrrSmooth implements IWrr {
class Wrr {
Element ele;
int current = 0;
Wrr(Element ele){
this.ele = ele;
}
}
final Wrr[] cachedWeights;
public WrrSmooth(Element[] elements) {
this.cachedWeights = Arrays.stream(elements)
.map(Wrr::new)
.collect(Collectors.toList())
.toArray(new Wrr[0]);
}
@Override
public String next() {
int total = 0;
Wrr shed = cachedWeights[0];
for(Wrr item : cachedWeights){
int weight = item.ele.weight;
total += weight;
item.current += weight;
if(item.current > shed.current){
shed = item;
}
}
shed.current -= total;
return shed.ele.peer;
}
}
Эта версия Nginx очень проста в написании. Рекомендуется хорошо его понять и освоить метод записи красно-черного дерева и версию Ningx.
End
Общие интервью на самом деле сосредоточены на случайных числах и инкрементных версиях.Конечно, версия красно-черного дерева также может быть рассмотрена. Что касается этих способов написания LVS и Nginx, то, если вы не сталкивались с ними раньше, вы, вероятно, не сможете их написать, если вы не гений.
Но если ты гений, зачем тебе такое пошлое интервью?
Об авторе:Мисс сестра вкус(xjjdog), публичная учетная запись, которая не позволяет программистам идти в обход. Сосредоточьтесь на инфраструктуре и Linux. Десять лет архитектуры, десятки миллиардов ежедневного трафика, обсуждение с вами мира высокой параллелизма, дающие вам другой вкус. Мой личный WeChat xjjdog0, добро пожаловать в друзья для дальнейшего общения.