Опытные мелочи-10, или «DFS и отказоустойчивость»
Продолжение «опытных мелочей». Предыдущие части можно почитать тут.
Сегодняшний выпуск будет выпуск-обещание. Выполняя то, что обещал, я расскажу как с помощью DFS можно сделать интересную вещь. Это будет, конечно, не полноценная отказоустойчивость файловых данных, но что-то похожее на онлайн-бэкап, как минимум.
Можно построить на базе DFS своего рода онлайн-реплику, которая не будет работать основное время (а значит бОльшая часть проблем с синхронизацией данных не проявится), и которую можно будет включить, в случае отказа основной реплики.
Выглядеть это может например вот так:
Здесь (на примере папки Department) создано две реплики одной папки, настроена группа репликации и задания репликации (все это делается мастером настройки и не вызовет у вас никаких проблем). Самый смак идеи в том, что одна из ссылок на сервера хранилища — отключена, т.е. реплика есть, репликация между серверами проходит как задано, но пользователи, обращающиеся через DFS в эту папку будут перенаправляться исключительно на первый, активный сервер.
Второй сервер будет реплицировать данные по мере возможности, и будет как бы «на подхвате». В случае какой-то нештатной ситуации, можно будет произвести рокировку и включить линк уже на второй сервер, а линк на первый — выключить и пользователи снова попадут к своим родным данным, которые будут настолько актуальны, насколько DFS-репликация была способна сделать (на практике это от полной актуальности, т.е. состояния 0,5-2 сек давности, до 2-3 дней в случае с открытыми файлами, которые не реплицируются пока не будут закрыты, т.е. разблокированы приложением).
Кстати, по словам знающих, в среде Windows Server 2008 (R2) DFS (и особенно ее служба репликации) была кардинально улучшена, и, возможно, часть проблем была успешно решена. Попробуйте — может быть там предложенная схема будет работать куда лучше.
Как настроить Distributed File System (DFS) и Replication в Active Directory
В инструкции описан процесс настройки распределенной файловой системы и репликации данных в домене Active Directory на серверах под управлением Windows Server.
Что это такое?
Наличие общих каталогов для доступа к определенным документам и файлам является важной проблемой в бизнес-среде. Системным администраторам необходимо найти удобное решение для обмена общими данными.
Существует два типа DFS:
Установка
В нашем случае установка производится на контроллер домена.
Откройте панель управления сервером Windows и найдите Add roles and features (Добавить роли и компоненты).
В качестве типа установки укажите Role-based or feature-based installation (Установка ролей и компонентов).
Выберите ваш сервер из пула серверов.
В следующем окне отметьте DFS Namespaces и DFS Replication.
Затем установите выбранные компоненты.
Настройка пространства имен DFS
Прежде, чем перейти к добавлению пространства имен, необходимо создать хотя бы одну сетевую директорию на любом из серверов, добавленных в домен. В данном примере используется созданная на том же контроллере домена папка с общим доступом.
Для предоставления общего доступа к папке достаточно выбрать опцию Общий Доступ (Give access to) при нажатии на папку правой кнопкой мыши и выбрав доменного пользователя или группу пользователей, которым будет предоставлен доступ. В результате будет отображен путь до сетевой папки вида \\MachineName\Folder.
Теперь можно приступить непосредственно к добавлению пространства имен DFS.
Или в поиске введите команду dfsmgmt.msc.
Для создания нового пространства имен выберите в правой части экрана New Namespace.
Введите имя сервера, на которым установлена роль DFS.
Введите любое удобное для вас название. Нажмите кнопку Edit Settings.
В открывшемся окне необходимо настроить права доступа к пространству имен для пользователей сети. Чтобы предоставить полный доступ, нажмите кнопку Customize.
На следующем шаге выберите Domain-based namespace, т.к. используются доменные службы Active Directory (AD DS).
Проверьте конфигурацию и нажмите Create.
В результате вы увидите сообщение об успешном создании пространства имен.
Добавление нового каталога в существующее пространство имен DFS
Чтобы создать каталог в созданном namespace, откройте DFS Management, выберите нужное пространство и справа в вертикальном меню нажмите New Folder.
Введите удобное имя каталога и нажмите Add, для того чтобы связать каталог DFS и созданную ранее сетевую папку на сервере-участнике домена.
Введите имя сетевого каталога и кликнете OK.
Нажмите OK для сохранения изменений.
Подключиться к данному пространству с другого сервера можно набрав в проводнике следующий адрес:
Настройка DFS-репликации на Windows Server
Чтобы настроить репликацию данных, необходимо установить роль DFS Replication на втором добавленном в домен сервере.
Теперь создадим на втором сервере сетевую папку, в которую будут реплицироваться данные из директории, добавленной ранее на контроллер домена.
На сервере пространства имен (в данном случае на Контроллере Домена)откройте DFS Management, выберете нужное пространство и справа в вертикальном меню кликните Add Folder Target.
Введите имя добавленного в домен сервера и созданного на предыдущем шаге сетевого каталога.OK.
Откроется окно с вопросом о создании новой группы репликаций. Нажмите Yes.
Откроется настройщик Replication DFS. Проверьте имя группы репликации и каталога, который вы собираетесь реплицировать.
На следующем шаге проверьте пути сетевых директорий.
Выберите основной узел, с которого данные будут реплицироваться в другие директории, являющиеся частью пространства имен DFS.
На последнем шаге необходимо настроить расписания реплицирования данных. В первом случае репликация производится моментально, во втором можно настроить удобное расписание.
Проверьте настройки и нажмите Create.
В результате вы увидите сообщение об успешном создании группы репликаций.
На данное системное сообщение кликните OK левой кнопкой мыши.
Откройте каталог, в который будет происходить первоначальная репликация данных и нажмите Continue. Произойдет первоначальная репликация данных.
На этом настройка распределенной файловой системы и репликации данных в ней закончена.
P. S. Другие инструкции:
Ознакомиться с другими инструкциями вы можете на нашем сайте. А чтобы попробовать услугу — кликните на кнопку ниже.
Обход графа: поиск в глубину и поиск в ширину простыми словами на примере JavaScript
Доброго времени суток.
Что такое обход графа?
Простыми словами, обход графа — это переход от одной его вершины к другой в поисках свойств связей этих вершин. Связи (линии, соединяющие вершины) называются направлениями, путями, гранями или ребрами графа. Вершины графа также именуются узлами.
Двумя основными алгоритмами обхода графа являются поиск в глубину (Depth-First Search, DFS) и поиск в ширину (Breadth-First Search, BFS).
Несмотря на то, что оба алгоритма используются для обхода графа, они имеют некоторые отличия. Начнем с DFS.
Поиск в глубину
DFS следует концепции «погружайся глубже, головой вперед» («go deep, head first»). Идея заключается в том, что мы двигаемся от начальной вершины (точки, места) в определенном направлении (по определенному пути) до тех пор, пока не достигнем конца пути или пункта назначения (искомой вершины). Если мы достигли конца пути, но он не является пунктом назначения, то мы возвращаемся назад (к точке разветвления или расхождения путей) и идем по другому маршруту.
Давайте рассмотрим пример. Предположим, что у нас есть ориентированный граф, который выглядит так:
Мы находимся в точке «s» и нам нужно найти вершину «t». Применяя DFS, мы исследуем один из возможных путей, двигаемся по нему до конца и, если не обнаружили t, возвращаемся и исследуем другой путь. Вот как выглядит процесс:
Здесь мы двигаемся по пути (p1) к ближайшей вершине и видим, что это не конец пути. Поэтому мы переходим к следующей вершине.
Мы достигли конца p1, но не нашли t, поэтому возвращаемся в s и двигаемся по второму пути.
Достигнув ближайшей к точке «s» вершины пути «p2» мы видим три возможных направления для дальнейшего движения. Поскольку вершину, венчающую первое направление, мы уже посещали, то двигаемся по второму.
Мы вновь достигли конца пути, но не нашли t, поэтому возвращаемся назад. Следуем по третьему пути и, наконец, достигаем искомой вершины «t».
Так работает DFS. Двигаемся по определенному пути до конца. Если конец пути — это искомая вершина, мы закончили. Если нет, возвращаемся назад и двигаемся по другому пути до тех пор, пока не исследуем все варианты.
Мы следуем этому алгоритму применительно к каждой посещенной вершине.
Необходимость многократного повторения процедуры указывает на необходимость использования рекурсии для реализации алгоритма.
Заметка: этот специальный DFS-алгоритм позволяет проверить, возможно ли добраться из одного места в другое. DFS может использоваться в разных целях. От этих целей зависит то, как будет выглядеть сам алгоритм. Тем не менее, общая концепция выглядит именно так.
Анализ DFS
Давайте проанализируем этот алгоритм. Поскольку мы обходим каждого «соседа» каждого узла, игнорируя тех, которых посещали ранее, мы имеем время выполнения, равное O(V + E).
Краткое объяснение того, что означает V+E:
V — общее количество вершин. E — общее количество граней (ребер).
Может показаться, что правильнее использовать V*E, однако давайте подумаем, что означает V*E.
V*E означает, что применительно к каждой вершине, мы должны исследовать все грани графа безотносительно принадлежности этих граней конкретной вершине.
С другой стороны, V+E означает, что для каждой вершины мы оцениваем лишь примыкающие к ней грани. Возвращаясь к примеру, каждая вершина имеет определенное количество граней и, в худшем случае, мы обойдем все вершины (O(V)) и исследуем все грани (O(E)). Мы имеем V вершин и E граней, поэтому получаем V+E.
Далее, поскольку мы используем рекурсию для обхода каждой вершины, это означает, что используется стек (бесконечная рекурсия приводит к ошибке переполнения стека). Поэтому пространственная сложность составляет O(V).
Теперь рассмотрим BFS.
Поиск в ширину
BFS следует концепции «расширяйся, поднимаясь на высоту птичьего полета» («go wide, bird’s eye-view»). Вместо того, чтобы двигаться по определенному пути до конца, BFS предполагает движение вперед по одному соседу за раз. Это означает следующее:
Вместо следования по пути, BFS подразумевает посещение ближайших к s соседей за одно действие (шаг), затем посещение соседей соседей и так до тех пор, пока не будет обнаружено t.
Чем DFS отличается от BFS? Мне нравится думать, что DFS идет напролом, а BFS не торопится, а изучает все в пределах одного шага.
Далее возникает вопрос: как узнать, каких соседей следует посетить первыми?
Для этого мы можем воспользоваться концепцией «первым вошел, первым вышел» (first-in-first-out, FIFO) из очереди (queue). Мы помещаем в очередь сначала ближайшую к нам вершину, затем ее непосещенных соседей, и продолжаем этот процесс, пока очередь не опустеет или пока мы не найдем искомую вершину.
Анализ BFS
Может показаться, что BFS работает медленнее. Однако если внимательно присмотреться к визуализациям, можно увидеть, что они имеют одинаковое время выполнения.
Очередь предполагает обработку каждой вершины перед достижением пункта назначения. Это означает, что, в худшем случае, BFS исследует все вершины и грани.
Несмотря на то, что BFS может казаться медленнее, на самом деле он быстрее, поскольку при работе с большими графами обнаруживается, что DFS тратит много времени на следование по путям, которые в конечном счете оказываются ложными. BFS часто используется для нахождения кратчайшего пути между двумя вершинами.
Таким образом, время выполнения BFS также составляет O(V + E), а поскольку мы используем очередь, вмещающую все вершины, его пространственная сложность составляет O(V).
Аналогии из реальной жизни
Если приводить аналогии из реальной жизни, то вот как я представляю себе работу DFS и BFS.
Когда я думаю о DFS, то представляю себе мышь в лабиринте в поисках еды. Для того, чтобы попасть к цели мышь вынуждена много раз упираться в тупик, возвращаться и двигаться по другому пути, и так до тех пор, пока она не найдет выход из лабиринта или еду.
Упрощенная версия выглядит так:
В свою очередь, когда я думаю о BFS, то представляю себе круги на воде. Падение камня в воду приводит к распространению возмущения (кругов) во всех направлениях от центра.
Упрощенная версия выглядит так:
Выводы
Неиспользуемые резервы Wi-Fi
В странах и городах с развитой телекоммуникационной инфраструктурой у пользователей всё чаще возникают нарекания на работу Wi-Fi. В урбанистической среде, плотно насыщенной клиентскими устройствами, использующими Wi-Fi, среднестатистическое качество связи год от года ухудшается. Можно ли как-то переломить эту тенденцию?
Сейчас в мире более 6,5 млрд устройств, подключённых к сети посредством этого беспроводного стандарта, а к 2020-му году их количество достигнет почти 21 млрд. Это примерно 2,8 устройств на каждого человека на планете. Так что нехватка пропускной способности беспроводных каналов будет только усугубляться. Однако для решения этой проблемы недостаточно просто установить больше мощных маршрутизаторов. Причиной «виртуальных пробок» является не только «узость дорог», но и ряд других факторов.
Сегодня в каждом доме и многих квартирах есть по Wi-Fi-роутеру, а в некоторых — по несколько Повышение скорости соединения обычно связано с более плотным использованием полос пропускания. Кроме того, мобильны операторы покушаются на Wi-Fi-диапазон, упаковывая в него часть трафика, и с появлением 5G ситуация может ещё больше усугубиться.
То есть Wi-Fi фактически стал жертвой собственного успеха. Что можно сделать для решения этой проблемы, или хотя бы для её смягчения?
Толчея в эфире
Хотя в разных странах регуляторы могут накладывать определённые требования по лицензированию спектра частот Wi-Fi, в целом этот диапазон остаётся более-менее открытым. Пользователи должны соблюдать технические требования, включая ограничения по мощности передачи, но для этого не нужно получить никаких специальных разрешений. Сегодня почти все общественные Wi-Fi-сети, в том числе и домашние, работают в диапазонах 2,4 и 5 ГГц. При этом 2,4-гигагерцовые волны лучше проникают сквозь стены и мебель, да и вообще передаются дальше по сравнению с 5-гигагерцовыми, при одинаковой мощности передачи.
К примеру, в США регулятор выделил для Wi-Fi полосу шириной 84,5 МГц. В рамках стандарта 802.11b/g/n ширина каналов — 20 или 22 МГц, так что в общую полосу можно без взаимного перекрытия уместить только три канала: 1, 6 и 11. В Европе ситуация почти такая же: 13 каналов, из которых одновременно можно использовать только три без взаимных перекрытий. В Японии чуть легче: 14 каналов и 4 одновременных неперекрывающихся.
Так что если в списке Wi-Fi-сетей вы видите более трёх 2,4-гигагерцовых роутеров, или если их три, но какой-то один использует канал, отличный от 1, 6 и 11, то имеет место наложение каналов.
В 5-гигацерцовом Wi-Fi ситуация иная: в диапазон от 5170 до 5905 ГГц уложено 38 неперекрывающихся каналов 10- и 20-мегагерцовой ширины (в США — 5180-5825 и 24 канала 20-мегагерцовой ширины, в Европе и Японии каналов ещё меньше). Казалось бы, в несколько раз больше каналов, которые не мешают друг другу, должны улучшить качество связи в 5-гигагерцовом диапазоне. Но тут вмешивается региональная специфика: в разных странах часть каналов могут быть недоступны для общественного использования, так как на этих частотах работают военные и метеорологические радары, спутниковое телевидение. Поэтому из-за сложности «вписывания» трафика в «проблемные» частоты подавляющее большинство роутеров их просто игнорируют.
Итак, в каждом из двух диапазонов у нас есть ряд неперекрывающихся каналов. Но из-за обилия роутеров и клиентских устройств перекрытие превратилось в нормальную ситуацию. Когда возникает коллизия — пересекаются две Wi-Fi-передачи — все участники временно замолкают, и через какую-то паузу снова возвращаются в эфир. Длительность пауз увеличивается экспоненциально по мере увеличения количества коллизий, в результате скорость работы и надёжность Wi-Fi-соединения снижаются.
В густонаселённых районах загруженность эфира может быть такова, что связь в 2,4-гигагерцовом диапазоне еле ползает. Это привело к тому, что в ряде стран провайдеры начали закрывать этот диапазон для передачи видео или голоса, а большинство производителей смартфонов вообще не рекомендуют пользоваться 2,4-гигагерцовым Wi-Fi. Стандарт IEEE 802.11ac вообще подразумевает работу только в 5-гигагерцовом диапазоне, хотя и обратно совместим с более старым IEEE 802.11n.
Современный Wi-Fi-эфир можно сравнить с загруженным шоссе в час пик. Но, как говорилось выше, дело не только в количестве клиентских подключений. Переход с 2,4 на 5 ГГц был призван решить проблему с перегруженностью каналов, но при этом пришлось пожертвовать покрытием. Это привело к тому, что многие пользователи начали применять аппаратные усилители и строить mesh-сети, чтобы добиться приличного уровня сигнала в каждой комнате. Усилители слушают эфир, получают от роутера сигнал и дублируют его с более высокой мощностью, иногда на другом канале. Это приводит к увеличению количества перекрытий Wi-Fi-передач в тех же частотных диапазонах.
Провайдеры и операторы
С этой точки зрения настоящим злом стали общественные точки Wi-Fi-доступа. В 2005 году испанский провайдер Fon Wireless впервые представил концепцию точек доступа для сообществ (community hotspots), которые создаются на базе частных роутеров, и сегодня это явление набирает популярность в мире. Некоторые интернет-провайдеры начали быстро развёртывать такие точки для подписчиков, используя для этого роутеры своих клиентов. Согласно данным исследовательской компании Juniper Research, в 2017-м треть домашних роутеров в мире смогут работать в режиме точки доступа для сообщества. На эти нужды будет выделяться часть Wi-Fi-спектра, причём владельцев самих роутеров даже не будут об этом предупреждать.
Но это ещё не всё. Стремительный рост поголовья смартфонов привёл к тому, что выделенные для мобильной связи полосы спектра оказались практически исчерпаны. И телеком-операторы планируют в ближайшие годы перенести существенную часть нагрузки по мобильной передаче данных в нелицензируемые Wi-Fi-диапазоны. Подобные технологии называются LTE-U (LTE-Unlicensed) и LAA (Licensed Assisted Access). Они подразумевают использование 4G LTE и роутеров для передачи данных в том же 5-гигагерцовом диапазоне, что и Wi-Fi. И хотя телеком-операторы уверяют, что это слабо скажется на пользователях Wi-Fi, ряд крупных компаний, включая Google и Microsoft, считают, LTE-U и LAA однозначно усугубят загруженность Wi-Fi-каналов и снизят качество связи.
Вам шашечки или ехать?
Идём дальше: в самом свежем стандарте IEEE 802.11ac уменьшено количество каналов в угоду увеличению скорости, чтобы транслировать потоковое видео в высоком разрешении и экономить аккумуляторы мобильных устройств, которые будут передавать данные на высоких частотах только в течение ограниченного времени. Максимальную пропускную способность подняли до 1,3 Гб/с. по сравнению с 450 Мб/с. в 802.11n. Но достигнуто это было в том числе и путём объединения каналов. В IEEE 802.11ac Wave 3 весь доступный Wi-Fi-спектр вообще разбивается всего на два канала по 160 МГц, то есть в это режиме одновременно без перекрывания могут работать только две пары устройств. Если, к примеру, ваш сосед использует один из этих двух каналов для просмотра кино, а другой сосед занял второй канал, то вам ничего не останется.
Как-то внезапно исчезло главное преимущество 5-гигагерцового диапазона перед 2,4-гигагерцовым — большое количество неперекрывающихся каналов.
Учитывая всё вышеописанное, в ближайшие годы Wi-Fi в больших городах рискует превратиться из быстрой альтернативы мобильному интернету в раздражающе медленную. Увы, но широкое распространение стандарта 802.11ac, предлагающего более широкие и быстрые, но малочисленные каналы лишь ухудшит ситуацию. К слову, телекоммуникационное агентство Ofcom ещё в 2013-м опубликовало исследование, в котором предсказан достижение критического уровня перегруженности Wi-Fi-спектра к 2020-му году.
DFS как временная мера
Помните про радары, имеющих приоритетное право использования части 5-гигагерцового диапазона? Сегодня эти каналы игнорируются потребительскими устройствами, но если начать массово их использовать, то это может полностью изменить картину.
Как подсказывает Капитан, далеко не на каждом углу в больших городах встречаются военные и метеорологические радары, многие из которых к тому же не работают круглосуточно. Поэтому эта часть спектра может быть задействована потребительскими устройствами при условии массового внедрения механизма DFS (Dynamic Frequency Selection): роутер постоянно отслеживает активность приоритетных источников сигнала, и как только начинает работать радар, происходит переключение на другой канал или снижение мощности передачи. DFS подразумевает освобождение канала в течение 10 секунд на последующие полчаса даже при обнаружении 1-миллисекундного импульса от приоритетного источника.
Большинство выпущенных в последние 3-4 года потребительских устройств — в первую очередь, смартфонов, планшетов и ноутбуков — могут понимать команды DFS, но для этого роутеры должны быть DFS-мастерами. То есть именно на роутеры ложится ответственность по мониторингу спектра и освобождению каналов смежного использования.
Но не так просто внедрить в роутер функцию DFS-мастера: радарные импульсы могут быть очень труднообнаруживаемы из-за их скоротечности (0,5 мс) и крайне низкого уровня энергии (-62..-64 дБ на млВт). Более того, инструменты обнаружения радарных импульсов съедают часть пропускной способности роутера, поскольку он вынужден перед началом использования канала прослушивать его в течение 60 секунд, прежде чем решить, что тот свободен, а также прослушивать между сеансами обмена данными.
На сегодняшний день функция DFS-мастера встречается только в дорогих роутерах, которые обычно используются в крупных компаниях. Но постепенно DFS проникает и в более низкие ценовые сегменты. Правда, это тоже не панацея: ведь при обнаружении сигнала от приоритетного источника роутер вынужден переходить на один из каналов по умолчанию, в неDFS-часть 5-гигагерцового спектра, а там довольно «тесно». Более того, современные роутеры обычно не возвращаются на DFS-каналы, пока их не перезагрузят. В корпоративных системах это делается ежедневно, а домашние роутеры могут работать без перезагрузки неделями и месяцами, пока владельцы не сообразят, что скорость Wi-Fi слишком низкая и пора перезагрузиться.
Дело в том, что в современных реализациях DFS радиомодуль прослушивает единовременно только один канал. И когда DFS-мастер мониторит канал, его радиомодуль в течение 60 секунд не должен ничего передавать в другие каналы, чтобы не мешать текущему прослушиванию. Во избежание подобных ситуаций большинство DFS-реализаций требуют перезагрузки роутера для возвращения в открытый DFS-канал.
Но если создать более эффективную технологию обнаружения приоритетных источников, то фактически простаивающие сегодня каналы помогли бы разгрузить 5-гигагерцовый Wi-Fi-спектр. Например, можно оснастить роутер детекторной системой — дополнительным радиомодулем для сканирования спектра и отдельным процессором для выявления радарных импульсов и управления каналами. При этом детекторная система должна быть полностью отделена от системы приёма/передачи Wi-Fi, что позволит решить большинство проблем, присущих современным реализациям DFS, когда один процессор отвечает и за передачу данных, и за поиск приоритетных источников сигнала. Отдельный радиомодуль позволит регулярно сканировать все каналы, и когда в текущем канале возникает приоритетный источник, роутер будет знать, есть ли другой открытый в данный момент DFS-канал, перенося соединение туда, а не в публичный канал по умолчанию. Точно также роутер может автоматически возвращаться в предыдущий DFS-канал по истечение получасового лимита без прерывания соединения.
При этом дополнительный процессор поможет минимизировать количество ложных обнаружений, тем самым увеличив длительность работы в DFS-каналах. Учитывая рост нагрузки на процессоры современных роутеров, второй процессор совсем не выглядит излишеством.
В принципе, всё это тоже временная мера: чем больше роутеров начнут использовать ныне простаивающие каналы, тем быстрее они тоже окажутся перегружены. Но к тому времени могут быть согласованы для использования Wi-Fi-сетями и другие диапазоны. Либо нам придётся просто смириться с тем, что через несколько лет в мегаполисах Wi-Fi будет работать, мягко говоря, не быстро.
