Кластер (англ. cluster ) — в некоторых типах файловых систем логическая единица хранения данных в таблице размещения файлов, объединяющая группу секторов. Например, на дисках с размером секторов в 512 байт, 512-байтный кластер содержит один сектор, тогда как 4-килобайтный кластер содержит восемь секторов.
Как правило, это наименьшее место на диске, которое может быть выделено для хранения файла.
Понятие кластер используется в файловых системах FAT, NTFS, a так же HFS Plus. Другие файловые системы оперируют схожими понятиями (зоны в Minix, блоки в Unix).
Оптимизация
В некоторых файловых системах Linux (ReiserFS, Reiser4, Btrfs), BSD (FreeBSD UFS2) последний блок файла может быть поделен на подфрагменты, в которые могут быть помещены «хвосты» других файлов. В NTFS маленькие файлы могут быть записаны в Master File Table (MFT). В файловой же системе FAT из-за примитивного алгоритма степень фрагментации постоянно растёт и требуется периодическая дефрагментация. Маленький кластер лучше подходит для маленьких файлов. Так экономнее расходуется место. Большой кластер позволяет достичь более высоких скоростей, но на мелких файлах место будет использоваться нерационально (многие сектора будут не полностью заполненными, но будут считаться занятыми).
Это заготовка статьи о компьютерах. Вы можете помочь проекту, исправив и дополнив её. Это примечание по возможности следует заменить более точным.
Полезное
Смотреть что такое «Кластер (единица хранения данных)» в других словарях:
Кластер — в вычислительной технике группа компьютеров, объединенных высокоскоростными каналами связи и представляющая с точки зрения пользователя одну многопроцессорную вычислительную машину. По английски: Cluster См. также: Мультипроцессорная обработка… … Финансовый словарь
Кластер — (англ. cluster скопление) объединение нескольких однородных элементов, которое может рассматриваться как самостоятельная единица, обладающая определёнными свойствами. В информационных технологиях: Кластер как подмножество… … Википедия
кластер — Термин кластер Термин на английском cluster Синонимы суператом Аббревиатуры Связанные термины магические кластеры, наночастица, фуллерен, эндоэдральный, матричная изоляция Определение (от англ. cluster рой, скопление) компактная группа связанных… … Энциклопедический словарь нанотехнологий
КЛАСТЕР — Объединение в систему однородных единиц. При этом данная система может считаться самостоятельным элементом обладающим определенными свойствами. Понятие кластер входит во многие области науки химию, физику, социологию, астрономию и т.д. В… … Словарь бизнес-терминов
Кластеры — Кластер (англ. cluster скопление) объединение нескольких однородных элементов, которое может рассматриваться как самостоятельная единица, обладающая определёнными свойствами. В информационных технологиях: Кластер (единица хранения данных) … … Википедия
ГОСТ Р 54136-2010: Системы промышленной автоматизации и интеграция. Руководство по применению стандартов, структура и словарь — Терминология ГОСТ Р 54136 2010: Системы промышленной автоматизации и интеграция. Руководство по применению стандартов, структура и словарь оригинал документа: 4.1 абстрактная деталь (abstract part): Деталь, которая определена только своей… … Словарь-справочник терминов нормативно-технической документации
картографирование науки — КАРТОГРАФИРОВАНИЕ НАУКИ. В эпистемологии и философии науки интерес к тематическому строению науки был вызван общей эволюцией научного знания. К 70 80 гг. 20 в. фронт таких исследований значительно расширяется, интенсивное развитие… … Энциклопедия эпистемологии и философии науки
Самара — У этого термина существуют и другие значения, см. Самара (значения). Городской округ Самара … Википедия
В своей дипломной работе я проводил обзор и сравнительный анализ алгоритмов кластеризации данных. Подумал, что уже собранный и проработанный материал может оказаться кому-то интересен и полезен. О том, что такое кластеризация, рассказал sashaeve в статье «Кластеризация: алгоритмы k-means и c-means». Я частично повторю слова Александра, частично дополню. Также в конце этой статьи интересующиеся могут почитать материалы по ссылкам в списке литературы.
Так же я постарался привести сухой «дипломный» стиль изложения к более публицистическому.
Понятие кластеризации
Кластеризация (или кластерный анализ) — это задача разбиения множества объектов на группы, называемые кластерами. Внутри каждой группы должны оказаться «похожие» объекты, а объекты разных группы должны быть как можно более отличны. Главное отличие кластеризации от классификации состоит в том, что перечень групп четко не задан и определяется в процессе работы алгоритма.
Меры расстояний
Итак, как же определять «похожесть» объектов? Для начала нужно составить вектор характеристик для каждого объекта — как правило, это набор числовых значений, например, рост-вес человека. Однако существуют также алгоритмы, работающие с качественными (т.н. категорийными) характеристиками.
Классификация алгоритмов
Объединение кластеров
Обзор алгоритмов
Алгоритмы иерархической кластеризации
Среди алгоритмов иерархической кластеризации выделяются два основных типа: восходящие и нисходящие алгоритмы. Нисходящие алгоритмы работают по принципу «сверху-вниз»: в начале все объекты помещаются в один кластер, который затем разбивается на все более мелкие кластеры. Более распространены восходящие алгоритмы, которые в начале работы помещают каждый объект в отдельный кластер, а затем объединяют кластеры во все более крупные, пока все объекты выборки не будут содержаться в одном кластере. Таким образом строится система вложенных разбиений. Результаты таких алгоритмов обычно представляют в виде дерева – дендрограммы. Классический пример такого дерева – классификация животных и растений.
Для вычисления расстояний между кластерами чаще все пользуются двумя расстояниями: одиночной связью или полной связью (см. обзор мер расстояний между кластерами).
К недостатку иерархических алгоритмов можно отнести систему полных разбиений, которая может являться излишней в контексте решаемой задачи.
Алгоритмы квадратичной ошибки
Задачу кластеризации можно рассматривать как построение оптимального разбиения объектов на группы. При этом оптимальность может быть определена как требование минимизации среднеквадратической ошибки разбиения:
где cj — «центр масс» кластера j (точка со средними значениями характеристик для данного кластера).
К недостаткам данного алгоритма можно отнести необходимость задавать количество кластеров для разбиения.
Нечеткие алгоритмы
Алгоритмы, основанные на теории графов
Суть таких алгоритмов заключается в том, что выборка объектов представляется в виде графа G=(V, E), вершинам которого соответствуют объекты, а ребра имеют вес, равный «расстоянию» между объектами. Достоинством графовых алгоритмов кластеризации являются наглядность, относительная простота реализации и возможность вносения различных усовершенствований, основанные на геометрических соображениях. Основными алгоритмам являются алгоритм выделения связных компонент, алгоритм построения минимального покрывающего (остовного) дерева и алгоритм послойной кластеризации.
Алгоритм выделения связных компонент
В алгоритме выделения связных компонент задается входной параметр R и в графе удаляются все ребра, для которых «расстояния» больше R. Соединенными остаются только наиболее близкие пары объектов. Смысл алгоритма заключается в том, чтобы подобрать такое значение R, лежащее в диапазон всех «расстояний», при котором граф «развалится» на несколько связных компонент. Полученные компоненты и есть кластеры.
Для подбора параметра R обычно строится гистограмма распределений попарных расстояний. В задачах с хорошо выраженной кластерной структурой данных на гистограмме будет два пика – один соответствует внутрикластерным расстояниям, второй – межкластерным расстояния. Параметр R подбирается из зоны минимума между этими пиками. При этом управлять количеством кластеров при помощи порога расстояния довольно затруднительно.
Алгоритм минимального покрывающего дерева
Алгоритм минимального покрывающего дерева сначала строит на графе минимальное покрывающее дерево, а затем последовательно удаляет ребра с наибольшим весом. На рисунке изображено минимальное покрывающее дерево, полученное для девяти объектов.
Путём удаления связи, помеченной CD, с длиной равной 6 единицам (ребро с максимальным расстоянием), получаем два кластера: и . Второй кластер в дальнейшем может быть разделён ещё на два кластера путём удаления ребра EF, которое имеет длину, равную 4,5 единицам.
Послойная кластеризация
Алгоритм послойной кластеризации основан на выделении связных компонент графа на некотором уровне расстояний между объектами (вершинами). Уровень расстояния задается порогом расстояния c. Например, если расстояние между объектами , то .
Алгоритм послойной кластеризации формирует последовательность подграфов графа G, которые отражают иерархические связи между кластерами:
Файловая система и размер кластера при форматировании
Перед началом работы с диском, флешкой или другим носителем информации его необходимо отформатировать. При форматировании надо выбрать файловую систему и установить для нее размер кластера.
В данной статье даются самые базовые сведения о том, как организуется хранение информации на дисках, что такое файловая система, кластер и как оптимальным образом выбрать размер кластера при форматировании.
Файловая система и ее виды
Система отвечает за запись информации на носитель, ее поиск, чтение и удаление. Некоторые системы дополнительно могут шифровать информацию, разграничивать права доступа и обеспечивать совместный доступ к файлам.
На сегодняшний день наиболее распространены следующие системы:
Размещение информации на жестком диске
Жесткий диск компьютера физически представляет из себя металлический диск, на поверхность которого нанесен магнитный слой. Диск вращается с постоянной скоростью, а над его поверхностью, не касаясь ее, скользят магнитные головки. При записи магнитные головки оставляют на поверхности намагниченный след — дорожку. Дорожка делится на сектора, в которые, собственно, и записывается информация. В стандартном секторе 512 байт информации. Головки могут двигаться от края диска к центру, формируя на его поверхности множество дорожек. Номер дорожки и номер сектора на ней однозначно определяют положение информации на диске.
Что такое кластер
Итак, минимальный фрагмент информации на диске — это сектор размером 512 байт.
Работать с фрагментами такого малого размера не всегда удобно, поэтому файловая система работает не с отдельными секторами, а с блоками секторов, называемыми кластерами.
Величина кластера может меняться в зависимости от того, сколько секторов объединяется в кластер. Минимальный размер кластера — 512 байт, максимальный — 32 МБ.
Таким образом, минимальный фрагмент информации, который может быть записан на диск или считан с него, равен в общем случае не сектору, а кластеру.
На что влияет размер кластера
С точки зрения операционной системы диск представляет собой массив минимальных блоков информации — кластеров.
При записи файла он всегда занимает на диске определенное число блоков. Например, при записи файла в 12 байт он занимает на диске минимальное возможное пространство в 1 блок. При величине блока в 512 байт реально используется 12 байт, а остальные 500 теряются бесполезно.
Таким образом, чем меньше блок, тем более экономно расходуется дисковое пространство.
Длинный файл представляет собой цепочку блоков. Чем меньше размер, тем больше блоков в цепочке. Блоки могут оказаться разбросаны по разным секторам и дорожкам весьма хаотично. Контроллеру диска придется разыскивать последовательно блок за блоком на разных дорожках, и этот процесс может занять значительное время.
Чем больше кластер, тем меньше их в файле, и тем быстрее происходит его поиск, чтение или запись.
Оптимальная величина кластера — это компромисс между скоростью и экономией дискового пространства.
Размер кластера в разных файловых системах
Для каждой системы определена величина кластера по умолчанию.
Этот размер считается оптимальным и установится автоматически, если при форматировании носителя не установить другой размер принудительно.
Для наиболее популярных систем эти значения будут равны:
Значение по умолчанию имеет смысл использовать при форматировании диска в подавляющем большинстве случаев.
Что такое форматирование
Форматирование носителя — это его разметка для подготовки к использованию для чтения или записи информации.
Различают низкоуровневое и высокоуровневое форматирование.
Различают два вида форматирования: быстрое и полное.
Файловая система для флешки
Флеш-накопители на заводе по умолчанию форматируются под FAT-32.
Это наиболее универсальная на сегодняшний день система, с которой работают практически все устройства: как старые, так и новые.
Единственное практически важное ограничение — размер файла не может быть больше 4 Гб.
Если есть необходимость записи файлов более 4 Гб, например, игр или фильмов, можно отформатировать под NTFS или под ExFAT. Но будьте готовы к тому, что более старые устройства не смогут работать с этими системами.
Размер кластера при форматировании флешки
Общее правило форматирования: чем больше длина файлов, которые предполагается хранить, тем большую величину следует выбирать при форматировании. При отсутствии особых показаний оставлять значение по умолчанию.
Видео
Из этого видео вы узнаете, как самостоятельно правильно отформатировать флешку.
Кластер — группа компьютеров, объединённых высокоскоростными каналами связи и представляющая с точки зрения пользователя единый аппаратный ресурс.
Один из первых архитекторов кластерной технологии Грегори Пфистер дал кластеру следующее определение: «Кластер — это разновидность параллельной или распределённой системы, которая:
Обычно различают следующие основные виды кластеров:
Содержание
Классификация кластеров
Кластеры высокой доступности
Обозначаются аббревиатурой HA (англ. High Availability — высокая доступность). Создаются для обеспечения высокой доступности сервиса, предоставляемого кластером. Избыточное число узлов, входящих в кластер, гарантирует предоставление сервиса в случае отказа одного или нескольких серверов. Типичное число узлов — два, это минимальное количество, приводящее к повышению доступности. Создано множество программных решений для построения такого рода кластеров.
Отказоустойчивые кластеры и системы вообще строятся по трем основным принципам:
Конкретная технология может сочетать данные принципы в любой комбинации. Например, Linux-HA поддерживает режим обоюдной поглощающей конфигурации (англ. takeover ), в котором критические запросы выполняются всеми узлами вместе, прочие же равномерно распределяются между ними. [1]
Кластеры распределения нагрузки
Принцип их действия строится на распределении запросов через один или несколько входных узлов, которые перенаправляют их на обработку в остальные, вычислительные узлы. Первоначальная цель такого кластера — производительность, однако, в них часто используются также и методы, повышающие надёжность. Подобные конструкции называются серверными фермами. Программное обеспечение (ПО) может быть как коммерческим (OpenVMS, MOSIX, Platform LSF HPC, Solaris Cluster, Moab Cluster Suite, Maui Cluster Scheduler), так и бесплатным (OpenMosix, Sun Grid Engine, Linux Virtual Server).
Вычислительные кластеры
Кластеры используются в вычислительных целях, в частности в научных исследованиях. Для вычислительных кластеров существенными показателями являются высокая производительность процессора в операциях над числами с плавающей точкой (flops) и низкая латентность объединяющей сети, и менее существенными — скорость операций ввода-вывода, которая в большей степени важна для баз данных и web-сервисов. Вычислительные кластеры позволяют уменьшить время расчетов, по сравнению с одиночным компьютером, разбивая задание на параллельно выполняющиеся ветки, которые обмениваются данными по связывающей сети. Одна из типичных конфигураций — набор компьютеров, собранных из общедоступных компонентов, с установленной на них операционной системой Linux, и связанных сетью Ethernet, Myrinet, InfiniBand или другими относительно недорогими сетями. Такую систему принято называть кластером Beowulf. Специально выделяют высокопроизводительные кластеры (Обозначаются англ. аббревиатурой HPC Cluster — High-performance computing cluster). Список самых мощных высокопроизводительных компьютеров (также может обозначаться англ. аббревиатурой HPC) можно найти в мировом рейтинге TOP500. В России ведется рейтинг самых мощных компьютеров СНГ. [1]
Системы распределенных вычислений (grid)
Такие системы не принято считать кластерами, но их принципы в значительной степени сходны с кластерной технологией. Их также называют grid-системами. Главное отличие — низкая доступность каждого узла, то есть невозможность гарантировать его работу в заданный момент времени (узлы подключаются и отключаются в процессе работы), поэтому задача должна быть разбита на ряд независимых друг от друга процессов. Такая система, в отличие от кластеров, не похожа на единый компьютер, а служит упрощённым средством распределения вычислений. Нестабильность конфигурации, в таком случае, компенсируется больши́м числом узлов.
Кластер серверов, организуемых программно
Кластер серверов (в информационных технологиях) — группа серверов, объединённых логически, способных обрабатывать идентичные запросы и использующихся как единый ресурс. Чаще всего серверы группируются посредством локальной сети. Группа серверов обладает большей надежностью и большей производительностью, чем один сервер. Объединение серверов в один ресурс происходит на уровне программных протоколов.
В отличие от аппаратного кластера компьютеров, кластеры организуемые программно, требуют:
Применение
В большинстве случаев, кластеры серверов функционируют на раздельных компьютерах. Это позволяет повышать производительность за счёт распределения нагрузки на аппаратные ресурсы и обеспечивает отказоустойчивость на аппаратном уровне.
Однако, принцип организации кластера серверов (на уровне программного протокола) позволяет исполнять по нескольку программных серверов на одном аппаратном. Такое использование может быть востребовано:
Самые производительные кластеры
Дважды в год организацией TOP500 публикуется список пятисот самых производительных вычислительных систем в мире, среди которых в последнее время часто преобладают кластеры. Самым быстрым кластером является IBM Roadrunner (Лос-Аламосская национальная лаборатория, США, созданный в 2008 году), его максимальная производительность (на июль 2008) составляет 1,026 Петафлопс. Самая быстрая система в Европе (на июль 2008) — суперкомпьютер, BlueGene/P находится в Германии, в исследовательском центре города Юлих, земля Северный Рейн-Вестфалия, максимально достигнутая производительность 167,3 Терафлопс.
Кластерные системы занимают достойное место в списке самых быстрых, при этом значительно выигрывая у суперкомпьютеров в цене. На июль 2008 года на 7 месте рейтинга TOP500 находится кластер SGI Altix ICE 8200 (Chippewa Falls, Висконсин, США).
Сравнительно дешёвую альтернативу суперкомпьютерам представляют кластеры, основанные на концепции Beowulf, которые строятся из обыкновенных недорогих компьютеров на основе бесплатного программного обеспечения. Один из практических примеров такой системы — Stone Soupercomputer (Оак Ридж, Теннесси, США, 1997).
Крупнейший кластер, принадлежащий частному лицу (из 1000 процессоров), был построен Джоном Коза (John Koza).
История
История создания кластеров неразрывно связана с ранними разработками в области компьютерных сетей. Одной из причин для появления скоростной связи между компьютерами стали надежды на объединение вычислительных ресурсов. В начале 1970-х гг. группой разработчиков протокола TCP/IP и лабораторией Xerox PARC были закреплены стандарты сетевого взаимодействия. Появилась и операционная система Hydra («Гидра») для компьютеров PDP-11 производства DEC, созданный на этой основе кластер был назван C.mpp (Питтсбург, шт. Пенсильвания, США, 1971). Тем не менее, только около 1983 г. были созданы механизмы, позволяющие с лёгкостью пользоваться распределением задач и файлов через сеть, по большей части это были разработки в SunOS (операционной системе на основе BSD от компании Sun Microsystems).
Первым коммерческим проектом кластера стал ARCNet, созданный компанией Datapoint в 1977 г. Прибыльным он не стал, и поэтому строительство кластеров не развивалось до 1984 г., когда DEC построила свой VAXcluster на основе операционной системы VAX/VMS. ARCNet и VAXcluster были рассчитаны не только на совместные вычисления, но и совместное использование файловой системы и периферии с учётом сохранения целостности и однозначности данных. VAXCluster (называемый теперь VMSCluster) — является неотъемлемой компонентой операционной системы HP OpenVMS, использующих процессоры Alpha и Itanium.
Два других ранних кластерных продукта, получивших признание, включают Tandem Hymalaya (1994, класс HA) и IBM S/390 Parallel Sysplex (1994).
История создания кластеров из обыкновенных персональных компьютеров во многом обязана проекту Parallel Virtual Machine. В 1989 г. это ПО для объединения компьютеров в виртуальный суперкомпьютер открыло возможность мгновенного создания кластеров. В результате суммарная производительность всех созданных тогда дешёвых кластеров обогнала по производительности сумму мощностей «серьёзных» коммерческих систем.
Создание кластеров на основе дешёвых персональных компьютеров, объединённых сетью передачи данных, продолжилось в 1993 г. силами Американского аэрокосмического агентства (NASA), затем в 1995 г. получили развитие кластеры Beowulf, специально разработанные на основе этого принципа. Успехи таких систем подтолкнули развитие grid-сетей, которые существовали ещё с момента создания UNIX.
Программные средства
Широко распространённым средством для организации межсерверного взаимодействия является библиотека MPI, поддерживающая языки C и Fortran. Она используется, например, в программе моделирования погоды MM5.
Операционная система Solaris предоставляет программное обеспечение Solaris Cluster, которое служит для обеспечения высокой доступности и безотказности серверов, работающих под управлением Solaris. Для OpenSolaris существует реализация с открытым кодом под названием OpenSolaris HA Cluster.
Среди пользователей GNU/Linux популярны несколько программ:
Кластерные механизмы планируется встроить и в ядро DragonFly BSD, ответвлившуюся в 2003 году от FreeBSD 4.8. В дальних планах также превращение её в среду единой операционной системы.
Компанией Microsoft выпускается HA-кластер для операционной системы Windows. Существует мнение, что он создан на основе технологии Digital Equipment Corporation, поддерживает до 16 (с 2010 года) узлов в кластере, а также работу в сети SAN (Storage Area Network). Набор API-интерфейсов служит для поддержки распределяемых приложений, есть заготовки для работы с программами, не предусматривающими работы в кластере.
Windows Compute Cluster Server 2003 (CCS), выпущенный в июне 2006 года разработан для высокотехнологичных приложений, которые требуют кластерных вычислений. Издание разработано для развертывания на множестве компьютеров, которые собираются в кластер для достижения мощностей суперкомпьютера. Каждый кластер на Windows Compute Cluster Server состоит из одного или нескольких управляющих машин, распределяющих задания и нескольких подчиненных машин, выполняющих основную работу. В ноябре 2008 представлен Windows HPC Server 2008, призванный заменить Windows Compute Cluster Server 2003.
, то 
.
,
