X

Recent Posts

General

ZFS Deduplication

You knew this day was coming: ZFS now has built-in deduplication. If you already know what dedup is and why you want it, you can skipthe next couple of sections. For everyone else, let's start witha little background. What is it? Deduplication is the process of eliminating duplicate copies of data.Dedup is generally either file-level, block-level, or byte-level.Chunks of data -- files, blocks, or byte ranges -- are checksummedusing some hash function that uniquely identifies data with very highprobability. When using a secure hash like SHA256, the probability of ahash collision is about 2\^-256 = 10\^-77 or, in more familiar notation,0.00000000000000000000000000000000000000000000000000000000000000000000000000001.For reference, this is 50 orders of magnitude less likely than an undetected,uncorrected ECC memory error on the most reliable hardware you can buy. Chunks of data are remembered in a table of some sort that maps thedata's checksum to its storage location and reference count. When youstore another copy of existing data, instead of allocating new spaceon disk, the dedup code just increments the reference count on theexisting data. When data is highly replicated, which is typical ofbackup servers, virtual machine images, and source code repositories,deduplication can reduce space consumption not just by percentages,but by multiples. What to dedup: Files, blocks, or bytes? Data can be deduplicated at the level of files, blocks, or bytes. File-level assigns a hash signature to an entire file. File-leveldedup has the lowest overhead when the natural granularity of dataduplication is whole files, but it also has significant limitations:any change to any block in the file requires recomputing the checksumof the whole file, which means that if even one block changes, any spacesavings is lost because the two versions of the file are no longer identical.This is fine when the expected workload is something like JPEG or MPEG files,but is completely ineffective when managing things like virtual machineimages, which are mostly identical but differ in a few blocks. Block-level dedup has somewhat higher overhead than file-level dedup whenwhole files are duplicated, but unlike file-level dedup, it handles block-leveldata such as virtual machine images extremely well. Most of a VM image isduplicated data -- namely, a copy of the guest operating system -- but someblocks are unique to each VM. With block-level dedup, only the blocks thatare unique to each VM consume additional storage space. All other blocksare shared. Byte-level dedup is in principle the most general, but it is also the mostcostly because the dedup code must compute 'anchor points' to determinewhere the regions of duplicated vs. unique data begin and end.Nevertheless, this approach is ideal for certain mail servers, in which anattachment may appear many times but not necessary be block-aligned in eachuser's inbox. This type of deduplication is generally best left to theapplication (e.g. Exchange server), because the application understandsthe data it's managing and can easily eliminate duplicates internallyrather than relying on the storage system to find them after the fact. ZFS provides block-level deduplication because this is the finestgranularity that makes sense for a general-purpose storage system.Block-level dedup also maps naturally to ZFS's 256-bit block checksums,which provide unique block signatures for all blocks in a storage poolas long as the checksum function is cryptographically strong (e.g. SHA256). When to dedup: now or later? In addition to the file/block/byte-level distinction described above,deduplication can be either synchronous (aka real-time or in-line)or asynchronous (aka batch or off-line). In synchronous dedup,duplicates are eliminated as they appear. In asynchronous dedup,duplicates are stored on disk and eliminated later (e.g. at night).Asynchronous dedup is typically employed on storage systems that havelimited CPU power and/or limited multithreading to minimize theimpact on daytime performance. Given sufficient computing power,synchronous dedup is preferable because it never wastes spaceand never does needless disk writes of already-existing data. ZFS deduplication is synchronous. ZFS assumes a highly multithreadedoperating system (Solaris) and a hardware environment in which CPU cycles(GHz times cores times sockets) are proliferating much faster than I/O.This has been the general trend for the last twenty years, and theunderlying physics suggests that it will continue. How do I use it? Ah, finally, the part you've really been waiting for. If you have a storage pool named 'tank' and you want to use dedup,just type this: zfs set dedup=on tank That's it. Like all zfs properties, the 'dedup' property follows the usual rulesfor ZFS dataset property inheritance. Thus, even though deduplicationhas pool-wide scope, you can opt in or opt out on a per-dataset basis. What are the tradeoffs? It all depends on your data. If your data doesn't contain any duplicates, enabling dedup will addoverhead (a more CPU-intensive checksum and on-disk dedup table entries)without providing any benefit. If your data does contain duplicates,enabling dedup will both save space and increase performance. Thespace savings are obvious; the performance improvement is due to theelimination of disk writes when storing duplicate data, plus thereduced memory footprint due to many applications sharing the samepages of memory. Most storage environments contain a mix of data that is mostly uniqueand data that is mostly replicated. ZFS deduplication is per-dataset,which means you can selectively enable dedup only where it is likelyto help. For example, suppose you have a storage pool containinghome directories, virtual machine images, and source code repositories.You might choose to enable dedup follows: zfs set dedup=off tank/home zfs set dedup=on tank/vm zfs set dedup=on tank/src Trust or verify? If you accept the mathematical claim that a secure hash like SHA256 hasonly a 2\^-256 probability of producing the same output given two differentinputs, then it is reasonable to assume that when two blocks have thesame checksum, they are in fact the same block. You can trust the hash.An enormous amount of the world's commerce operates on this assumption,including your daily credit card transactions. However, if this makesyou uneasy, that's OK: ZFS provies a 'verify' option that performsa full comparison of every incoming block with any alleged duplicate toensure that they really are the same, and ZFS resolves the conflict if not.To enable this variant of dedup, just specify 'verify' instead of 'on': zfs set dedup=verify tank Selecting a checksum Given the ability to detect hash collisions as described above, it ispossible to use much weaker (but faster) hash functions in combinationwith the 'verify' option to provide faster dedup. ZFS offers thisoption for the fletcher4 checksum, which is quite fast: zfs set dedup=fletcher4,verify tank The tradeoff is that unlike SHA256, fletcher4 is not a pseudo-randomhash function, and therefore cannot be trusted not to collide. It istherefore only suitable for dedup when combined with the 'verify' option,which detects and resolves hash collisions. On systems with a very highdata ingest rate of largely duplicate data, this may provide betteroverall performance than a secure hash without collision verification. Unfortunately, because there are so many variables that affect performance,I cannot offer any absolute guidance on which is better. However, ifyou are willing to make the investment to experiment with differentchecksum/verify options on your data, the payoff may be substantial.Otherwise, just stick with the default provided by setting dedup=on;it's cryptograhically strong and it's still pretty fast. Scalability and performance Most dedup solutions only work on a limited amount of data -- a handfulof terabytes -- because they require their dedup tables to be residentin memory. ZFS places no restrictions on your ability to dedup. You can dedupa petabyte if you're so inclined. The performace of ZFS dedup willfollow the obvious trajectory: it will be fastest when the DDTs(dedup tables) fit in memory, a little slower when they spill overinto the L2ARC, and much slower when they have to be read from disk.The topic of dedup performance could easily fill many blog entries -- andit will over time -- but the point I want to emphasize here is that thereare no limits in ZFS dedup. ZFS dedup scales to any capacity on anyplatform, even a laptop; it just goes faster as you give it more hardware. Acknowledgements Bill Moore and I developed the first dedup prototype in two very intensedays in December 2008. Mark Maybee and Matt Ahrens helped us navigatethe interactions of this mostly-SPA code change with the ARC and DMU.Our initial prototype was quite primitive: it didn't support gang blocks,ditto blocks, out-of-space, and various other real-world conditions.However, it confirmed that the basic approach we'd been planning forseveral years was sound: namely, to use the 256-bit block checksumsin ZFS as hash signatures for dedup. Over the next several months Bill and I tag-teamed the work so thatat least one of us could make forward progress while the other dealtwith some random interrupt of the day. As we approached the end game, Matt Ahrens and Adam Leventhal developedseveral optimizations for the ZAP to minimize DDT space consumption bothon disk and in memory, key factors in dedup performance. George Wilsonstepped in to help with, well, just about everything, as he always does. For final code review George and I flew to Colorado where many folksgenerously lent their time and expertise: Mark Maybee, Neil Perrin,Lori Alt, Eric Taylor, and Tim Haley. Our test team, led by Robin Guo, pounded on the code and made a coupleof great finds -- which were actually latent bugs exposed by some new,tighter ASSERTs in the dedup code. My family (Cathy, Andrew, David, and Galen) demonstrated enormouspatience as the project became all-consuming for the last few months.On more than one occasion one of the kids has asked whether we can dosomething and then immediately followed their own question with,"Let me guess: after dedup is done." Well, kids, dedup is done. We're going to have some fun now.

You knew this day was coming: ZFS now has built-in deduplication. If you already know what dedup is and why you want it, you can skip the next couple of sections. For everyone else, let's start witha...

ZFS

Сквозная целостность данных в ZFS

Работу любой файловой системыможно свести к следующему: на просьбу прочитать блок данных, она должнавернуть те же самые данные, которые были ранее записаны в этот блок.Если этого сделать не получается -- из-за отключения диска, поврежденияданных и т.д. -- она должна обнаружить это и вернуть ошибку. Невероятно,но большинство файловых систем не проходят этот тест. Они опираются нато, что используемое "железо" определит ошибку и сообщит о ней. Еслидиск просто вернёт некорректные данные, обычная файловая система дажене обнаружит этого. Даже если предположить, что все дискиидеальны и всегда возвращают то, что было записано ранее, данные всеещё будут уязвимы при передаче: ошибки в микрокоде контроллера, ошибкичетности при DMA и т.д. Мы могли бы говорить только о том, что данныебыли целы, когда покидали пластину диска. Если рассматривать данные какпосылку, это все равно что UPS говорила бы: "Мы гарантируем, что вашапосылка не была повреждена, когда мы приняли её". Это не совсем тагарантия, которая нам нужна. Повреждение данных при передаче не есть предмет простого научного любопытства: даже такая приземлённая вещь, как неисправный источник питания может вызвать неявное повреждение данных. Безосновательнодорогие массивы хранения данных не могут решить эту проблему. Путьпрохождения операций ввода/вывода не только остаётся таким же уязвимым,но и становится длиннее: покидая пластину диска, данные должны уцелеть,несмотря на какие бы то ни было аппаратные и программно-аппаратныеошибки, которые могут содержаться в массиве. А если ваш массив находится в SAN, вы используете сеть, спроектированную писателями микрокода дисков. Бог в помощь. Чтоже делать? Одним из вариантов является сохранение контрольной суммыкаждого блока на диске. Большинство современных дисковых накопителеймогут быть отформатированы с размером сектора, который немного большестандартных 512 байт -- обычно 520 или 528. Эти дополнительные байтыможно использовать для хранения контрольной суммы блока. Сказать легко,но правильно использовать контрольную сумму сложнее: эфективностьконтрольной суммы крайне зависит от места хранения и момента проверки. Во многих дисковых массивах (типичный пример с прекрасным описанием данного метода можно найти в статье о Dell|EMC PowerVault) данные сравниваются с контрольной суммой внутри массива.К сожалению, это не очень помогает справиться с проблемой. Такой способне позволяет выявить типичные ошибки в микрокоде диска, такие как,например, фантомная запись (операция записи, которая не достигла диска,но была подтверждена как выполненная), так как данные и контрольнаясумма хранятся вместе -- они непротиворечивы, даже если диск возвращаетустаревшие данные. Да и весь путь ввода-вывода, который должны пройтиданные от момена прочтения с пластины диска до момента попадания впамять сервера (и наоборот) остается незащищенным. Короче говоря, такойвариант использования контрольной суммы блока есть лишь хороший способубедиться в том, что надёжность массива ничуть не ниже надёжностидисков, в нём содержащихся, но не более того. Способиспользования контрольной суммы блока, применяемый NetApp, выглядитпохоже, но на самом деле намного мощнее. Как и во многих другихмассивах, NetApp форматирует диски с секторами по 520 байт. Затем онигруппируются в блоки по 8 секторов: 4Кб данных (размер блока файловойсистемы WAFL) и 64 байта контрольной суммы. Когда система WAFL читаетблок, данные сравниваются с контрольной суммой, как и в случае смассивом из предыдущего примера, но с ключевым отличием: сравнениепроисходит после того, как данные прошли весь путьввода-вывода, что позволяет удостовериться в том, что блок прошел путьот пластины диска до памяти без повреждения. Это существенноеулучшение, но и его недостаточно. Контрольная сумма на уровне блокатолько доказывает, что блок цел сам по себе; она не доказывает, что этоправильный блок. Повторяя нашу аналогию с UPS: "Мы гарантируем, чтопосылка, которую вы получили, цела. Но мы не гарантируем, что это вашапосылка." Основная проблема со всеми этими схемами в том,что они не обеспечивают изоляцию сбоев между данными и контрольнойсуммой, их защищающей. Аутентификация данных в ZFS Сквозная целостность данных требует проверки каждого блока данных с использованием независимой контрольной суммы, послеприбытия данных в память. Недостаточно знать, что каждый блок являетсясам собой, или что он был корректен в какой-то момент прохождения попути ввода/вывода в прошлом. Наша цель - выявлять любые возможные формыповреждения, включая такие человеческие ошибки, как использование дискас файловой системой в качестве области подкачки, или опечатки варгументах команды dd(1). (Не приходилось ли вам место когда-нибудьвместо "if=" ввести "of="?) Пул дисковой памяти в ZFS -это, на самом деле, дерево блоков. ZFS обеспечивает изоляцию сбоевмежду данными и контрольной суммой за счет хранения контрольной суммыкаждого блока в указателе, указывающем на этот блок(указателе-родителе) -- а не в самом блоке. Каждый блок дерева содержитконтрольные суммы всех "детей", таким образом, весь пул оказываетсясамоверифицирующимся. [Вершина иерархии - убер-блок (uberblock, кореньдерева) - особый случай, так как он не имеет родителя; о том, как мыобращаемся с ним, поговорим в отдельной заметке.] Еслиданные не соответствуют контрольной сумме, ZFS может доверятьконтрольной сумме, поскольку контрольная сумма является частьюкакого-то другого блока, находящегося на предыдущем уровне в дереве, ацелостность этого вышележащего блока уже была проверена. ZFSиспользует сквозные контрольные суммы для выявления и исправлениянеявных нарушений целостности данных. Если диск возвращает некорректныеданные в результате случайного сбоя, ZFS определит это и попытаетсяпрочитать данные еще раз. Если диск является частью "зеркала" или RAID-Z,ZFS не только определит, но и исправит ошибку: контрольная суммапозволит определить правильную копию, предоставить корректные данныеприложению и исправить с их помощью поврежденную копию. Обратите внимание, что сквозная целостность данных в ZFS, как обычно, не требует специального аппаратного обеспечения. Нет нужды в дорогих дисках или массивах, нет необходимости переформатировать диски на сектора по 520 байт, не требуется модифицировать приложения для эффективного использования секторов увеличенного размера. Всё полностью автоматизировано и работает на недорогих дисках. Но и это еще не всё! Блоки пула дисковой памяти ZFS образуют дерево Меркле,в котором каждый блок проверяет всех своих "детей". Было доказано, чтодерево Меркле обеспечивает криптографически стойкую аутнтификацию какдля каждого компонента дерева, так и для всего дерева целиком. ZFSиспользует 256-битную контрольную сумму (алгоритм SHA-256) для каждогоблока (метаданных) и проддерживает алгоритмы вычисления контрольныхсумм для пользовательских данных начиная с простого и быстрогоалгоритма fletcher2 (используемого по умолчанию) до медленного, нобезопасного SHA-256.При использовании для пользовательских данных криптографически стойкогохеша, такого как SHA-256, контрольная сумма убер-блока являетсяпостоянно обновляющимся крипто-хэшем для всех данных в пуле. А это будет очень удобно, если вам потребуется обратиться в UPS для пересылки пула. Теги Technorati: OpenSolaris Solaris ZFS

Работу любой файловой системы можно свести к следующему: на просьбу прочитать блок данных, она должна вернуть те же самые данные, которые были ранее записаны в этот блок.Если этого сделать не...

ZFS

RAID-Z

Исходным обещанием технологии RAID (избыточный массивнедорогих дисков) было обеспечение быстрого надёжного хранилища сиспользованием дешёвых дисков. Ключевым пунктом была дешевизна; но каким-то образом мы оказались тут. Почему? ТехнологияRAID-5 (как и другие схемы организации данных и чётности, такие какRAID-4, RAID-6, чёт-нечет и строчно-диагональная чётность) никогда вполной мере не выполняла обещания RAID -- да и не может -- из-зарокового просчёта, известного как "окно уязвимости". При любомобновлении данных в сегменте RAID нужно обязательно изменить чётностьтак, чтобы применение операции "исключающее ИЛИ" к данным со всехдисков сегмента RAID-5 давало в результате 0 -- это то самое уравнение,которое позволяет реконструировать данные в случае выхода из строядиска. Проблема в том, что нет способа обновить содержимое двух илиболее дисков атомарно, одной неделимой операцией (то есть существуетвременное окно между выполнением двух операций записи, в течениекоторого система уязвима к сбоям), поэтому массив RAID может оказатьсяповреждённым в случае системной ошибки или отключения питания. Представьте,что питание пропадает после записи блока данных, но до записисоответствующего блока контроля чётности. Теперь блоки данных и блокконтроля чётности для данного сегмента RAID противоречивы, и останутсятаковыми навсегда (если только у вас не получится перезаписать старыеданные полностью путем записи полного сегмента в какой-то моментвремени). Поэтому в случае отказа диска процесс реконструкции RAIDсгенерирует "мусор" при следующем чтении любого блока из этогосегмента. Хуже всего то, что это происходит неявно -- массив RAID-5даже не будет подозревать, что возвращает вам некорректные данные. Дляэтой проблемы существуют чисто программные обходные пути, но онинастолько медленны, что программный RAID практически вымер и исчез срынка. Все доступные на данный момент продукты RAID используютреализации схем RAID на аппаратном уровне, где они могут использоватьэнергонезависимую память (NVRAM) для защиты от сбоев и пропаданияпитания. Этот вариант работает, но стоит дорого. Кроме этого,в существующих схемах RAID имеется серьёзная проблема спроизводительностью. При записи неполного сегмента -- то есть приобновлении меньшего количества данных, чем содержит один сегмент RAID,-- система RAID должна прочитать с диска значение старых данных ичётности для того, чтобы вычислить новое значение чётности. А этозаметно снижает производительность. Если при записи полного сегментаможно просто использовать асинхронную запись, запись неполного сегментатребует выполнения синхронных операций чтения прежде, чем может бытьначата какая бы то ни была запись. И снова предлагаетсядорогое аппаратное решение: массив RAID может буферизировать операциизаписи неполного сегмента в энергонезависимой памяти (NVRAM) на времяожидания завершения необходимых операций чтения, скрывая таким образомот пользователя задержку, добавляемую ими. Естественно, это работает дотех пор, пока не происходит переполнения буфера NVRAM. Нет проблем,говорят продавцы устройств хранения! Просто подкиньте деньжат надополнительные устройства NVRAM. Ведь нет задачи, с которой несправился бы бумажник. Запись неполного сегмента создаётдополнительную проблему для транзакционной файловой системы, такой какZFS. Запись неполного сегмента неизбежно требует модификации актуальныхданных, что нарушает одно из правил транзакционной семантики. (В ZFSневажно, пропадёт ли питание при записи полного сегмента по той жепричине, по которой неважно, что пропадёт питание при любой другойоперации записи в файловую систему: ни один из блоков, в которыепроизводится запись, не содержит актуальных данных.) Если бы только не эти дьявольские записи неполных сегментов... Встречайте RAID-Z RAID-Zпредставляет собой схем�� организации данных и четности, подобнуюRAID-5, но использующую динамический размер сегмента. По сути, каждыйлогический блок файловой системы -- это сегмент RAID-Z, независимо отразмера блока. Это значит, что каждая запись RAID-Z -- это записьполного сегмента. Добавьте к этому копирование при записи втранзакционной семантике ZFS, и вы полностью избавитесь от "окнауязвимости" RAID. Кроме этого, RAID-Z быстрее обычного RAID, так какздесь не требуется читать данные, менять их, а потом снова записывать. Стоп,стоп, стоп -- что это? Переменный размер сегмента? Выглядит довольноочевидно. Но если это настолько хорошая идея, почему же все ей непользуются? Оказывается, что ключевой момент здесь --реконструкция RAID-Z. Так как сегменты RAID-Z имеют различный размер,простая формула "исключающее ИЛИ с данных со всех дисков равно нулю"становится неприменима. Для определения геометрии сегмента RAID-Z нужныметаданные файловой системы, для реконструкции всех сегментов придетсяобойти метаданные всей файловой системы. Заметим, что это было быневозможно, если бы файловая система и RAID-массив были бы отдельнымипродуктами, и именно поэтому на рынке систем хранения данных сегоднянет ничего подобного RAID-Z. Нужен комплексный взгляд на логическую ифизическую структуру данных, чтобы справиться с этой задачей. "Минуточку,не слишком ли это медленно?" - спросите вы. Не слишком ли дорогообходить все метаданные? Фактически это компромисс. Если пул с даннымиочень близок к заполнению, тогда да, это медленнее. Но если пул неочень-то заполнен, тогда реконструкция по метаданным будет быстрее, таккак копироваться будут только актуальные данные и не нужно будеттратить время на реконструкцию участков неиспользуемого дисковогопространства. Гораздо важнее то, что проход по метаданнымпозволяет ZFS в процессе сверить каждый блок с его 256-битнойконтрольной суммой. Традиционные RAID-системы не могут этого сделать,они лишь вслепую выполняют операцию исключающего ИЛИ. Этоподводит нас к отличительной особенности RAID-Z: самовосстановлениюданных. Помимо обработки отказов диска целиком, RAID-Z может выявлять иисправлять неявные повреждения данных. При каждом чтении блока RAID-Zвыполняется его проверка на соответствие контрольной сумме. Еслипроверка покажет, что диски с данными вернули неправильное содержимоеблока, то ZFS прочитает диск с чётностью и выполнит комбинаторнуюреконструкцию данных для выявления диска, вернувшего неправильныеданные. Затем ZFS восстановит поврежденные данные и вернет правильныеданные приложению. Помимо этого, ZFS сообщит об этом инциденте,используя Solaris FMA, так что системный администратор будет знать, чтос одним из дисков проблема. В завершение хочется отметить, что для RAID-Z не нужно никакого специального аппаратного обеспечения.Для обеспечения корректности не нужна энергонезависимая память (NVRAM),а для хорошей производительности не нужна буферизация операций записи.С помощью RAID-Z система ZFS выполняет исходное обещание RAID:обеспечить быстрое, надёжное хранилище данных с использованиемнедорогих дисков. Реальный пример выявления и исправления неявного повреждения данных ненадёжным "железом" можно найти здесь: Eric Lowe's SATA saga. Первоначальнаяверсия RAID-Z поддерживала только один разряд четности, но концепцияRAID-Z работает для любых видов RAID. Текущая версия поддерживает и дваразряда четности, в этом случае ее обычно называют RAID-Z2. И ещё один момент, который оценят коллеги-программисты: полная реализация RAID-Z занимает всего 599 строк. Теги Technorati: OpenSolaris Solaris ZFS

Исходным обещанием технологии RAID (избыточный массив недорогих дисков) было обеспечение быстрого надёжного хранилища с использованием дешёвых дисков. Ключевым пунктом была дешевизна; но каким-то...

ZFS

Быстрые зеркала

Восстановление зеркальной копии (иливосстановление избыточности, так как это применимо не только кзеркалам) -- также известное как ресинхронизация, перестройка илиреконструкция -- это процесс исправления поврежденного устройства сиспользованием содержимого нетронутых устройств. Это то, что долженсделать любой менеджер томов или RAID-массив в случае отказа, заменыили кратковременной недоступности диска. В случае зеркалавосстановление избыточности может быть не сложнее простого копированиядиска целиком. В случае RAID-5 процедура немногим сложнее: вместокопирования одного диска на другой, нужно вычислить "исключающее ИЛИ"для данных на остальных дисках сегмента RAID-5 и использоватьполучившийся результат для восстановления избыточности. Но основнаяидея все та же. В традиционных системах хранения данных,восстановление избыточности происходит в менеджере томов илиRAID-контроллере. Но и в том, и в другом случае - гораздо ниже уровняфайловой системы. Но мы говорим о ZFS, так что хочешь-не хочешь, а нужно быть отличным. В предыдущей заметке я упоминал о том, что восстановление избыточности для RAID-Z требуетдругого подхода, так как для определения геометрии сегмента RAID-Zнужны метаданные файловой системы. В сущности, ZFS делает 'cp -r'дерева блоков пула с одного диска на другой. Это кажется болеемедленным, чем прямолинейное копирование диска целиком, да и обходдерева блоков в активно использующемся пуле определенно нетривиальнаязадача (но подробнее об этом в будущей заметке). Но, как оказалось, увосстановления избыточности по метаданным так много преимуществ, что мыпредпочли использовать его даже для простых зеркал. Самая важная причина - целостность данных. При простом копировании диска не узнаешь, корректны ли данные на исходном диске. Сквозная целостность данных требует сверки каждого блока данных с независимойконтрольной суммой -- нам недостаточно знать, что блок является самсобой, так как это не позволяет обнаружить типичные аппаратные ошибки иошибки в микрокоде, такие как, например, неверно адресованное чтение ифантомная запись. Обходя дерево блоков по метаданным,система ZFS может использовать сквозные контрольные суммы для выявленияи исправления неявных повреждений данных, так же, как ZFS делает этопри обычном чтении блоков. Если диск вернул некорректные данные из-закратковременного сбоя, ZFS определит это и попытается прочитать данныееще раз. В случае тройного зеркала и повреждения одного из двухисправных дисков, предположительно содержащих целостные данные, ZFSвоспользуется контрольной суммой для определения диска, содержащегоцелостные данные, затем скопирует целостные данные данные на новый диски восстановит содержимое поврежденного. При прямолинейномкопировании всего диска данные не проходит такую проверку. Уже по однойэтой причине восстановление избыточности по метаданнымпредпочтительнее, даже если за это придется заплатить ощутимой долейпроизводительности. К счастью, в большинстве случаев это не так. Фактически, восстановление избыточности по метаданным имеет несколько преимуществ: Только актуальные блоки:ZFS не тратит время и ресурсы каналов ввода/вывода на копированиенеиспользуемых блоков диска, так как они не являются частью дереваблоков пула. Если пул заполнен на 10-20%, выигрыш будет значительным Исключение транзакций:если диск был недоступен короткое время, нет необходимостивосстановления избыточности для всего диска -- только для измененнойчасти. Это будет описано подробнее в следующей статье, но вкратце: ZFSиспользует время создания каждого блока для того, чтобы определить,есть ли необходимость восстанавливать избыточность для потомков этогоблока в дереве. Это позволяет пропускать большие поддеревья и быстронаходить данные, которые действительно были изменены с того момента,когда диск стал недоступен. На практике это означает, чтоесли диск был недоступен пять секунд, восстановление избыточностиданных займет около пяти секунд. И за это не надо дополнительно платить-- ни деньгами, ни производительностью -- не в пример тому, как этоделается с помощью механизма объектов изменений (change objects) вVeritas. Исключение транзакций является важной архитектурнойособенностью ZFS. Нисходящее восстановление:пул дисковой памяти - это дерево блоков. Чем ближе к корню дереванаходится блок, тем значительнее его потеря, так как она означаетпотерю доступа к во всем потомкам этого блока. Использованиеметаданных позволяет ZFS осуществлять нисходящее восстановлениеизбыточности. Это значит, что в первую очередь ZFS восстановитубер-блок и метки диска. Затем будет восстановлена избыточностьметаданных, общих для всего пула; затем метаданных каждой файловойсистемы; и так далее вниз по дереву. В ходе этого процесса ZFS следуеттакому правилу: ибыточность блока не восстанавливается до тех пор, покане восстановлена избыточность всех его предков. Труднопреувеличить важность этого правила. При прямолинейном копированиивсего диска, даже если успешно скопировано 99%, есть неплохой шанс, чтоодин из верхних блоков дерева еще не скопирован. С точки зрениясреднего времени восстановления после отказа (MTTR) это значит, чтопрогресса нет: отказ или ошибка второго диска в этот момент времени всееще будет иметь катастрофические последствия. При нисходящемвосстановлении избыточности, копирование каждого следующего блокаувеличивает количество данных, которые могут быть обнаружены. В случаесбоя еще одного диска, все данные, избыточность которых былавосстановлена до этого момента, останутся доступными. Приоритетное восстановление избыточности.ZFS еще не делает этого, но скоро будет. В ZFS восстановление следуетза логической структурой данных, так что будет довольно просто пометитьотдельную файловую систему или файлы как приоритетные длявосстановления избыточности. Например, на файловом сервере может бытьпредпочтительнее в первую очередь восстановить избыточность календарей(они, как правило, очень малы и очень важны), затем каталог /var/mail,затем домашние каталоги пользователей и т.д. Я надеюсь каждой их этих заметок донести не то, как устроенымеханизмы той или иной особенности ZFS, а проиллюстрировать, как всечасти ZFS составляют единое целое. Например, может быть совсем неочевидно, что транзакционная семантика ZFS имеет какое-либо отношение кпроцессу восстановления избыточности, тем не менее исключениетранзакций позволяет осуществить восстановление после кратковременнойнедоступности диска в буквальном смысле на порядки быстрее. Подробнее отом, как это работает -- в следующей заметке.

Восстановление зеркальной копии (или восстановление избыточности, так как это применимо не только к зеркалам) -- также известное как ресинхронизация, перестройка илиреконструкция -- это процесс...

ZFS

Безудержное нарушение принципа многоуровневости?

Эндрю Мортон лихо назвал ZFS "безудержным нарушением принципа многоуровневости",поскольку она она объединяет в себе функциональность файловой системы,менеджера томов и контроллера RAID. Я полагаю, все зависит от значенияслова нарушить . При разработке ZFS мы обнаружили, чтостандартное разделение на уровни в стеке управления данными приводит кудивительному количеству ненужной сложности и дублированю логики. Мыобнаружили, что путем небольшого рефакторинга -- то есть, изменениятого, где проходят границы между уровнями, -- можно сделать всю системугораздо проще. Пример из математики послужит отличным прологом. Предположим, вам нужно подсчитать сумму 1/n(n+1) для n от единицы до бесконечности. Раскрыв это выражение для каждого слагаемого, мы получим:         1/(1\*2) + 1/(2\*3) + 1/(3\*4) + 1/(4\*5) + ... то есть:         1/2 + 1/6 + 1/12 + 1/20 + ... Кчему сходится этот бесконечный ряд? Это может показаться труднойзадачей, но это только потому, что мы неверно смотрим на нее. Если выдостаточно сообразительны, вы, наверное, уже заметили, что каждоеслагаемое можно представить по-другому:         1/n(n+1) = 1/n - 1/(n+1) Например,         1/(1\*2) = 1/1 - 1/2        1/(2\*3) = 1/2 - 1/3        1/(3\*4) = 1/3 - 1/4 Таким образом, наша сумма примет вид:         (1/1 - 1/2) + (1/2 - 1/3) + (1/3 - 1/4) + (1/4 - 1/5) + ... Теперьзаметим следующее: каждую вычитаемую часть мы снова прибавляем. Заполезную работу это может сойти разве что в Конгрессе. Так что если мыпросто изменим порядок скобок -- то есть, если мы безудержно нарушимделение исходной задачи на уровни, воспользовавшись правиломассоциативности для группировки соседних слагаемых с разными знаками,-- мы получим следующее:         1/1 + (-1/2 + 1/2) + (-1/3 + 1/3) + (-1/4 + 1/4) + ... или         1/1 + 0 + 0 + 0 + ... Другими словами,         1. Разве это не здорово? Дляобозначения этого у математиков есть подходящий термин. Когда выпереставляете элементы ряда так, что они взаимно уничтожаются, этоназывается вложение -- по аналогии с подзорной трубой. В двухсловах, это как раз то, что делает ZFS: вложение элементов стекауправления данными. Это позволяет нам получить файловую систему,менеджер томов, массив RAID с одним и двумя разрядами четности, сжатие,снимки, клоны и кучу других полезных вещей всего лишь в 80000 строккода. Конечно, системы хранения данных гораздо сложнее этойпростой аналогии, но на высоком уровне такая идея вполне применима.Любой стек управления данными можно представлять себе какпоследовательность преобразований из одной схемы именования в другую -в конечном счете переводящей имя файла в логический адрес блока надиске (LBA - Logical Block Address). Обычно это выглядит следующимобразом:         файловая система(сверху): имя файла - объект (inode)        файловая система(снизу): объект - LBA тома        менеджер томов: LBA тома - LBA массива        контроллер RAID: LBA массива - LBA диска Рефакторинг этого стека мы собираемся произвести. Во-первых, отметим, что традиционный уровень файловой системыслишком монолитен. Лучше будет разделить часть, отвечающую затрансляцию "имя файла - объект" (верхняя половина), и часть, отвечающуюза трансляцию "объект - LBA тома" (нижняя половина); так мы сможемповторно использовать нижнюю половину кода для поддержки других типовхранилищ данных, например объектов и томов iSCSI, которые не имеютимени файла. Тогда такие классы хранилищ смогут напрямуювзаимодействовать с уровнем объектов. Это более эффективно, чемиспользовать механизм /dev/lofi, который позволяет придать файлу POSIXвид блочного устройства. Но что более важно, это дает возможностьиспользовать новую мощную программную модель -- хранилище объектов --без дополнительного кода. Во-вторых, отметим, что уровень LBA тома полностью бесполезен.Добавление уровня косвенности часто увеличивает гибкость, но не вданном случае: это можно сравнить с переводом сначала с английского нафранцузский, а потом с французского на немецкий, в то время как мылегко можем перевести сразу с английского на немецкий. Промежуточныйфранцузский не имеет особого значения. Он не виден ни приложениям, нимассиву RAID, и не выполняет никакой административной функции. Этонакладные расходы в чистом виде. Поэтому в ZFS этот уровень вложен. В ZFS есть три четких уровня:ZPL (ZFS POSIX Layer), который обеспечивает стандартную семантикуфайловой системы POSIX; DMU (Data Management Unit), которыйобеспечивает многоцелевое транзакционное хранилище объектов; и SPA(Storage Pool Allocator), обеспечивающий манипуляцию блокамивиртуального хранилища и преобразование данных (репликацию, сжатие ивскоре шифрование). В целом стек преобразований в ZFS выглядит так:         ZPL: имя файла - объект        DMU: объект - DVA (data virtual address)        SPA: DVA - LBA диска DMUобеспечивает файловый и блочный доступ к общему пулу физическихнакопителей. Файловый доступ осуществляется через ZPL, блочный доступ(через блочное устройство) представляет собой прямое отображение наодин объект DMU. Мы также разрабатываем новые методы доступа к данным,которые используют транзакционные возможности DMU более интереснымиспособами -- но об этом в другой раз. Архитектура ZFS устраняет целый уровень трансляции -- и вместе с тем целый класс метаданных (LBA тома).  Она также исключает необходимость аппаратных контроллеров RAID. В то же время, ZFS предоставляет новый полезный интерфейс -- хранилищеобъектов -- который был до этого недоступен, будучи похоронен внутримонолитной файловой системы. Я точно не вижу здесь никакого нарушения.  А вы?

Эндрю Мортон лихо назвал ZFS "безудержным нарушением принципа многоуровневости", поскольку она она объединяет в себе функциональность файловой системы,менеджера томов и контроллера RAID. Я полагаю,...

ZFS

Карты пространства

Каждая файловая система должна следить за двумя основными вещами: где находятся данные, а где свободное пространство. В принципе, отслеживание свободного пространства необязательно:каждый блок либо занят, либо свободен, поэтому свободное пространствоможет быть рассчитано как всё пространство за исключением занятого; азанятое пространство может быть обнаружено путем обхода всей файловойсистемы от корня. Блок, не найденный при обходе, свободен поопределению. На практике, поиск свободного пространства таким путём неприемлем,так как требует слишком много времени для любой файловой системынетривиального размера. Чтобы сделать выделение и освобождение блоковбыстрым, файловой системе нужен эффективный способ отслеживаниясвободного пространства. В этой заметке мы рассмотрим наиболеераспространенные методы, присущие им проблемы масштабирования и новыеподходы, разработанные для ZFS. Битовые картыНаиболее распространенный способ представить свободное пространство -использовать битовую карту. Битовая карта - это просто битовый массив,в котором бит с номером N указывает, свободен ли блок с номером N.Накладные расходы на битовую карту невелики: 1 бит на блок. Для блока в4Кб, это 1/(4096\*8) = 0,003% от размера блока (здесь 8 - количество битв байте). Для файловой системы в 1Гб битовая карта займет 32Кб -- её можнодержать в оперативной памяти и довольно быстро сканировать для поискасвободного пространства. Для файловой системы в 1Тб размер битовойкарты составит уже 32 Мб -- такой объём ещё можно уместить воперативной памяти, но это уже нетривиально в смысле размера и временисканирования. Битовая карта для файловой системы в 1Пб потребует уже32Гб, и уже просто-напросто не поместится в оперативной памятибольшинства машин. Следовательно, сканирование битовой карты в этомслучае потребует её чтения с диска, который намного медленнееоперативной памяти. Ясно, что такой способ плохо масштабируется. Очевидным выходом является разделение битовой карты на небольшиечасти и хранение количества битов, установленных в каждой из них.Например, для файловой системы в 1Пб с размером блока в 4Кб, свободноепространство может быть разделено на миллион битовых карт, размеркаждой из которых составит 32Кб. Сводная информация -- миллион целыхчисел, хранящих количество установленных битов в соответствующейбитовой карте -- уже поместится в оперативной памяти, поэтому можнобудет достаточно легко найти битовую карту со свободным местом ипросканировать её для поиска места. Но это не избавляет нас от одной фундаментальной проблемы: битовыекарты нужно обновлять не только когда выделяется новый блок, но итогда, когда блок освобождается. Файловая система может управлятьлокальностью выделяемых блоков (решать, в каком месте размещать новыеданные), но не имеет никакого способа влиять на положение освобождаемыхблоков. Простая команда вроде 'rm -rf' может вызвать освобождениеблоков, разбросанных по всему диску. Например, удаление 4Гб данных(т.е. миллиона блоков по 4Кб) из нашей файловой системы размером в 1Пбпотребует, в худшем случае, чтения, изменения и повторной записимиллиона битовых карт. Это означает два миллиона дисковых операцийввода/вывода для освобождения каких-то 4Гб -- что неразумно даже вхудшем случае. Этот фактор в большей степени, чем другие, является причиной плохоймасштабируемости битовых карт: так как освобождение блоков частопроисходит случайно, битовые карты, не помещающиеся в памяти,демонстрируют патологическую производительность при случайныхпоследовательностях операций освобождения. Сбалансированные деревьяДругим распространенным способом представления свободного пространстваявляется использование сбалансированного дерева диапазонов. Диапазонпредставляет собой непрерывный участок свободного пространства,описываемый двумя целыми числами: смещением и размером. Сортировкад��апазонов в сбалансированном дереве по смещению позволяет эффективнореализовать поиск и выделение непрерывных кусков пространства. Ксожалению, сбалансированные деревья диапазонов при работе со случайнымипоследовательностями операций освобождения страдают от той же проблемы,что и битовые карты. Что же делать? Отложенное освобождение Одиниз способов уменьшить проблему случайного освобождения - это отложитьобновление битовой карты или сбалансированного дерева, а вместо этогохранить список недавно освобождённых блоков. Когда этот списокдостигнет определенного размера, он может быть отсортирован в памяти ивключён в нужное место битовой карты или дерева, возможно, с лучшейстепенью локальности. Не идеально, но уже лучше. А если пойти дальше? Карты пространства: списки диапазонов с журнальной структурой Вспомним,что файловые системы с журнальной структурой уже ставили такой вопросдовольно давно: что, если вместо периодической свёртки журналатранзакций обратно в файловую систему, сделать сам журнал транзакций файловой системой? Такой же вопрос можно поставить и по отношению к нашему спискуотложенных операций: что, если вместо свёртки в битовую карту илидерево сделать сам список отложенных операций представлением свободного пространства? Именнотак и сделано в ZFS. Пространство каждого виртуального устройства в ZFSразделено на несколько сотен регионов, называемых метаслабы (metaslab).С каждым метаслабом связана карта пространства, которая описываетсвободное пространство в метаслабе. Карта пространства (на диске) - этопросто-напросто журнал операций выделения и освобождения блоков,упорядочненный по времени (точнее, номеру группы транзакций). Картыпространства делают случайные операции освобождения такими жеэффективными, как и последовательные, потому что независимо отположения освобождаемого блока, на диске он представляется добавлениемсоответствующего диапазона (пары целых чисел - смещения и размера) кобъекту "карта пространства" -- а добавление имеет идеальнуюлокальность. Операции выделения блоков представляются на дискеаналогично - добавлением диапазона к объекту "карта пространства" надиске с единственным отличием - установленным битом, показыващим, чтоэто операция выделения, а не освобождения. Когда ZFS принимает решение о выделении блоков из определенногометаслаба, она сперва читает карту пространства этого метаслаба с дискаи применяет операции выделения и освобождения блоков к AVL-деревусвободных диапазонов в памяти, отсортированному по смещению. Этопозволяет получить компактное представление свободного пространстваэтого метаслаба в памяти, которое обеспечивает эффективный поиск ивыделение непрерывных кусков пространства. ZFS также используетпредставление в памяти как шанс сократить размер карты пространства надиске: если список на диске содержит большое количество взаимноуничтожающихся операций выделения/освобождения блоков, старый журнал надиске заменяется новым, содержащим меньшее количество диапазонов. Карты пространства имеют несколько интересных свойств: Нетребуют инициализации: карта пространства без записей показывает, чтоопераций выделения и освобождения блоков не было, все пространстводоступно Хорошо масштабируются: поскольку новыедиапазоны только добавляются в конец объекта "карта пространства", дляполучения наилучшей производительности в памяти нужно хранить тольколишь последний блок этого объекта, вне зависимости от того,пространством какого размера мы управляем Неподвержены патологиям: карты пространства можно эффективно обновлять,независимо от последовательности операций выделения и освобождения Одинаковоэффективны при выделении свободного места, как при пустом, так и призаполненном пуле (в отличие от битовых карт, на сканирование которыхтребуется всё больше и больше времени по мере их наполнения) Помимоэтого, нужно отметить, что когда свободное пространство, описываемоекартой, полностью исчерпано, для ее представления достаточно одногодиапазона. Поэтому карты пространства имеют прекрасное свойство: помере приближения заполненности пула к 100%, карты пространств�� начинаютбуквально "испаряться", занимая всё меньше и меньше места, даваявозможность максимально использовать имеющееся дисковое пространстводля хранения полезной информации.

Каждая файловая система должна следить за двумя основными вещами: где находятся данные, а где свободное пространство. В принципе, отслеживание свободного пространства необязательно:каждый блок либо...

ZFS

ZFS におけるエンド・ツー・エンドのデータ整合性

ブロックの読み込み要求をした場合、前回そのブロックに書き込んだときと同じデータが返ってこなければなりません。どんなファイルシステムでも、その役割は結局ここに行き着きます。ディスクがオフラインであるとか、データが破損したとか、改ざんされたなどの理由で、もし同じデータを返せないのなら、それを検出してエラーを返さなければなりません。 驚くべきことに、ほとんどのファイルシステムがこの課題をクリアできません。そのようなファイルシステムでは、エラーの検出と報告を下位のハードウェアに頼っています。もしディスクが何の報告もせずただ誤ったデータだけを返した場合、標準的なファイルシステムはそれを検出することすらできません。 たとえすべてのディスクが完璧に動作すると仮定できたとしても、入出力経路上のデータはまだ安全ではありません。コントローラのバグやDMA パリティーエラーなどがありえます。ユーザーにわかるのは、プラッタから読み取る瞬間までデータが完全だったというところまでです。データを小包に例えると、USP が「集荷の際にお荷物に損傷がなかったことを保証いたします」と言うようなものです。ユーザーが求めている信頼性とは少々異なります。 転送中のデータ破損は、単なる学問的な興味の対象ではありません。電源供給の誤切断のようなありふれた原因で、データのサイレント破損が起きます。 高価なストレージアレイをオプションで購入しても、問題の解決にはなりません。I/O パスが脆弱なままで、しかも経路が延びてしまいます。プラッタから読み取ったあと、ハードウェアやファームウェアにどのようなバグがあってもデータが無事であることを、ストレージアレイが保証しなければなりません。 もし SAN を使っているなら、ディスクのファームウェア技術者が設計したネットワークを使っていることになります。ご愁傷様。 どうすればよいのでしょうか。すべてのディスクブロックについてチェックサムを保存しておくという方法があります。近年のディスクドライブは、通常の 512 バイトよりもわずかに大きいセクターサイズ (520 か 528 バイトが一般的) でフォーマットして、余分に確保した領域にブロックのチェックサムを保存することができます。しかし、このチェックサムを有効活用するのは思ったほど簡単ではありません。チェックサムの有効性は、どこにチェックサムを保存するかと、いつチェックサムの検証を行うかに、恐ろしいほど依存しているからです。 多くのストレージアレイでは、アレイの内部でデータとチェックサムを比較します。Dell|EMC PowerVault のレポートに、すばらしい解説つきで一般的な例が掲載されています。残念ながら、これではあまり役に立ちません。データとチェックサムが同じユニットに保存されるため、書き込み成功の誤報告 (前回書き込んだはずの内容がディスクに書き込まれていない) など、よくあるファームウェアのバグを検出できません。つまり、ディスクが古いデータを返しても、チェックサムは一致します。しかも、アレイからホストまでの I/O パスは保護されないままになっています。つまりこの種のブロックチェックサムは、ストレージアレイが搭載しているディスクと比較して信頼性で劣っていないということを保証するのに適した手段になりますが、それだけなのです。 チェックサムをブロックに追加する NetApp のアプローチも似たようなものに見えますが、実はかなり違います。ほかの多くのアレイと同様に、NetApp ではドライブを 520 バイトセクターでフォーマットします。その上で、8 セクターでひとまとまりのブロックを作ります。4K のデータ (WALF ファイルシステムのブロックサイズ) と 64 バイトのチェックサムを保存可能な容量になります。WAFL がブロックを読み込むと、ほかのアレイと同様にチェックサムとデータを比較しますが、決定的な違いがあります。データが I/O パスを通過したあとに比較を行うので、プラッタで読み取られたデータブロックが経路上で破損することなくメモリに到着したかどうか検証できます。 これは大きな進歩ですが、まだ十分ではありません。ブロックレベルのチェックサムは、ブロックが同一性を保っていることを保証するのみで、それが正しいブロックであるかどうか確認できません。UPS のたとえでいうと「荷物が途中で破損しなかったことを保証しますが、お客様の荷物かどうかは保証しません」ということになります。 ここまで紹介したスキーマすべてに共通する根本的な問題は、データとそれを保護するチェックサムを分けずに保管しているという点です。 ZFS のデータ確認 エンド・ツー・エンドのデータ整合性を得るには、すべてのデータブロックが、別途保存されたチェックサムで、データがホストのメモリに到達したあとに、検証される必要があります。各ブロックが単に同一性を保っているとか、I/O パスのある時点で正しかったなどというだけでは、不十分です。私たちの目標は、ディスクの入れ間違いや dd(1) コマンド引数のミスタイプなどのヒューマンエラーも含めて、想定しうるすべての破損を検出することです。「if=」と入力しようとして「of=」とタイプしてしまったことはありませんか。 ZFS のストレージプールはブロックをツリー状に集めただけのものです。ZFS は、各ブロックのチェックサムを、そのブロック自体と同じ場所ではなく、親ブロックのポインタに保存することで、データとチェックサムの問題を��り分けています。ツリー上のすべてのブロックが子ブロックのチェックサムを持っており、プール全体で破損の検証が可能です。(最上位ブロック (ツリーのルート) は例外で、親ブロックがありませんが、どのように処理しているかは後日投稿します。) データとチェックサムが一致しない場合、チェックサムを保存してあるツリー上の 1 段上の階層のブロックはすでに検証が済んでいるため、ZFS はチェックサムを信頼できると判断できます。 ZFS は、このエンド・ツー・エンドのチェックサムを利用して、データのサイレント破損を検出し訂正しています。ディスクから不正なデータが返ってきた場合、ZFS がこれを検出して読み取りをリトライします。ディスクがミラーまたは RAID-Z を構成している場合、ZFS はエラーの検出と訂正の両方を行います。チェックサムと比較してどちらのコピーが正しいかを判断し、アプリケーションに正常なデータを送り、破損したコピーを訂正します。 何度も書いていますが、ZFS のエンド・ツー・エンドデータ整合性には特別なハードウェアが必要ないことに注目してください。高価なディスクやストレージアレイを購入する必要も、ディスクを 520 バイトセクターで再フォーマットする必要も、エラー訂正を有効にするためにアプリケーションの設定をする必要もありません。すべて自動で、安価なディスクでも機能します。 もう少しだけ ZFS ストレージプールのブロックは、各ブロックが子ブロックを検証する Merkle ツリーを構成します。Merkle ツリーは、ツリーのどの部分についても、またツリー全体についても、暗号学的に強力な検証方式であることが知られています。ZFS は各ブロックに 256 ビットのチェックサムを用意しており、単純で高速な fletcher2 (デフォルト) から、速度は落ちるものの安全性の高い SHA-256 まで、チェックサムの種類を選択することができます。SHA-256 のような暗号学的ハッシュを用いる場合、最上位ブロックのチェックサムが常に、ストレージプール全体に関する最新のデジタル署名として機能します。 UPS に運送を頼むなら、どの方法が便利でしょうか。Technorati タグ:OpenSolaris Solaris ZFS

ブロックの読み込み要求をした場合、前回そのブロックに書き込んだときと同じデータが返ってこなければなりません。どんなファイルシステムでも、その役割は結局ここに行き着きます。ディスクがオフラインであるとか、データが破損したとか、改ざんされたなどの理由で、もし同じデータを返せないのなら、それを検出してエラーを返さなければなりません。 驚くべきことに、ほとんどのファイルシステム...

ZFS

ミラーの同期ずれ

ミラー再同期 (Resilvering) は、破損が起きたドライブのデータを、正常なほかのディスクの内容を元に修復する作業のことで、再構築、リビルド、再構成などと呼ぶこともあります。どんなボリュームマネージャーや RAID アレイでも、ディスクが寿命になった場合、交換した場合、一時的な停止があった場合などには必ず、この作業をしなければなりません。 ミラーリングの場合、単にディスク全体をコピーするだけで再同期できます。RAID-5 の場合は、少しだけ複雑になります。あるディスクからほかのディスクにデータをコピーするのではなく、RAID-5 ストライプを構成する全ディスクの XOR を取ります。どちらも、基本的な考え方は同じです。 従来のストレージシステムでは、ボリュームマネージャーか RAID ハードウェアのどちらかが再同期を行なっていました。いずれにせよ、ファイルシステムよりもずっと下のレイヤーでの処理になります。 しかし、私たちが使っているのは ZFS です。従来のファイルシステムと同じなどということはありません。 以前の投稿で RAID-Z の再同期に通常とは異なるアプローチが必要だという話に触れました。RAID-Z のジオメトリを判断するためにメタデータが必要になるからです。実質的には ZFS が、あるディスクからほかのディスクに、ストレージプールのブロックツリーを「cp -r」します。単純にディスク全体をコピーするのと比べて効率が悪く、ライブプールの走査を安全に行うのは厄介な問題だと感じるかもしれません (詳細な情報を後日投稿します)。しかし、メタデータを基にした再同期には多くの利点があるため、単純なミラーリングに対しても、私たちはこの方法を採用しています。 もっとも説得力のある理由は、データの整合性です。単純なディスクコピーでは、コピー元のディスクが正常なデータを返しているかどうか、確認する手段がありません。エンド・ツー・エンドのデータ整合性を実現するには、各データブロックについてそれぞれ別途保存されたチェックサム確認をしなければなりません。各ブロックが変化していないことを確認するだけでは、誤ったブロックからの読み取りや書き込み成功の誤報告など、ハードウェアやファームフェアに見られる一般的なバグを把握できないため、不十分です。 ZFS ではメタデータを走査することで、通常の読み取りを行う場合と同様に、エンド・ツー・エンドのチェックサムを用いたサイレント破損の検出と修正ができます。ディスクから不正なデータが返ってきた場合、ZFS がこれを検出して読み取りをリトライします。3 ウェイミラーリングで、正常であるはずのミラー 2 つのうち 1 つが実は破損していた場合、ZFS がチェックサムを用いてどちらのミラーが正しいのか判断し、新しいディスクにデータをコピーして、破損したディスクのデータを修正します。 単純なディスク全体のコピーでは、このようなデータ保護は機能しません。このことを考えただけでも、たとえパフォーマンス的にそれなりのコストがかかったとしても、メタデータを元にした再同期が望ましいのです。 幸いなことに、ほとんどの場合パフォーマンスはそれほど低下しません。それどころか、メタデータを元にした再同期のほうが優れている点もあります。 ライブブロックだけを読み取る。 ZFS では、未割り当てのディスクブロックのコピーで時間や入出力帯域を無駄にすることがありません。未割り当てブロックは、ストレージプールのブロックツリーに含まれないからです。プールの容量を 10 から 20% しか使っていないなら、これは大きな利点です。 トランザクションの効率化。ディスクに一時的な停止が起きた場合、ディスク全体を再同期する必要はなく、変更があった部分だけで済みます。詳細は後日投稿しますが、概要は次のとおりです。ZFS は、各ブロックの作成時刻を用いて、ツリーの下位に再同期が必要な部分があるかどうか判断します。これにより巨大なツリー全体を検証する必要がなくなり、不具合発生後にデータが変更された部分をすばやく発見できます。 実用上の意義としては、たとえばディスクが 5 秒間の不具合を起こした場合、再同期にも約 5 秒間しかかかりません。しかもこの機能は Veritas の変更オブジェクトを使う場合と違い、コスト (金銭面でもパフォーマンス面でも) がかかりません。トランザクションの効率化は、ZFS アーキテクチャーの本質的な機能です。 トップダウン式の再同期。ストレージプールはブロックをツリー状に集めたものです。ツリーの上位であればあるほど、ブロックが破損した場合に大きな被害をもたらします。破損したブロックより下位にアクセスすることができなくなるためです。 ZFS では、メタデータの走査によりトップダウン式の再同期が可能です。つまり、ZFS では最上位ブロックとディスクラベルから再同期が始まります。その後、プール全体のメタデータ、ファイルシステムのメタデータと続けて、同様にツリーの下位へと進みます。この手順全体を通して ZFS は、次のルールに従います。つまり、上位ブロックの再同期が完了していないブロックは再同期しない、というルールです。 このことの大切さは、どんなに強調しても足りないくらいです。ディスク全体のコピーでは、コピーが 99% まで進んでも、ツリー最上位 100 ブロックのうちいずれかがまだコピーされていない、という可能性がかなりあります。MTTR の観点からは、まったく作業が進んでいないのと同じことになります。さらに、このタイミングで 2 台目のディスクも故障すると、大変なことになります。 トップダウン式の再同期では、ブロックを 1 つコピーするごとにアクセス可能なデータが増えます。2 台目のディスクが故障したとしても、故障の直前までに再同期したデータすべてにアクセスできます。 優先度に従った再同期。ZFS でまだ実現していませんが、実装中の機能です。データの論理構造に従った再同期を行うことで、ファイルシステムやファイルごとの再同期優先度を簡単に指定できるようにします。たとえばファイルサーバーで、非常に小さいものの重要なデータであるカレンダーを最初に、次に /var/mail、次にホームディレクトリを再同期したい、などです。 ここ一連の投稿で私が伝えたいことは、単に各機能の実装がどのようなメカニズムなのかということではなく、ぞれらを統合した ZFS 全体がどのようなものなのかということです。これは、ぱっと見ただけではわからないことです。たとえば、トランザクションのセマンティクスは再同期と何の関係もありませんが、トランザクションの効率化により、一時的な故障から非常に短時間で復旧ができます。次回のポストで、この仕組みがどのように機能しているのか紹介します。

ミラー再同期 (Resilvering) は、破損が起きたドライブのデータを、正常なほかのディスクの内容を元に修復する作業のことで、再構築、リビルド、再構成などと呼ぶこともあります。どんなボリュームマネージャーや RAID アレイでも、ディスクが寿命になった場合、交換した場合、一時的な停止があった場合などには必ず、この作業をしなければなりません。 ミラーリングの場合、単にディスク全体をコピーするだ...

ZFS

RAID-Z

安価なディスクで高速かつ信頼性の高いストレージを提供することが、RAID (Redundant Arrays of Inexpensive Disks) 本来の目的でした。安価なという点が重要なはずでしたが、現在こういった製品も販売されています。どうしてでしょうか。 RAID-5 (だけでなく、RAID-4、RAID-6、Even-Odd 法、Row Diagonal Parity 法など、ほかのデータ/パリティースキーマ) は、RAID の目的を完全に達成するものではありません。また、RAID-5 書き込みホールと呼ばれる致命的欠陥があるため、目的の完全達成は不可能です。ディスク故障時のデータ復旧のために、RAID ストライプのデータを更新するときは必ずパリティーも更新して、全ディスクでの XOR をゼロにしておかなければなりません。問題は、複数のディスクをアトミックにアップデートする方法がないということです。このため、ディスククラッシュや停電で RAID ストライブのデータが破損することがあります。 データブロック書き込みの直後で、かつ、書き込んだデータのパリティーブロック書き込みの前に電源が落ちた、という例を考えると、理解しやすいでしょう。ストライプ上でデータとパリティーが一致しなくなり、ストライプ全体の書き込みでたまたま以前と同じデータが上書きされないかぎり、不一致を解消する手段がありません。このため、ディスクエラーを起こしたストライプ上にあるブロックを読み込むと、RAID の修復プロセスが誤ったデータを生成します。さらに悪いことに、この現象を検知する手段がありません。正常なデータを出力しているときと変わりがないのです。 この問題について、ソフトウェアだけで完結する回避方法もありますが、その方法では速度が大きく低下するため、ソフトウェア RAID の市場価値がなくなってしまいます。現行の RAID 製品はいずれも、NVRAM を利用した電源断対策が可能なハードウェアで、RAID ロジックを処理しています。この対応は有効ですが、高価です。 既存の RAID スキーマには、ほかにも面倒なパフォーマンス問題があります。ストライプ一部の書き込みをする場合、つまり RAID ストライプ 1 つ分よりも小さなデータを更新する場合、新しいパリティーを計算するために、既存のデータとパリティーを読み込まなければなりません。これは大きなオーバーヘッドになります。ストライプ全体の書き込みでは、単純にすべての書き込みを非同期処理できますが、ストライプ一部の書き込みでは、同期読み取りをしなければ書き込みを始めることもできません。 繰り返しますが、これは高価なハードウェアを使えば解決可能な問題です。ディスク読み取りの終了を待つ間に、RAID アレイがストライプ一部の書き込みの内容を NVRAM に保存しておき、読み取りの待ち時間をユーザーに意識させないという対応が可能です。もちろん、NVRAM のバッファーがいっぱいになると、この仕組みは機能しなくなります。それで問題ない、というのがストレージベンダーの主張です。さらに費用をかけて NVRAM を増設すればよいのです。お金さえあれば問題はありません。 ストライプ一部の書き込みにはまだ問題があります。ZFS ようなトランザクション対応ファイルシステムでの問題です。ストライプ一部の書き込みにはライブデータの書き換えが必要ですが、このことが、トランザクションのセマンティクスを確保するためのルールと矛盾します (ZFS へのほかの書き込みと同様に、ストライプ全体の書き込み時に電源が落ちても、書き込み中のブロックはすべてライブでないため、問題ありません)。 厄介者の、ストライプ一部の書き込みさえなければよかったのですが。 RAID-Z 入門 RAID-Z は RAID-5 と似たデータ/パリティースキーマですが、ストライプ幅が可変である点が異なります。ブロックサイズにかかわらず、すべてのブロックで RAID-Z のストライプを構成します。つまり、RAID-Z への書き込みはすべてストライプ全体の書き込みになります。これを ZFS のトランザクションセマンティクスであるコピーオンライトと組み合わせると、RAID の書き込みホールを完全に回避できます。RAID-Z は、リードモディファイライトを行わないため、従来の RAID と比較して速度も向上しています。 あれ、それで全部 ? 可変幅ストライプ ? まったくわかりきったことだ。そんなに名案なら、皆がやってるはずだろう ? 仕掛けがあるのは、RAID-Z の再構築機能です。ストライプのサイズがそれぞれに異なるため、「全ディスクでの XOR をゼロにする」といった単純な処理ではありません。ファイルシステムのメタデータを走査して、RAID-Z のジオメトリを判断する必要があります。これは、ファイルシステムと RAID アレイが分離した製品では不可能なことで、RAID-Z のような仕組みがこれまでストレージ市場になかったことの理由でもあります。データの論理的構造と物理的構造を総合的に把握する必要があります。 あなたはこう言いたいのかもしれません。遅くないのか ? メタデータの走査にかかるコストは高くないのか ? たしかに、トレードオフは避けられません。容量に余裕がない場合は、比較的遅くなります。しかし実際は、よほど容量が逼迫していないかぎり、メタデータによる再構成のほうが高速です。ライブデータのコピー作成のみを行い、未割り当てディスクスペースのコピーに無駄な時間を使わないからです。 それよりもはるかに重要なことがあります。ZFS がメタデータを検証するということは、すべてのブロックで 256 ビットのチェックサムを確認できるということです。従来の RAID 製品では、これができません。ただ盲目的にすべてのディスクの XOR を確認するだけです。 RAID-Z の特長はどのような点でしょうか。データの自己修復ができます。ディスク全���のエラーだけでなく、サイレント破損を検出して修正することもできます。RAID-Z のブロックを読み込むたびに、ZFS がチェックサムを確認します。データディスクの内容が正しくない場合、ZFS はパリティーを読み込んで複合再構成を行い、どのディスクが不正なデータを返したのか探ります。そのうえで、破損したディスクを修復し、正しいデータをアプリケーションに返します。また、Solaris FMA で処理内容を通知し、システム管理者にサイレント破損を起こしているディスクがあることを知らせます。 最後に、RAID-Z には特別なハードウェアが必要ないということに注目してください。データを守るための NVRAM も、パフォーマンスを向上させるための書き込みバッファーも、必要ありません。ZFS と RAID-Z の併用で、RAID 本来の目的を遂行します。つまり、安価な普及品のディスクで、高速かつ信頼性が高いストレージを提供します。 耐久性の低下したハードウェア上のサイレント破損を、RAID-Z で検出し修正する実例については、Eric Lowe のブログを参照してください。 現行の RAID-Z はシングルパリティーアルゴリズムですが、RAID-Z の基本設計はどのような形態の RAID にも適応可能なものです。ダブルパリティー対応版は現在開発中です。 もう 1 つだけ、プログラマがには驚きの情報を。RAID-Z の実装は、599 行しかありません。Technorati タグ:OpenSolaris Solaris ZFS

安価なディスクで高速かつ信頼性の高いストレージを提供することが、RAID (Redundant Arrays of Inexpensive Disks) 本来の目的でした。安価なという点が重要なはずでしたが、現在こういった製品も販売されています。どうしてでしょうか。 RAID-5 (だけでなく、RAID-4、RAID-6、Even-Odd 法、Row Diagonal...

ZFS

Integridade de dados ponta a ponta do ZFS

A função de qualquer sistema de arquivos se resume a isto: quando solicitado a ler um bloco, ele deve retornar os mesmos dados que foram gravados anteriormente nesse bloco. Se não puder fazer isso, seja porque o disco está off-line ou os dados estão danificados ou adulterados, ele deverá detectar isso e retornar um erro. Incrivelmente, a maioria dos sistemas de arquivos falha neste teste. Eles dependem do hardware subjacente para detectar e informar erros. Se um disco simplesmente retornar dados inválidos, o sistema de arquivos médio nem mesmo detectará isso. Mesmo que possamos assumir que todos os dados estejam perfeitos, ainda assim os dados estariam vulneráveis a danos em trânsito: erros da controladora, erros de paridade DMA (acesso direto à memória) e assim por diante. Tudo o que você realmente sabe é que os dados estavam intactos quando saíram do disco. Se você pensar em seus dados como um pacote, isso seria como se a UPS dissesse, "Garantimos que o seu pacote não estava danificado quando nós o pegamos." Não exatamente a garantia que você deseja. Danos em vôo não são uma mera preocupação acadêmica: mesmo algo tão comum quanto uma fonte de alimentação com defeito pode provocar corrupção silenciosa de dados. Matrizes de armazenamento caras não conseguem resolver o problema. O caminho de E/S continua muito vulnerável, e ainda mais longo: após sair do disco, os dados precisam sobreviver a quaisquer erros de hardware e de firmware que a matriz ofereça. E se estiver em uma SAN, você estará usando uma rede projetada por autores de firmware de disco. Que Deus te ajude! O que fazer? Uma opção é armazenar uma soma de verificação em cada bloco de disco. A maioria das modernas unidades de disco podem ser formatadas com setores que são ligeiramente maiores do que os usuais 512 bytes, normalmente 520 ou 528. Esses bytes extras podem ser usados para armazenar a soma de verificação. Mas fazer bom uso dessa soma de verificação é mais difícil do que parece: a eficácia de uma soma de verificação depende tremendamente do local onde ela estiver armazenada e do momento em que for avaliada. Em muitas matrizes de armazenamento (consulte o documento Dell|EMC PowerVault para ver um exemplo típico com uma excelente descrição dos problemas), os dados são comparados com sua soma de verificação dentro da matriz. Infelizmente, isso não ajuda muito. Não detecta erros comuns de firmware, como as gravações fantasmas (a gravação anterior não foi feita no disco) porque os dados e a soma de verificação são armazenados como uma unidade, de modo que fiquem consistentes entre si, mesmo quando o disco retornar dados obsoletos. E o restante do caminho de E/S, da matriz até o host, permanece desprotegido. Resumindo, esse tipo de soma de verificação de bloco oferece uma boa maneira de garantir que um produto de matriz não é menos confiável do que os discos que contém, mas isso é tudo. A abordagem da soma de verificação anexada ao bloco do NetApp parece semelhante, mas é muito mais robusta. Igual a muitas matrizes, o NetApp formata suas unidades com setores de 520 bytes. Em seguida, ele as agrupa em blocos de 8 setores: 4K de dados (o tamanho de bloco do sistema de arquivos WAFL) e 64 bytes da soma de verificação. Quando o WAFL lê um bloco, ele compara a soma de verificação com os dados da mesma maneira como uma matriz o faria, mas há uma importante diferença: ele faz essa comparação após os dados terem percorrido todo o caminho de E/S, de modo a validar que o bloco fez a jornada do disco até a memória sem danos em trânsito. Esse é um aperfeiçoamento importante, mas ainda não é suficiente. Uma soma de verificação em nível de bloco somente prova que o bloco é consistente consigo mesmo; ela não prova que ele é o bloco correto. Repetindo nossa analogia da UPS, "Garantimos que o pacote que você recebeu não tem danos. Não garantimos que é o seu pacote." O problema fundamental com todos esses esquemas é que eles não fornecem isolamento contra falhas entre os dados e a soma de verificação que os protege. Autenticação de dados do ZFS A integridade de dados ponta a ponta exige que cada bloco de dados seja comparado com uma soma de verificação independente, após os dados terem chegado à memória do host. Não é suficiente saber que cada bloco é meramente consistente consigo mesmo, ou que estava correto em um ponto anterior do caminho de E/S. Nossa meta é detectar todas as formas possíveis de danos, inclusive erros humanos, como trocas em um disco do sistema de arquivos ou erro de digitação dos argumentos para dd(1). (Você já deve ter digitado "of=" quando queria dizer "if=".) Um pool de armazenamento ZFS é realmente apenas uma árvore de blocos. O ZFS fornece isolamento contra falhas entre os dados e a soma de verificação armazenando a soma de verificação de cada bloco em seu ponteiro de bloco pai, e não no próprio bloco. Cada bloco da árvore contém as somas de verificação de todos os seus filhos, de modo que todo o pool é auto-validante. [O bloco inicial (a raiz da árvore) é um caso especial porque não tem pai; mais sobre como lidar com isso em outra postagem.] Quando os dados e a soma de verificação não conferem entre si, o ZFS sabe que a soma de verificação é confiável porque a própria soma de verificação faz parte de algum outro bloco que está um nível acima na árvore e que esse bloco já foi validado. O ZFS usa somas de verificação ponta a ponta para detectar e corrigir corrupção silenciosa de dados. Se um disco retornar dados inválidos de maneira transitória, o ZFS detectará e tentará ler de novo. Se o disco fizer parte de um espelho ou de um grupo RAID-Z, o ZFS detectará e corrigirá o erro: ele usará a soma de verificação para determinar qual cópia está correta, fornecer dados válidos para o aplicativo e reparar a cópia danificada. Como sempre, observe que a integridade de dados ponta a ponta do ZFS não exige qualquer hardware especial. Você não precisa de discos ou matrizes caras, não precisa reformatar as unidades com setores de 520 bytes e não precisa modificar aplicativos para se beneficiar dela. É totalmente automática e funciona com discos baratos. Mas espere, pois tem mais! Os blocos de um pool de armazenamento ZFS formam uma árvore Merkle na qual cada bloco valida todos os seus filhos. As árvores Merkle demonstraram que proporcionam uma autenticação criptograficamente forte para quaisquer componentes da árvore e para a árvore como um todo. O ZFS emprega somas de verificação de 256 bits para cada bloco e oferece funções de soma de verificação que variam entre a simples e rápida fletcher2 (padrão) até a mais lenta, porém segura, SHA-256. Quando se usa um hash criptográfico como o SHA-256, a soma de verificação do bloco inicial fornece uma assinatura digital constantemente atualizada para todo o pool de armazenamento. Que será muito conveniente se você solicitar à UPS para fazer o traslado. Tags Technorati: OpenSolaris Solaris ZFS

A função de qualquer sistema de arquivos se resume a isto: quando solicitado a ler um bloco, ele deve retornar os mesmos dados que foram gravados anteriormente nesse bloco. Se não puder fazer isso,...

ZFS

Integridad de datos de extremo a extremo ZFS

El trabajo de cualquier sistema de archivos se reduce a esto: cuando se le pide que lea un bloque, debe devolver los mismos datos que se hayan escrito en el bloque. Si no puede hacerlo, ya sea porque el disco está fuera de línea o porque los datos estén dañados o alterados, debería detectar el error y comunicarlo. Por increíble que parezca, la mayoría de los sistemas de archivos no superan esta prueba, porque dependen del hardware subyacente para detectar e informar sobre los errores. La mayor parte de los sistemas de archivos ni siquiera podrían detectar si un disco devuelve datos incorrectos. Incluso en el caso de que todos los discos funcionen perfectamente, los datos siguen siendo vulnerables durante el transporte: fallos del controlador, errores de paridad DMA, entre otros varios peligros. Todo lo que se puede saber es que los datos estaban intactos cuando salieron del disco. Considerando los datos como si fuera paquete, es como si UPS dijera: "Garantizamos que su paquete no sufrió ningún daño en la recogida". Vale, pero no es el tipo de garantía que se espera encontrar. Un daño en vuelo no es un mero problema académico: incluso algo tan prosaico como una fuente de alimentación en mal estado puede causar el deterioro silencioso de los datos. Las matrices de almacenamiento caras y arbitrarias no pueden resolver el problema. El camino de E/S sigue siendo tan vulnerable como antes, pero se ha hecho más largo: después de dejar el disco, los datos no han sobrevivido a la gama de errores de hardware y firmware que la matriz pone a su disposición. Y si se encuentra en una SAN, está utilizando, además, una red diseñada por escritores de firmware. Dios le ampare, hermano. ¿Qué hacer? Una opción es guardar una suma de comprobación con cada bloque de disco. La mayoría de las unidades de disco modernas se pueden formatear con sectores que son ligeramente más grandes que los habituales de 512 bytes -- por lo general, de 520 o 528. Estos bytes extras se pueden utilizar para guardar la suma de comprobación del bloque. Pero hacer un buen uso de la suma de comprobación es más duro de lo que parece: la eficacia de una suma de comprobación depende extraordinariamente del lugar en el que se guarda y del momento en que se calcula. En muchas matrices de almacenamiento (consulte el documento Dell|EMC PowerVault para ver un ejemplo típico con una descripción excelente de los problemas), los datos se comparan con su propia suma de comprobación dentro de la matriz. Por desgracia, esto no ayuda mucho. No detecta errores comunes de firmware, como las escrituras fantasma (la escritura anterior no llega jamás a grabarse en el disco) ya que los datos y la suma de comprobación se guardan como una unidad -- de modo que son coherentes entre sí incluso aunque el disco devuelva datos erróneos. Y el resto del camino de E/S de la matriz al ordenador anfitrión sigue estando desprotegido. En resumen, este tipo de suma de comprobación de bloque ofrece un buen método de garantizar que el producto de la matriz no es menos fiable que los discos que contiene, pero no hay más. El enfoque de la suma de comprobacion añadida a un bloque de NetApp se parece algo pero lo cierto es que es mucho más fuerte. Al igual que muchas matarices, NetApp formatea sus unidades con sectores de 520 bytes. Y luego las agrupa en bloques de ocho sectores: 4 K de datos (el tamaño del bloque del sistema de archivos WAFL) y 64 bytes de la suma de comprobación. Cuando WAFL lee un bloque, compara la suma de comprobación con los datos, exactamente igual a como lo haría una matriz, pero con una diferencia clave: realiza la comparación después de que los datos hayan recorrido el camino de E/S, por lo que garantiza que el bloque ha pasado del disco a la memoria sin sufrir daños en el trayecto. Esto representa una gran mejora, pero sigue sin ser suficiente. Una suma de comprobacion a nivel del bloque sólo prueba que el bloque es coherente consigo mismo, pero no garantiza que sea el bloque correcto. Retomando la analogía anterior, es como si UPS dijera: "Garantizamos que el paquete que ha recibido no ha sufrido daños. No garantizamos que se trate de su paquete". El problema fundamental con todos estos esquemas es que no ofrecen aislamiento contra fallos entre los datos y la suma de comprobacion que los protege. Autentificación de datos ZFS La integridad de los datos de extremo a extremo requiere que cada bloque de datos se compare con una suma de comprobacion independiente después de que los datos hayan llegado a la memoria del ordenador anfitrión. No basta con saber que cada bloque es coherente consigo mismo ni que fuera correcto en cualquier punto anterior del camino de E/S. Lo que pretendemos es detectar cada posible forma de daño, incluidos los fallos humanos, como el intercambio de archivos en un disco del sistema de archivos o un error al escribir un argumento en dd(1). (¿Nunca ha escrito "of=" cuando quería poner "if="?) Un lugar de almacenamiento ZFS es realmente un árbol de bloques. ZFS proporciona aislamiento contra fallos entre los datos y la suma de comprobación guardando la suma de comprobación de cada bloque en su bloque padre -- no en el propio bloque. Cada bloque del árbol contiene las sumas de comprobación de todos sus hijos, por lo que todo el lugar de almacenamiento está comprobado automáticamente. [El bloque principal (la raíz del árbol) es un caso especial porque no tiene padre; hablaremos más sobre esto en otra entrega]. Cuando los datos y la suma de comprobación están en desacuerdo, ZFS sabe que la suma de comprobación es correcta porque forma parte de otro bloque que se encuentra en un nivel superior del árbol y que, a su vez, ya ha sido validado. ZFS utiliza sus propias sumas de comprobación de extremo a extremo para detectar y corregir la corrupción silenciosa de los datos. Si un disco devuelve datos dañados, ZFS los detectará y repetirá su lectura. Si el disco forma parte de un espejo o de un grupo RAID-Z, ZFS detectará ambos y corregirá el error: utilizará la suma de comprobación para determinar la copia correcta, ofrecer datos correctos a la aplicación y reparar la copia dañada. Como siempre, recuerde que la integridad de los datos de extremo a extremo ZFS no requiere ningún tipo especial de hardware. No tendrá que gastar en discos ni matrices caras, no tendrá que reformatear unidades con sectores de 520 bytes ni tendrá que modificar aplicaciones para poder disfrutar de sus ventajas. Es totalmente automático y funciona con discos baratos. ¡Espere un momento, que todavía hay más! Los bloques de un lugar de almacenamiento ZFS forman un árbol Merkle en el que cada bloque valida a todos sus hijos. Los árboles Merkl han demostrado que proporcionan una autentificación criptográficamente fuerte para cualquier componente del árbol y para todo el árbol en su conjunto. ZFS utiliza sumas de comprobación de 256 bits para cada bloque y ofrece funciones de sumas de comprobación que comprenden desde la sencilla y rápida fletcher2 (valor predeterminado) a la más lenta pero segura SHA-256. Cuando se utiliza una hash criptográfica, como SHA-256, la suma de comprobacion del bloque principal proporciona una firma digital actualizada para todo el lugar de almacenamiento. Que viene muy bien si pide a UPS que haga el traslado. Technorati Tags: OpenSolaris Solaris ZFS

El trabajo de cualquier sistema de archivos se reduce a esto: cuando se le pide que lea un bloque, debe devolver los mismos datos que se hayan escrito en el bloque. Si no puede hacerlo, ya sea porque...

ZFS

ZFS 端到端数据完整性

文件系统的工作归结为:当被请求读取块时,它应该返回上次写到此块的数据。如果它做不到这一点(由于磁盘脱机或数据已经被损坏或篡改),那么它应该能检测并返回错误。难以置信的是,大多数文件系统未能做到这一点。它们依赖底层硬件来检测和报告错误。如果磁盘返回坏数据,一般文件系统甚至无法检测到这一点。即使我们可以假设所有磁盘都是完美的,数据也很容易在传输中受到损坏:控制器 bug、DMA 奇偶校验错误等等。您知道的只是数据离开磁盘片时是完好无缺的。如果将数据当作一个包,则这就像 UPS 所说的那样,“我们保证您的包裹在我们包装时没有损坏”。这根本不是您寻求的保证。过程中的损坏不仅仅是一个学术问题:甚至像糟糕的供电这样的小事都可能导致无提示数据损坏。任何昂贵的存储阵列都无法解决这个问题。I/O 路径仍然易受攻击,但它变得更长:不管阵列存在什么样的硬件和固件 bug,在离开磁盘片之后,数据必须要能够存活。如果您位于 SAN 上,您将使用磁盘固件读盘器设计的网络。上帝保佑您。 怎么办?一种选择是在每个磁盘块中存储校验和。大多数现代磁盘驱动器可以使用比通常的 512 字节略大的扇区来格式化,通常是 520 或 528。这些额外的字节可用于存放块校验块。但有效利用此校验和要比想象中困难:校验和的有效性极大地依赖于它的存储位置和它的评估时间。在许多存储阵列中(请参阅 Dell|EMC PowerVault paper 中的一个典型示例,当中有这些问题的完整描述),数据与其阵列内的校验和进行比较。不幸的是,这没有多少用处。它不会检测常见的固件 bug,比如幻象写(上一次写操作,但实际上从未对磁盘执行过),因为数据和校验和存储为单元,所以它们是自我一致的 (self-consistent),即使当磁盘返回坏数据时。从阵列到主机的其他 I/O 路径仍不受保护。简而言之,这种块校验和提供了一种好的方法来确保阵列产品不会比它所包含的磁盘可靠性低,但也仅此而已。NetApp 的块附加校验和方法似乎与此类似,但事实上要强大得多。与许多阵列一样,NetApp 使用 520 字节扇区来格式化其驱动器。然后,它将其分组为 8 扇区块:4K 的数据(WAFL 文件系统块大小)和 64 字节的校验和。当 WAFL 读取块时,它将校验和与数据进行比较,就像阵列一样,但有一个关键的不同之处:它在数据已经通过 I/O 路径进行了比较之后,才进行比较,所以它会验证块在从磁盘片到内存的过程中没有受到损坏。这是一个主要的改进,但仍不足够。块级校验和只能证明块是自我一致的;它不能证明这是一个正确的块。再次请出我们的 UPS,“我们保证您收到的包裹没有损坏。但我们不保证它是您的包裹”。所有这些方案的基本问题在于,它们不在数据与保护它的校验和之间提供故障隔离。ZFS 数据认证 端到端数据完整性需要在数据已经到达主机的内存之后,按照独立的校验和验证数据。知道每个块仅仅与自身一致,或者它在 I/O 路径一些先前的点上是正确的还远远不够。我们的目标是检测所有可能发生的损坏,包括人工错误,比如替换文件系统磁盘,或者输入了错误的 dd(1) 参数。(您有没有过这样的经历:本来想键入 "if=" 结果却键入了 "of="?)ZFS 存储池实际上只是一个块树。ZFS 将每个块的校验和存储在其父块指针而非块本身中,以此提供数据与校验和之间的故障隔离。树中的每个块都包含所有子块的校验和,所以整个池是自我验证的。[超级块(树根)是特殊情况,因为它没有父块;有关如何处理这种情况的详细信息,我们将在另一篇文章中介绍。] 当数据和校验和不一致时,ZFS 知道校验和可以信任,因为校验和本身属于树中更高一层的其他块,而该块已通过验证。ZFS 使用其端到端的校验和检测并更正无提示数据损坏。如果磁盘瞬时返回坏数据,ZFS 将检测到它并重试读取。如果磁盘属于镜像或 RAID-Z 组,则 ZFS 将同时检测并更正错误:它将使用校验和确定哪个副本是正确的,为应用程序提供好数据并修复损坏的副本。与以往一样,注意 ZFS 端到端数据完整性不需要任何特殊硬件。您不需要高价的磁盘或阵列,您不需要使用 520 字节的扇区重新格式化驱动器,您不需要修改应用程序来从中获益。它是完全自动的,而且它使用的是廉价磁盘。等一等,这还没完! ZFC 存储池的块形成一棵 Merkle 树,其中每个块验证其所有子块。实践证明,Merkle 树可以为树的任何组件以及整个树提供了加密强认证。ZFS 为每个块使用了 256 位校验和,并提供了从简单快捷的 fletcher2(默认值)到慢但安全的 SHA-256 校验和功能。使用类似 SHA-256 的加密散列时,超级块校验和为整个存储池提供了持续更新的数字签名。如果您叫 UPS 发送包裹,这肯定能派上用场。Technorati Tags: OpenSolaris Solaris ZFS

文件系统的工作归结为:当被请求读取块时,它应该返回上次写到此块的数据。如果它做不到这一点(由于磁盘脱机或数据已经被损坏或篡改),那么它应该能检测并返回错误。 难以置信的是,大多数文件系统未能做到这一点。它们依赖底层硬件来检测和报告错误。如果磁盘返回坏数据,一般文件系统甚至无法检测到这一点。 即使我们可以假设所有磁盘都是完美的,数据也很容易在传输中受到损坏:控制器 bug、DMA 奇偶校...

ZFS

豪快なレイヤー分け違反

Andrew Morton が ZFS を「豪快なレイヤー違反」と呼んだのは有名ですが、その理由は、ファイルシステムの機能、ボリューム管理、RAID コントローラを統合していることにあります。 違反という言葉の意味をどう取るかで、解釈が異なると思います。 ZFS の設計に際して、ストレージスタックの標準的なレイヤー分けが、驚くほど大量の無駄手間と冗長な処理を含んでいることを発見しました。 問題点にちょっとしたリファクタリングを加えれば、つまり、レイヤーを分ける境界を移動させてやれば、全体をもっと単純化できるのではないかと気づきました。数学 (私のバックグラウンド分野) を例にするとわかりやすいでしょう。n=1 から 無限大まで、1/n(n+1) について数列の和を計算しなければならないと仮定します。項ごとにして開くと、次のような計算になります。        1/(1\*2) + 1/(2\*3) + 1/(3\*4) + 1/(4\*5) + ...つまり、        1/2 + 1/6 + 1/12 + 1/20 + ...無限に足し算を続けるのはどうでしょうか。非常に難しいことのようですが、問題を正しく観察していないというだけのことです。 賢明な人は、各項を先ほどとは違うやり方で記述できることに気付いたかもしれません。        1/n(n+1) = 1/n - 1/(n+1)たとえば、        1/(1\*2) = 1/1 - 1/2        1/(2\*3) = 1/2 - 1/3        1/(3\*4) = 1/3 - 1/4そこで、次のように記述することができます。        (1/1 - 1/2) + (1/2 - 1/3) + (1/3 - 1/4) + (1/4 - 1/5) + ...規則性に注目してください。各項の後半で引き算したのと同じ数を、その次の項で足し算する繰り返しになっています。 こういう計算で意味があるのは、学会の中だけです。 では、区切り方を変えてみましょう。つまり元の問題に対して、結合性を元に、豪快なレイヤー分け違反をします。そうして、隣接項の両端同士の計算にリファクタリングします。次のようになります。        1/1 + (-1/2 + 1/2) + (-1/3 + 1/3) + (-1/4 + 1/4) + ...つまり、        1/1 + 0 + 0 + 0 + ...別の書き方をすると、        1.賢いやり方ではないでしょうか。このように、 連続した項の配置を変えて互いに消去することを、数学の用語で Telescoping (たたみ込み) と呼びます。折りたたみ式の携帯望遠鏡 (Telescope) に例えた言い方です。 簡単に言うと、ZFS がやっているのも同じことで、ストレージスタックをたたみ込んでいるのです。 それにより、ファイルシステム、ボリュームマネージャー、シングルパリティーとダブルパリティーに対応した RAID、圧縮、スナップショット、クローン作成、そのほかたくさんの有用な機能が、たった 80,000 行のコードで実現できたのです。ストレージシステムはここまで単純ではありませんが、高いレベルで、同じ考えを実際に利用しているのです。 どのようなストレージスタックも、ある命名スキーマから別の命名スキーマへの、変換の連続だと考えることができます。最終的には、ファイルネームをディスク LBA (Logical Block Address) に変換します。 典型的な例として、次のようになるでしょう。 ファイルシステム (上位):ファイルネームをオブジェクトに (inode) ファイルシステム (下位):オブジェクトをボリューム LBA に        ボリュームマネージャー:ボリューム LBA を アレイ LBA に        RAID コントローラ:アレイ LBA をディスク LBA にこれが、私たちがリファクタリングしようとしているスタックです。まず、従来のファイルシステムのレイヤーはモノリシックすぎるということに注目してください。 ファイルネームをオブジェクトに変換する部分 (前半) とオブジェクトをボリューム LBA に変換する部分 (後半) で 2 つに分けたほうがよいでしょう。この分け方だと、オブジェクトと iSCSI ターゲットなど、ファイルネームを持たず種類の異なるストレージをサポートする場合に、後半のコードを再利用できます。 つまり、各ストレージクラスからオブジェクトレイヤーに直接通信することができます。 この手法は、/dev/lofi などを経由するよりも効率的です。/dev/lofi は、POSIX ファイルをデバイスのように見せかける機能を提供しています。 さらに大切なことは、分け方を変えることで、コードを追加することなく新しくて強力なプログラミングモデルを実現できるということです。つまり、オブジェクトストレージのことです。次に、ボリューム LBA は完全に役立たずだということに注目してください。中間レイヤーを設けることで柔軟性が高まるケースは多くありますが、この場合はそうではありません。実際、英語をドイツ語に直接変換しても問題がないのに、英語をフランス語に変換してから、あらためてドイツ語に変換しているのです。 中間のフランス語は本質的に無価値です。 この処理は、アプリケーションからも RAID アレイからも見えず、管理に必要な機能を提供していません。 ただのオーバーヘッドです。そのため、ZFS ではレイヤー全体をたたみ込んで消去しました。 ZFS には、3 つの明確なレイヤーだけがあります。従来の POSIX ファイルシステムのセマンティクスを提供する ZPL (ZFS POSIX Layer)、汎用のトランザクションオブジェクトストアを提供する DMU (Data Management Unit)、仮想ブロック割り当てとデータ変換 (レプリケーション、圧縮、そして近い将来には暗号化も) を提供する SPA (Storage Pool Allocator) です。 ZFS の変換スタック全体は、次のようになります。        ZPL:ファイルネームをオブジェクトに        DMU:オブジェクトを DVA (Data Virtual Address) に        SPA:DVA を ディスク LBA にDMU が物理ストレージの共通プールに、ファイルアクセスとブロックアクセスの両方を提供します。 ブロックアクセスは DMU オブジェクトへの直接的なマッピングですが、ファイルアクセスは ZPL 経由で行います。 DMU のトランザクション能力をもっとおもしろい方法で利用した、新しいデータアクセスメソッドも開発中で、後日紹介する予定です。ZFS のアーキテクチャーにより、変換レイヤーが丸ごと消去され、それとともに、メタデータクラス (ボリューム LBA) も丸ごとなくなります。 ハードウェア RAID コントローラの必要性もなくなります。さらに、有用な新インタフェースであるオブジェクトストレージを提供します。モノリシックなファイルシステムに埋もれて、以前はアクセスできなかったインタフェースです。違反しているような感じはしませんが、 どう思いますか。

Andrew Morton が ZFS を「豪快なレイヤー違反」と呼んだのは有名ですが、その理由は、ファイルシステムの機能、ボリューム管理、RAID コントローラを統合していることにあります。 違反という言葉の意味をどう取るかで、解釈が異なると思います。...

ZFS

Espelhos esfumaçados

A restauração, também conhecida como ressincronização, reconstrução ou remontagem, é o processo de reparar um dispositivo danificado usando o conteúdo de dispositivos em bom estado. É isso que cada gerenciador de volume ou matriz RAID deve fazer quando um de seus discos pára de funcionar, é substituído ou sofre uma interrupção temporária de energia. Para um espelho, a restauração pode ser tão simples quanto copiar o disco todo. Para o RAID-5, isso é um pouco mais complicado: em vez de copiar um disco para outro, todos os outros discos da faixa RAID-5 devem ser submetidos juntos ao processo XOR. Mas a idéia básica é a mesma. Em um sistema de armazenamento tradicional, a restauração ocorre no gerenciador de volume ou no hardware RAID. De qualquer maneira, ocorre bem abaixo do sistema de arquivos. Mas este é o ZFS, assim, certamente tínhamos que ser diferentes. Em uma postagem anterior, mencionei que a reconstrução do RAID-Z requer uma abordagem diferente, porque ele precisa dos metadados do sistema de arquivos para determinar a geometria RAID-Z. Na verdade, o ZFS faz uma 'cp -r' (cópia e restauração) da árvore de blocos do pool de armazenamento de um disco para outro. Pode parecer menos eficiente do que uma cópia direta de todo o disco, e percorrer todo um pool ativo com segurança é, sem a menor dúvida, complicado (falaremos mais sobre esse assunto numa futura postagem). Mas a restauração orientada por metadados oferece tantas vantagens que preferimos usá-la até mesmo para espelhamento simples. A razão mais importante é a integridade de dados. Com uma cópia simples de disco, não há como saber se o disco de origem está retornando dados válidos. A integridade dos dados ponta a ponta requer que cada bloco de dados seja comparado com uma soma de verificação independente; não é suficiente saber que cada bloco é meramente consistente consigo mesmo, porque isso não detecta erros comuns de hardware e de firmware, como leituras equivocadas e gravações fantasmas. Ao percorrer os metadados, o ZFS pode usar suas somas de verificação ponta a ponta para detectar e corrigir corrupção silenciosa de dados, exatamente como ele faz durante as leituras normais. Se um disco retornar dados inválidos de maneira transitória, o ZFS detectará e tentará ler de novo. Se for um espelhamento de três vias e um dos dois discos supostamente bons estiver danificado, o ZFS usará a soma de verificação para determinar qual está correto, copiará os dados para o novo disco e reparará o disco danificado. Uma cópia simples de todo o disco ignoraria toda essa proteção de dados. Apenas isso seria suficiente para tornar a restauração orientada por metadados aconselhável, mesmo à custa de uma significativa redução de desempenho. Felizmente, na maioria dos casos, não é o que ocorre. Na realidade, a restauração orientada por metadados oferece diversas vantagens: Somente blocos ativos. O ZFS não perde tempo e largura de banda de E/S copiando blocos de disco livres porque eles não fazem parte da árvore de blocos do pool de armazenamento. Se o seu pool estiver com apenas de 10 a 20% de sua capacidade ocupados, isso será um grande ganho. Remoção de transações. Se um disco sofrer uma queda transitória de energia, não será necessário restaurar todo o disco, mas somente as partes que foram alteradas. Em uma futura postagem, vou descrever isso com mais detalhes, mas resumindo: o ZFS usa a hora de origem de cada bloco para determinar se há algo mais recente na árvore que precise de restauração. Isso permite pular enormes ramificações da árvore e descobrir rapidamente os dados que realmente foram alterados desde o início da interrupção. Na prática, isso significa que se um disco sofrer uma interrupção de cinco segundos, demorará cerca de cinco segundos para restaurá-lo. E você não terá custo extra por isso, nem em termos financeiros nem de desempenho, como acontece quando o Veritas modifica objetos. A remoção de transações é um recurso intrínseco da arquitetura do ZFS. Restauração descendente. Um pool de armazenamento é uma árvore de blocos. Quanto mais alto você estiver na árvore, mais desastrosa será a perda de um bloco, porque você perderá acesso a tudo abaixo dele. Passar pelos metadados permite que o ZFS faça uma restauração descendente. Ou seja, o primeiro item que o ZFS restaura é o bloco inicial e as identificações do disco. A seguir, ele restaura os metadados de todo o pool de armazenamento, depois, cada metadado do sistema de arquivos e assim por diante até chegar à base da árvore. Durante todo o processo, o ZFS obedece a esta regra: nenhum bloco será restaurado até que todos os seus antecessores tenham sido restaurados. É difícil enfatizar o quanto isso é importante. Em uma cópia de todo o disco, mesmo com 99% prontos, há uma grande possibilidade de um dos primeiros 100 blocos da árvore ainda não ter sido copiado. Isso significa que, de uma perspectiva de MTTR (tempo médio para reparos), na realidade, você não fez qualquer progresso: neste ponto, uma segunda falha de disco ainda seria catastrófica. Com a restauração descendente, cada bloco individual copiado aumenta a quantidade de dados detectáveis. Se ocorrer uma segunda falha no disco, tudo o que tiver sido restaurado até este ponto estará disponível. Restauração baseada em prioridade. O ZFS ainda não faz isso, mas está a caminho. A restauração do ZFS segue a estrutura lógica dos dados, logo, seria muito fácil marcar sistemas de arquivos ou arquivos individuais com uma prioridade específica de restauração. Por exemplo, em um servidor de arquivos, convém restaurar primeiro os calendários (eles são importantes, ainda que muito pequenos), a seguir, os diretórios /var/mail, depois, o diretório inicial e assim por diante. O que espero transmitir em cada uma destas postagens não é somente a mecânica de como um recurso específico foi implementado, mas ilustrar como todas as partes do ZFS formam um todo integrado. Por exemplo, não fica imediatamente óbvio que a semântica transacional tenha algo a ver com a restauração, ainda que a remoção de transações torne a recuperação de interrupções transitórias literalmente muito mais rápida. Mais a respeito de como isso funciona na próxima postagem.

A restauração, também conhecida como ressincronização, reconstrução ou remontagem, é o processo de reparar um dispositivo danificado usando o conteúdo de dispositivos em bom estado. É isso que cada...

ZFS

領域マップ

どんなファイルシステムで 2 つの基本的なことを記録します。どこにデータがあるかと、未使用領域がどこにあるかです。論理上、未使用領域の記録は、厳密には必須ではありません。すべてのブロックは割り当て済みと未割り当てのいずれかなので、まず全体が未使用領域である状態を想定し、そこから割り当て済みの領域を引き算してやれば、未使用の領域を知ることができます。割り当て済みの領域は、ファイルシステムをルートから走査することでわかります。 ルートからの走査でヒットしないブロックは、原理的に、すべて未割り当てのブロックです。このような方法による未使用領域の割り当ては、ファイルシステムのサイズがよほど小さくないかぎり、時間がかかりすぎて実用に耐えません。 ブロックの割り当てと開放を短時間で行うために、ファイルシステムは未使用領域を記録するトラックを効率的に管理しなければなりません。 今回は、もっともありふれた方法と、その方法で良好なスケーラビリティーを得られない理由、ZFS で工夫した新しいアプローチを紹介します。 ビットマップ未使用領域を知るためのもっともありふれた方法は、ビットマップを使うものです。 ビットマップとは、N 番目のブロックが割り当て済みか未割り当てかをN 番目のビットで示す、単純なビット列です。 ビットマップのオーバーヘッドはかなり小さく、1 ブロックにつき 1 ビットです。 ブロックサイズが 4K なら、1/(4096\*8) = 0.003% です (8 が出てくるのは 8 ビットで 1 バイトなので)。1G バイトのファイルシステムであれば、ビットマップは 32K バイトです。メモリ上に置いても差し支えなく、未使用領域を探すためのスキャンもすばやく行えます。 1T バイトのファイルシステムでは、ビットマップは 32M バイトです。まだメモリに置けますが、サイズもスキャンにかかる時間も無視できなくなります。 1P バイトのファイルシステムでは、ビットマップは 32G バイトです。ほとんどのマシンではメモリ上に置くこともできません。 スキャンするにはディスクからビットマップを読まねばならず、よりいっそう速度が低下します。明らかに、スケーラビリティーがありません。すぐに思いつく対応策は、ビットマップを小さなチャンクに分割して、各チャンクに設定されたビット数を保存しておくことです。 たとえば、ブロックサイズ 4K で容量 1P バイトのファイルシステムなら、未使用領域を 32K バイトずつで 1,000,000 のチャンクに分割します。 概要情報 (各ビットマップでどれだけの領域が未使用かを示す整数 1,000,000 個) ならメモリに置けるため、概要情報をスキャンして未使用領域のあるビットマップを探すのも、見つかったビットマップをスキャンして未使用ブロックを探すのも、すばやくできます。しかし、基本的な問題がまだ残っています。ビットマップは、新たにブロックを割り当てたときだけでなく、古いブロックを開放したあとにも更新しなければなりません。 ファイルシステムは割り当ての局所性 (どのブロックに新しいデータを保存するか) をコントロールしますが、解放する領域の局所性はコントロールできません。 「rm -rf」といった簡単な操作で、プラッタのどこでブロックが解放されます。 1P バイトのファイルシステムでの例では、最悪の場合で、4G バイト (4K のブロックを 1,000 ,000) 解放すると、1,000,000 あるビットマップすべてを読み込んで、更新し、書き戻さなければなりません。 4G バイトの解放にディスク I/O が 2,000,000 というのは、最悪のケースでの振舞いにしても、合理的な数字ではありません。ブロックの解放はランダムであることが多く、ランダムアクセス時にはビットマップをメモリ上に置けないため、ほかのどの点にも増してこのことが、スケーラビリティーのボトルネックになっています。B ツリーエクステントの B ツリーを用いて未使用領域を把握する方法も一般的です。 エクステントとは、2 つの整数、つまりオフセットと長さで表される連続した未使用領域のことです。 B ツリーでは、連続した領域の割り当てを効率よく行うために、エクステントをオフセット順にソートしています。 残念なことに、ランダムな解放を行う場合、エクステントの B ツリーにはビットマップと同様のボトルネックがあります。 どうすればよいのでしょうか。遅延解放ランダムな解放によるボトルネックを緩和するために、最近解放したブロックの一覧をべつに保持して、ビットマップや B ツリーの更新を遅延させるという方法があります。 この遅延解放リストが一定のサイズ、つまりメモリ上での最大サイズになると、ソートされた状態でビットマップや B ツリーに対して解放されるため、局所性は改善します。 理想的ではないにせよ、有用な方法です。では、私たちがこれを上回る工夫をするとしたら、どのような工夫でしょうか。領域マップ: ログ構造の解放リストログ構造化ファイルシステムが、かなり以前に次の質問を提示していたことを思い出してください。トランザクションログを定期的にファイルシステムに書き込むのではなく、ファイルシステムをトランザクションログにしてはどうでしょうか。そう、遅延解放リストにも同じことが言えます。ビットマップや B ツリーに書き込むのではなく、遅延解放リストで解放領域を表現してはどうでしょうか。ZFS がしているのは、まさにこれです。 ZFS は各仮想デバイスの領域をメタスラブと呼ばれる数百の区画に分けます。 メタスラブはそれぞれに、そのメタスラブが担当���る未使用領域を把握するための領域マップを持っています。 領域マップとは、割り当てと解放を記録した単純な時系列のログです。 どのエクステントを解放する場合にも、領域マップオブジェクトにエクステント (整数 2 つの組) を付加するだけで解放を把握でき、しかもエクステントの付加は完全な局所性を保って行われます。領域マップを用いると、このため、シーケンシャル解放と同じ効率でランダム解放を処理できます。 割り当ても同様に、領域マップオブジェクトに付加されたエクステント (エクステントのビットはもちろん、解放ではなく割り当てを示す) としてディスクに記録されます。ZFS が特定のメタスラブからブロックの割り当てを行う場合、まずメタスラブの領域マップをディスクから読み込み、メモリ内で未使用領域情報を保持している AVL ツリーでオフセット順に割り当てと解放を反映します。 これにより、メモリ内の未使用領域ツリーを小さくでき、連続した領域を効果的に割り当てられます。 メモリ内のデータを更新した際に、領域マップのサイズを小さくする処理も行います。これは、割り当てと解放を何度も繰り返して、履歴が冗長になっている場合、ZFS はディスク上の領域マップをより小さなメモリ内のマップで置き換えます。領域マップの特長をいくつか示します。初期化が必要ありません。エントリがない領域マップは、一度も割り当てや解放が行われていないことを示します。つまり、すべての領域が未使用と解釈されます。スケーラビリティーに優れます。領域マップは追記型なので、どんなに大きな領域を管理する場合であっても、メモリ内には領域マップの最後のブロックだけあれば高いパフォーマンスを発揮できます。ボトルネックがありません。領域マップは、割り当てと解放をどのようなパターンで行なっても、効率的に更新されます。プールが空でもいっぱいでも、未使用領域を探す効率が変わりません (これに対しビットマップは、ディスクがいっぱいに近付くとスキャンの時間が長くなります)。 最後に、領域マップが完全にいっぱいになると、1 つのエクステントで状態を記録できることに注目してください。 このため、ストレージプールの消費量が 100% に近付くと領域マップのサイズが小さくなり、ディスク容量を最後まで残らず有用なデータのために使うことができる、という利点があります。

どんなファイルシステムで 2 つの基本的なことを記録します。どこにデータがあるかと、未使用領域がどこにあるかです。論理上、未使用領域の記録は、厳密には必須ではありません。すべてのブロックは割り当て済みと未割り当てのいずれかなので、まず全体が未使用領域である状態を想定し、そこから割り当て済みの領域を引き算してやれば、未使用の領域を知ることができます。割り当て済みの領域は、ファイルシステム...

ZFS

Espejos ahumados

Restauración -- reparación, reconstrucción o recomposición -- es el proceso de reparar un dispositivo dañado utilizando el contenido de otros dispositivos en buen estado. Y esto es, exactamente, lo que cada administrador de volúmenes o matriz RAID debe hacer cada vez que uno de sus discos muere, se cambia o sufre un corte de corriente transitorio. Para un espejo, la restauración puede ser tan sencilla como hacer una copia de todo el disco. Para RAID-5 es un poco más complicada: en lugar de copiar un disco en otro, todos los demás discos de la banda RAID-5 deben someterse juntos al proceso XOR. Pero la idea de partida es la misma. En un sistema de almacenamiento tradicional, la restauración se produce en el administrador de volúmenes o en el hardware RAID. En cualquier caso, siempre por debajo del sistema de archivos. Pero esto es ZFS y, por supuesto, tenía que ser diferente. En una entrega anterior he comentado que la restauración de RAID-Z requiere un enfoque distinto puesto que necesita los metadatos del sistema de archivos para determinar la geometría RAID-Z. En efecto, ZFS hace un 'cp -r' del árbol de bloques de almacenamiento de un disco a otro. Suena menos eficiente que una copia directa de un disco completo en otro, y atravesar a salvo un almacenamiento vivo es, sin la menor duda, una operación arriesgada (hablaremos de ello en próximas entregas), pero resulta que la restauración dirigida por metadatos ofrece tantas ventajas que hemos decidido utilizar este procedimiento incluso con espejos sencillos. La razón más importante es la integridad de los datos. Con una copia de disco no hay forma de saber si el disco original devuelve datos en buen estado o no. La integridad de los datos de extremo a extremo requiere que cada bloque de datos se verifique con respecto a una suma de comprobación independiente; no basta con saber que cada bloque es coherente consigo mismo ya que no se capturan los fallos comunes de hardware y firmware, como pueden ser escrituras erróneas o lecturas fantasmas. Al atravesar los metadatos, ZFS puede utilizar sus propias sumas de comprobación de extremo a extremo para detectar y corregir la corrupción silenciosa, exactamente igual que durante una lectura normal. Si un disco devuelve datos dañados, ZFS los detectará y repetirá su lectura. Si se trata de un espejo de tres vías y uno de los dos discos supuestamente sanos estuviera dañado, ZFS utilizará la suma de comprobación para determinar cuál de ellos es el correcto, copiar los datos en el nuevo y reparar el disco dañado. Una simple copia de un disco completo omitiría todo este proceso de protección de datos. Por esta única razón, la restauración dirigida por metadatos debería ser deseable incluso aunque su aplicación pueda tener un coste importante en términos de rendimiento. Afortunadamente, en la mayoría de los casos no es así; de hecho, la restauración dirigida por metadatos ofrece varias ventajas: Sólo bloques vivos. ZFS no pierde tiempo ni ancho de banda de E/S copiando bloques de disco que están libres porque no forman parte del árbol de bloques de almacenamiento. Si su almacenamiento está sólo al 10-20% de su capacidad, es una gran victoria. Poda transaccional. Si un disco sufre un corte de luz transitorio no hace falta restaurarlo por completo, sólo las partes que hayan cambiado. Trataré este asunto con más detalle en una entrega próxima, pero, de momento: ZFS utiliza el tiempo de nacimiento de cada bloque para determinar si es necesario restaurar alguna de las ramas más bajas del árbol. Esto le permite saltarse las ramas más grandes para descubrir rápidamente los datos que han cambiado desde que comenzara el corte de luz. En la práctica, esto significa que si un disco sufre un corte de luz de cinco segundos, la restauración tardará sólo cinco segundos. Y no tendrá que pagar ninguna cantidad extra por arreglarlo - ya sea en metálico o en rendimiento - igual que como cuando cambia algo en Veritas. La poda transaccional es una capacidad intrínseca de la arquitectura de ZFS. Restauración de arriba abajo. Un lugar de almacenamiento es un árbol de bloques. Cuanto más se asciende en el árbol peor es el desastre que supone perder un bloque, porque se pierde el acceso a todo lo que queda por debajo. El proceso a través de metadatos permite a ZFS hacer una restauración de arriba abajo. Es decir, lo primero que ZFS restaura es el bloque superior y las etiquetas del disco. A continuación, restaura los datos de todo el lugar de almacenamiento, luego cada metadatos del sistema de archivos... y así hasta que llega a la base del árbol. En todo este proceso, ZFS respeta rigurosamente la regla siguiente: no se restaura ningún bloque hasta haber restaurado todos sus antecesores. No hace falta destacar la importancia de la regla. Con una copia completa de disco, incluso aunque se haya llegado a alcanzar el 909% existe la posibilidad de que siga pendiente de copiarse uno de los 100 bloques principales del árbol. Esto significa que, desde una punto de vista MTTR, no se ha conseguido el menor progreso: un segundo fallo del disco en este punto sería una auténtica catástrofe. Con la restauración de arriba abajo, cada bloque que se copia aumenta la cantidad de datos detectables. Y si hubiera un segundo fallo del disco... todo lo restaurado hasta ese punto seguiría estando restaurado y disponible. Restauración basada en prioridad. ZFS no lo hace todavía, pero ya lo tiene en los conductos. La restauración ZFS sigue la estructura lógica de los datos y sería muy fácil etiquetar cada sistema de archivos o cada archivo en función de su prioridad para una restauración concreta. Por ejemplo, en un servidor de archivos puede ser necesario restaurar primero los calendarios (son importantes aunque sean pequeños), luego los directorios /var/mail, después los de inicio, y sucesivamente. Lo que espero que se transmita con cada una estas entregas no es sólo la parte mecánica de cómo se implementa una función o característica específica, sino ilustrar el modo en que cada parte de ZFS forma un todo integrado. No es evidente a primera vista, por ejemplo, que la semántica transaccional tenga algo que ver con la restauración - literalmente, incluso la poda transaccional hace más rápida la restauración de órdenes importantes en cortes de luz transitorios. Habrá más sobre eso en la próxima entrega.

Restauración -- reparación, reconstrucción o recomposición -- es el proceso de reparar un dispositivo dañado utilizando el contenido de otros dispositivos en buen estado. Y esto es, exactamente,...

ZFS

烟镜

重新同步(也称为重新构建或重新构造)是使用健康设备修复受损设备的过程。这是每个卷管理器或 RAID 阵列在它的某个磁盘死亡、被替换或经历瞬时断电时必须执行的操作。对于镜像,重新同步就像全盘复制一样简单。对于 RAID-5,它就略微有一些复杂了:不是将一个磁盘复制到另一个磁盘,而是 RAID-5 存储带中的其他所有磁盘都必须异或到一起。但基本思想是相同的。在传统存储系统中,重新同步或者发生在卷管理器中,或者发生在 RAID 硬件中。不管是哪种方式,它都会在文件系统下发生。但这是 ZFS,所以,我们当然必须与众不同。在上一篇文章中,我提到过 RAID-Z 重新同步需要一种不同的方法,因为它需要文件系统元数据来确定 RAID-Z 几何。事实上,ZFS 从一个磁盘到另一个磁盘对存储池的块树进行 cp -r 操作。它听起来没有直接的全盘复制有效,而且安全地遍历有效池一定比较棘手(更多内容在将来的帖子中介绍)。但事实上,元数据驱动的重新同步的优点如此之多,以至于我们在简单的镜像中都使用它。最重要的原因是数据完整性。使用简单的磁盘复制,无法知道源磁盘返回的是否是好数据。端到端的数据完整性需要按照独立校验和验证每个数据块,知道每个块仅仅与自身一致远远不够,因为这无法捕获错读和幻象写这样常见的硬件和固件漏洞。通过遍历元数据,ZFS 可以使用其端到端的校验和来检测并更正无提示数据损坏,就像它在进行正常的读操作一样。如果磁盘瞬时返回坏数据,ZFS 将检测到它并重试读。如果它是 3 路镜像,并且两个认为是好磁盘中的一个被损坏了,ZFS 将使用校验和确定哪个是正确的,将数据复制到新磁盘,并修复损坏的磁盘。简单的全盘复制将绕过所有这种数据保护。就因为这个原因,元数据驱动的重新同步非常值得尝试,即使它的性价比很低。幸运的是,在大多数情况下,性价比都不低。事实上,元数据驱动的重新同步有许多优点:仅有效块。ZFS 不浪费时间和 I/O 带宽复制空闲的磁盘块,因为它们不属于存储池的块树。如果您的池只使用了 10-20%,那就赚到了。 事务修剪。如果磁盘经历了瞬时断电,没有必要重新同步整个磁盘,只针对已经更改的部分即可。我将在以后的文章中详细介绍相关内容,但简短说来:ZFS 使用每个块的生成时间来确定树中是否有更低的部分需要重新同步。这允许它跳过树的巨大分枝,快速发现自断电之后实际更改的数据。这实际上意味着,如果磁盘有 5 秒钟的断电,它将大约花 5 秒来重新同步。而且您不需要支付额外的成本(不管是金钱还是性能),就像您处理 Veritas 更改对象一样。事务修剪是 ZFS 的一个内在架构能力。自上而下重新同步。存储池是块树。越靠近树的顶端,损失一单位数据块的损失越大,因为将丢失对其下任何内容的访问。遍历元数据允许 ZFS 执行自上而下的重新同步。也就是说,ZFS 重新同步的第一个内容是超级块和磁盘标签。然后它重新同步池范围的元数据;然后是每个文件系统的元数据;沿树一直向下。整个过程中,ZFS 遵守以下规则:在其所有祖先都已重新同步之后,某个块才能重新同步。这非常重要。使用全盘复制,即使是在完成 99% 的时候,树中前 100 个块可能还有一个尚未复制。这意味着,从 MTTR 角度看,您实际上还没有任何进展:此时再次发生磁盘故障仍将会是灾难性的。 使用自上而下重新同步,已经复制的每个单独块都会增加可发现的数据量。如果再次发生磁盘故障,已经重新同步到此点的所有内容都将是可用的。基于优先级的重新同步。ZFS 还没有做这项工作,但它正在酝酿中。ZFS 重新同步遵循数据的逻辑结构,所以很容易使用特定的重新同步优先级标记各个文件系统或文件。例如,在文件服务器上,您应该首先重新同步日历(它们很重要但非常小),然后是 /var/mail,然后是主目录,等等。 在这些文章中,我希望传达的不仅是特定功能的实现机制,而且希望能展示 ZFS 的所有部分如何形成一个整体。例如,事务语义与重新同步存在着一些关系,但事务修剪使得从瞬时断电的恢复快了好几个数量级,这不容易一眼就看出来。有关其如何工作的内容将在下一篇文章中说明。

重新同步(也称为重新构建或重新构造)是使用健康设备修复受损设备的过程。这是每个卷管理器或 RAID 阵列在它的某个磁盘死亡、被替换或经历瞬时断电时必须执行的操作。 对于镜像,重新同步就像全盘复制一样简单。对于 RAID-5,它就略微有一些复杂了:不是将一个磁盘复制到另一个磁盘,而是 RAID-5 存储带中的其他所有磁盘都必须异或到一起。但基本思想是相同的。 在传...

ZFS

RAID-Z

La promesa original de RAID (matrices redundantes de discos baratos) fue que proporcionaría unidades de almacenamiento rápidas y fiables utilizando discos baratos. El punto clave era barato; pero sin saber muy bien cómo hemos acabado aquí. ¿Por qué? RAID-5 (y otros esquemas de datos/paridad como RAID-4, RAID-6, par-impar y paridad de fila diagonal) nunca harán cierta la promesa de RAID -- ni pueden -- debido a un defecto conocido como el agujero de escritura RAID-5, por el que cada vez que se actualicen los datos de una banda RAID deberá actualizarse también la paridad para que el valor XOR de todos los discos sea cero -- se trata de la ecuación que permite reconstruir los datos cuando falla un disco. El problema es que no hay forma de actualizar dos o más discos atómicamente, y eso hace que las bandas RAID resulten dañadas por un choque eléctrico o un apagón. Veamos esto con un ejemplo; suponga que la luz se corta después de haber escrito un bloque de datos pero antes de escribir el bloque de paridad correspondiente. En tal caso tendremos que los datos y la paridad de la banda no son coherentes entre sí, y permanecerán así para siempre (a menos que en algún momento consiga escribir una banda completa sobre los datos antiguos). De lo que se deduce que, si un disco falla, el proceso de reconstrucción de RAID generará basura tan pronto como se intente leer cualquier bloque de la misma banda. Y lo peor de todo es que lo hará tan en silencio... y sin la menor idea de que los datos que facilita no son correctos. Hay soluciones de software dedicadas, pero son tan lentas que el software de RAID está muerto en el mercado. Los productos RAID actuales realizan toda la lógica RAID en el hardware, donde pueden utilizar NVRAM para sobrevivir a la pérdida de energía. Funciona, pero es caro. Y, además, hay un molesto problema de rendimiento con los esquemas RAID existentes. Cuando se escribe parcialmente en una banda, es decir, cuando se actualizan menos datos de los que contiene una banda RAID, el sistema RAID debe leer los datos y la paridad antiguos para poder calcular la nueva paridad. Es una cantidad de trabajo enorme. Mientras que una escritura en toda una banda completa se puede hacer de forma asíncrona, una escritura parcial debe hacer la lectura síncrona antes incluso de empezar a escribir. De nuevo, el hardware caro ofrece una solución: una matriz RAID puede guardar temporalmente la escritura parcial en el búfer NVRAM mientras espera que el disco haga su tarea, de modo que la lectura de latencia quede oculta para el usuario. Por supuesto, este procedimiento sólo funciona hasta que el búfer NVRAM se llena. ¡No es problema, dice el vendedor de almacenamiento! Sólo hace soltar más efectivo para tener más NVRAM. No hay problema que no pueda resolverse con dinero. La escritura de banda parcial añade otro problema más a un sistema de archivos transaccional como ZFS. Necesariamente, un sistema de escritura de banda parcial modifica datos vivos, lo que no deja de ser una infracción a la norma que garantiza la semántica transaccional. (No tiene importancia si pierde energía durante una escritura de banda completa por la misma razón que no importa si pierde energía durante cualquier otra escritura en ZFS: ninguno de los bloques en los que se escribe sigue estando vivo). Si sólo hubiéramos hecho mal esas dichosas escrituras de banda parcial... Introducción de RAID-Z. RAID-Z es un esquema de datos/paridad igual que el sistema RAID-5, pero con un ancho de banda dinámico. Cada bloque, sea cual sea su tamaño, tiene una banda RAID-Z propia, lo que significa que cada escritura RAID-Z es una escritura de banda completa. Cuando esto se combina con la semántica transaccional "copiar al escribir" de ZFS, se elimina totalmente el agujero de escritura RAID. Además, RAID-Z es incluso más rápido que el sistema RAID tradicional porque no tiene que "leer-modificar-escribir". ¡Ja, ja, ja! ¿de qué habla? ¿Ancho de banda variable? Vale, parece bastante claro, pero, si es tan buena idea... ¿por qué no lo hace todo el mundo? Bueno, el truco está en la reconstrucción RAID-Z. Las bandas son todas de tamaños distintos, lo que quiere decir que no existen fórmulas de tipo "poner todos los valores XOR de los discos a cero". Ni es necesario atravesar el sistema de archivos de metadatos para determinar la geometría RAID-Z. Tenga en cuenta que esto sería imposible si el sistema de archivos y la matriz RAID fueran productos independientes... y he aquí la razón de que no haya nada que iguale a RAID-Z en el mercado del almacenamiento actual. Lo que en verdad necesita es una visión integrada de la estructura lógica y física de los datos para hacer que funcione. Pero, espere, según dice: ¿no es lento? ¿no es caro atravesar todos los metadatos? En realidad es un intercambio de concesiones. Si el lugar de almacenamiento está a punto de llenarse, entonces, sí, es lento. Pero si no está a punto de llenarse, la reconstrucción impulsada de los metadatos es mucho más rápida porque sólo copia los datos vivos, sin perder tiempo en copiar el espacio sin asignar del disco. Pero mucho más importante todavía es que, a medida que atraviesa los metadados, ZFS puede validar cada bloque al compararlo con una suma de comprobación de 256 bits. Los productos RAID tradicionales no pueden hacer esto; se limitan a agrupar a ciegas los XOR de los datos. Sin embargo, el punto más importante de RAID-Z es... la auto sanación de los datos. Además de poder gestionar un error total de disco, RAID-Z es capaz de detectar y corregir la corrupción silenciosa de los datos. Cada vez que se lee un bloque RAID-Z, ZFS lo compara con su propia suma de comprobación. Si los datos del disco no devuelven una respuesta correcta, ZFS lee la paridad y lleva a cabo la reconstrucción del proceso para averiguar qué disco ha devuelto los datos incorrectos. A continuación, repara el disco dañado y envía los datos correctos a la aplicación. ZFS se encarga también de informar del incidente a través de Solaris FMA para que el administrador del sistema sepa que uno de los discos está fallando. Por último, recuerde que RAID-Z no requiere ningún tipo de hardware especial. No necesita NVRAM para garantizar la corrección de los datos, ni necesita escribir en el búfer para ofrecer un buen rendimiento. Con RAID-Z, ZFS se hace realidad la promesa original de RAID: ofrecer unidades de almacenamiento rápidas, fiables y utilizando discos baratos. Para ver un ejemplo real de RAID-Z detectando y corrigiendo la corrupción silenciosa de datos en un hardware con problemas, consulte Saga SATA de Eric Lowe. El algoritmo actual RAID-Z es de paridad sencilla, pero el concepto RAID-Z funciona con cualquier tipo de RAID. En el trabajo se ha utilizado una versión de doble paridad. Un último detalle que los colegas programadores sabrán apreciar: toda la implementación de RAID-Z está sólo en 599 líneas. Technorati Tags: OpenSolaris Solaris ZFS

La promesa original de RAID (matrices redundantes de discos baratos) fue que proporcionaría unidades de almacenamiento rápidas y fiables utilizando discos baratos. El punto clave era barato; pero sin...

ZFS

RAID-Z

A promessa original do RAID (Redundant Arrays of Inexpensive Disks) era que proporcionaria armazenamento rápido e confiável usando discos baratos. A palavra-chave era barato; contudo, de alguma forma fomos parar aqui. Por que? O RAID-5 (e outros esquemas de paridade/dados, como RAID-4, RAID-6, par-ímpar e paridade diagonal de linha) nunca chegou a cumprir a promessa do RAID, nem pode, devido a uma falha fatal conhecida como furo de gravação RAID-5. Sempre que atualizar os dados em uma faixa RAID, você também precisará atualizar a paridade, de forma que a aplicação do operador lógico XOR a todos os discos resulte em zero -- é essa equação que permite reconstruir os dados em caso de falha de um disco. O problema é que não há como atualizar dois ou mais discos de forma atômica, portanto, as faixas RAID podem ser danificadas durante um travamento ou uma falta de energia. Para verificar isso, suponha que falte energia após a gravação de um bloco de dados, mas antes da gravação do bloco de paridade correspondente. Nesse caso, os dados e a paridade dessa faixa estão inconsistentes e assim permanecerão para sempre (a menos que, em algum momento, os dados antigos sejam substituídos por uma gravação de faixa completa). Portanto, em caso de falha de um disco, o processo de reconstrução RAID gerará lixo na próxima vez em que qualquer bloco dessa faixa for lido. O que é pior, ele fará isso silenciosamente, sem a menor idéia de que está fornecendo dados corrompidos. Existem soluções alternativas de software para isso, mas elas são tão lentas que o RAID de software desapareceu do mercado. Todos os produtos RAID atuais executam a lógica RAID no hardware, no qual podem usar a NVRAM para sobreviver a faltas de energia. Isso funciona, mas é caro. Existe também um desagradável problema de desempenho com os esquemas RAID existentes. Quando é feita uma gravação de faixa parcial (ou seja, quando não são atualizados todos os dados contidos em uma única faixa RAID), o sistema RAID precisa ler a paridade e os dados antigos para calcular a nova paridade. Isso acarreta uma enorme queda no desempenho. Enquanto uma gravação de faixa completa pode simplesmente ser feita de forma assíncrona, uma gravação de faixa parcial precisa fazer leituras síncronas antes até mesmo de iniciar as gravações. Uma vez mais, hardware caro oferece uma solução: uma matriz RAID pode armazenar gravações de faixa parcial em buffer na NVRAM, enquanto aguarda a conclusão das leituras do disco, ocultando, assim, a latência de leitura do usuário. Obviamente isso só funciona até que o buffer da NVRAM fique cheio. Isso não é problema, afirma seu fornecedor de armazenamento! Basta desembolsar mais dinheiro para comprar mais NVRAM. Não existe problema que o dinheiro não resolva. As gravações de faixa parcial apresentam um outro problema em sistemas de arquivos transacionais como o ZFS. Elas necessariamente modificam dados ativos, o que viola uma das regras que asseguram a semântica transacional. (Não importa que falte energia durante uma gravação de faixa completa, pelo mesmo motivo que não importa que falte energia durante qualquer outra gravação no ZFS: nenhum dos blocos nos quais você está gravando está ativo ainda.) Se não tivéssemos de fazer essas terríveis gravações de faixa parcial... Entra em cena o RAID-Z RAID-Z é um esquema de paridade/dados como o RAID-5, mas com largura de faixa dinâmica. Cada bloco, independentemente do seu tamanho, é a sua própria faixa RAID-Z. Isso significa que cada gravação RAID-Z é uma gravação de faixa completa. Isso, quando combinado com a semântica transacional "copiar ao gravar" do ZFS, elimina o furo de gravação RAID completamente. O RAID-Z também é mais rápido do que o RAID tradicional porque nunca precisa executar operações de leitura-modificação-gravação. Epa, epa, epa! É isso mesmo? Largura de faixa variável? Nossa, isso parece bem óbvio, mas se é uma idéia tão boa, por que não é adotada por todos? Bem, o macete está na reconstrução RAID-Z. Como todas as faixas têm tamanhos diferentes, não existe uma fórmula simples como "a aplicação do operador lógico XOR a todos os discos resulta em zero". É preciso percorrer os metadados do sistema de arquivos para determinar a geometria RAID-Z. Observe que isso seria impossível se o sistema de arquivos e a matriz RAID fossem produtos distintos, e essa é a razão pela qual não há nada que se compare ao RAID-Z no mercado de armazenamento atual. É imprescindível uma visão integrada da estrutura lógica e física dos dados para fazer com que funcione. Mas, espere, você diria: isso não é lento? Não sai caro percorrer todos os metadados? Na verdade, trata-se de um trade-off. Se o pool de armazenamento estiver bem próximo à capacidade máxima, então a resposta é sim, o processo é mais lento. Mas se ele não estiver próximo à capacidade máxima, a reconstrução orientada por metadados será, na verdade, mais rápida porque copia apenas dados ativos, não perdendo tempo com a cópia de espaço não alocado em disco. Mas muito mais importante é que, à medida que percorre os metadados, o ZFS pode validar cada bloco em relação a uma soma de verificação de 256 bits. Produtos RAID tradicionais não podem fazer isso; eles simplesmente executam uma operação lógica XOR nos dados, às cegas. O que nos leva ao mais ponto interessante do RAID-Z: dados auto-recuperáveis. Além de gerenciar falhas do disco inteiro, o RAID-Z também detecta e corrige corrupção silenciosa de dados. Sempre que um bloco RAID-Z é lido, o ZFS o compara com sua soma de verificação. Se os discos de dados não retornarem a resposta correta, o ZFS lerá a paridade e, depois, fará a reconstrução combinatória para averiguar qual disco retornou dados inválidos. Em seguida, fará os devidos reparos no disco danificado e retornará dados válidos ao aplicativo. O ZFS também relatará o incidente através do Solaris FMA, para que o administrador do sistema saiba que um dos disco está falhando silenciosamente. Por fim, observe que o RAID-Z não requer nenhum tipo de hardware especial. Ele não precisa de NVRAM para garantir a correção dos dados, nem precisa de gravação em buffer para oferecer um bom desempenho. Com o RAID-Z, o ZFS torna realidade a promessa original do RAID: oferecer armazenamento rápido e confiável usando discos de consumo baratos. Para ver um exemplo real do RAID-Z detectando e corrigindo corrupção silenciosa de dados em hardware com problemas, consulte a Saga SATA por Eric Lowe. O algoritmo RAID-Z atual tem paridade única, mas o conceito RAID-Z funciona para qualquer tipo de RAID. Uma versão de paridade dupla está a caminho. Um último detalhe com o qual os amigos programadores irão se deleitar: toda a implementação do RAID-Z tem apenas 599 linhas. Tags Technorati: OpenSolaris Solaris ZFS

A promessa original do RAID (Redundant Arrays of Inexpensive Disks) era que proporcionaria armazenamento rápido e confiável usando discos baratos. A palavra-chave era barato; contudo, de alguma forma...

ZFS

RAID-Z

RAID(廉价磁盘冗余阵列)最初的承诺是它将使用廉价磁盘提供快速、可靠的存储。重点在于廉价,但不知为何我们最终却得到这种结果。为什么呢?RAID-5(以及其他数据/奇偶校验方案,比如 RAID-4、RAID-6、奇偶和行对角奇偶校验)从未完全履行过 RAID 的承诺,并且也无法履行,这是因为存在一种称为 RAID-5 写漏洞的致命缺陷。不管何时更新 RAID 存储条,还必须更新校验,以便所有磁盘异或为 0,正是这个等式使您能在磁盘故障时重构数据。问题在于无法以原子方式更新两个或多个磁盘,所以 RAID 存储条可能在崩溃或电源断电时被损坏。为了认清这个问题,假设您在写入数据块之后、但在写入相应校验块之前断电。现在,此存储条的数据和奇偶校验就不一致,而且它们将永远保持不一致(除非在某个时候使用一个全存储条写操作覆盖了旧数据)。因此,如果磁盘故障,RAID 重构过程将在您下一次读取此存储条上的任何块时生成垃圾。更糟的是,它这样做使没有任何提示,它根本不知道提供给您的是损坏的数据。为解决此问题,出现过一些仅用于软件的应急方案,但它们的速度非常慢,所以软件 RAID 已经在市场中消亡。当前的 RAID 产品全部在硬件中执行 RAID 逻辑,这样它们可以使用 NVRAM 来应对断电。这确实有用,但成本很高。现有 RAID 方案还存在一个糟糕的性能问题。当执行部分存储条写操作时,也就是说,当更新的数据少于单个 RAID 存储条包含的数据时,RAID 系统必须读取旧数据和奇偶校验来计算新奇偶校验。这是一个巨大的性能损失。全存储条写操作异步执行所有写操作,而部分存储条写操作必须在同步读操作之后才能启动写操作。又一次,昂贵的硬件提供了一种解决方案:RAID 阵列可以在等待磁盘读操作完成时,在 NVRAM 中缓冲部分存储条写操作,这样读延迟就可以对用户隐藏。当然,这种方法只在 NVRAM 缓冲器用完之前有效。没问题!您的存储供应商会说。只要再多掏些现金,多买些 NVRAM 就好了。没有您的钱包不能解决的问题。部分存储条写操作在事务文件系统(比如 ZFS)中又提出了另一个问题。部分存储条写操作必然会修改有效数据,这违反了确保事务语义这一规则。(如果在完全存储条写时断电,则没什么问题,同理,如果您在 ZFS 中的其他任何写操作期间断电也没什么问题:但您正在写入的块没有一个是有效的。) 但愿我们不用执行这些烦人的部分存储条写操作…… 进入 RAID-Z 的世界。 RAID-Z 是一种数据/奇偶校验方案,比如 RAID-5,但它使用动态的存储条宽度。每个块是自己的 RAID-Z 存储条,不管块大小是多少。这意味着,每个 RAID-Z 写操作是一个全存储条写操作。当与 ZFS 的“写复制”事务语义相结合时,这完全消除了 RAID 写漏洞。RAID-Z 还比传统的 RAID 快,因为它从来不用执行读-改-写。 哇,哇,哇 —— 就这样?可变存储条宽度?天啊,这也太简单了。如果这真是一个好注意的话,那为什么并非人人都这样做呢? 这里棘手的地方在于 RAID-Z 重构。因为存储条的大小各不相同,所有根本没有像“所有磁盘都异或为 0”这样简单的公式。您必须遍历文件系统元数据来确定 RAID-Z 几何。注意,如果文件系统和 RAID 阵列是相互独立的产品的话,这将无法办到,这就是为什么今天的存储市场没有 RAID-Z 这样的东西。要解决这个问题,您真正需要的是一个集成数据逻辑和物理结构的视图。等等,您说:这是不是太慢了?遍历所有元数据的成本不是很高吗?实际上,这是一个折衷方案。如果您的存储池几乎已满,那么它确实会比较慢。但如果不是这样,则元数据驱动的重构事实上比较快,因为它只复制有效数据;而不浪费时间复制未分配的磁盘空间。 但更重要的是,遍历元数据意味着 ZFS 可以按照它的 256 位校验和验证每个块。传统 RAID 产品做不到这一点;它们只是盲目地一起异或数据。RAID-Z 带给我们最酷的一件事是:自愈数据。除了处理全磁盘故障之外,RAID-Z 还可以检测并更正无提示的数据损坏。不管何时读取 RAID-Z 块,ZFS 都会将其与校验和进行比较。如果数据磁盘没有返回正确的答案,ZFS 读取奇偶校验,然后执行组合重构以确定哪个磁盘返回了坏数据。然后,ZFS 修复损坏的磁盘,并向应用程序返回好数据。ZFS 还通过 Solaris FMA 报告事故,以便系统管理员知道其中一个磁盘无提示地发生了故障。 最后,注意 RAID-Z 不需要任何特殊的硬件。它不需要 NVRAM 进行更正,不需要写缓冲来获取好的性能。使用 RAID-Z,ZFS 很好地履行了最初的 RAID 承诺:它使用廉价的商品磁盘提供了快速、可靠的存储。有关 RAID-Z 检测并更正片状硬盘上无提示数据损坏的真实示例,请参阅 Eric Lowe's SATA saga。当前的 RAID-Z 算法是单奇偶校验,但 RAID-Z 概念适合任何 RAID 类型。双奇偶校验版本正在筹备中。同行编程人员将感激的最后一件事是:整个 RAID-Z 实现只有 599 行。Technorati Tags:OpenSolaris Solaris ZFS

RAID(廉价磁盘冗余阵列)最初的承诺是它将使用廉价磁盘提供快速、可靠的存储。重点在于廉价,但不知为何我们最终却得到这种结果。为什么呢? RAID-5(以及其他数据/奇偶校验方案,比如 RAID-4、RAID-6、奇偶和行对角奇偶校验)从未完全履行过 RAID 的承诺,并且也无法履行,这是因为存在一种称为 RAID-5 写漏洞的致命缺陷。不管何时更新 RAID 存储条,还必须更新校...

ZFS

Violação desenfreada de camadas?

Andrew Morton chamou o ZFS de "violação desenfreada de camadas" porque combina a funcionalidade de um sistema de arquivos, um gerenciador de volumes e uma controladora RAID. Acho que isso depende de qual é o sentido da palavra violar. Enquanto estávamos projetando o ZFS, observamos que as camadas padrão da pilha de armazenamento induzem a uma grande complexidade desnecessária e lógica duplicada. Descobrimos que ao fatorar um pouco o problema novamente, ou seja, alterar os limites entre as camadas, podemos tornar tudo muito mais simples.Um exemplo da matemática (minha verdadeira formação) oferece um prólogo útil.Suponha que você tenha que calcular a soma de n=1 até o infinito, de 1/n(n+1).Expandindo termo a termo, temos:        1/(1\*2) + 1/(2\*3) + 1/(3\*4) + 1/(4\*5) + ...Ou seja,        1/2 + 1/6 + 1/12 + 1/20 + ...Até onde essa série infinita pode ser combinada? Pode parecer um problema difícil, mas somente porque não o estamos examinando da perspectiva correta. Se você for sagaz, perceberá que existe uma maneira diferente de expressar cada termo:        1/n(n+1) = 1/n - 1/(n+1)Por exemplo,        1/(1\*2) = 1/1 - 1/2        1/(2\*3) = 1/2 - 1/3        1/(3\*4) = 1/3 - 1/4Dessa forma, nossa soma pode ser expressa como:        (1/1 - 1/2) + (1/2 - 1/3) + (1/3 - 1/4) + (1/4 - 1/5) + ...Agora, observe o padrão: cada termo que subtraímos, somamos novamente. Somente no Congresso isso é considerado como trabalho. De modo que, se reorganizarmos os parênteses, ou seja, se violarmos as camadas do problema original desenfreadamente usando a associatividade para fatorar novamente a aritmética de termos adjacentes da série, teremos isto:        1/1 + (-1/2 + 1/2) + (-1/3 + 1/3) + (-1/4 + 1/4) + ...ou        1/1 + 0 + 0 + 0 + ...Em outras palavras,        1.Não é legal?Os matemáticos têm um termo para designar isso. Quando você reorganiza os termos de uma série de forma que se cancelem, isso é chamado de telescopia, por analogia com um telescópio manual cujos segmentos se encaixam um dentro do outro. Resumindo, é isto que o ZFS faz: ele encaixa os segmentos de uma pilha de armazenamento. É o que nos permite ter um sistema de arquivos, um gerenciador de volumes, RAID com paridade simples e dupla, compactação, instantâneos, clones e muitas outras coisas úteis em apenas 80.000 linhas de código.Um sistema de armazenamento é mais complexo do que essa analogia simples, mas num nível mais alto, aplica-se a mesma idéia. Você pode encarar uma pilha de armazenamento como uma série de conversões de um esquema de nomeação em outro. Em última instância, é a conversão de um nome de arquivo em um LBA (endereço de bloco lógico) de disco. Normalmente, é parecido com isto: sistema de arquivos(superior): nome do arquivo em objeto (inode)        sistema de arquivos(inferior): objeto em LBA de volume        gerenciador de volume: LBA de volume em LBA de matriz        controladora RAID: LBA de matriz em LBA de discoEssa é a pilha que estamos prestes a fatorar novamente.Primeiro, observe que a camada de sistema de arquivos tradicional é muito monolítica. Seria melhor separar a parte "nome do arquivo em objeto" (a metade superior) da parte "objeto em LBA de volume" (a metade inferior), de modo que possamos reutilizar o mesmo código da metade inferior para aceitar outros tipos de armazenamento, como objetos e destinos iSCSI, que não têm nomes de arquivo. Assim, as classes de armazenamento podem se comunicar diretamente com a camada de objeto. Isso é mais eficiente do que algo como /dev/lofi, que faz um arquivo POSIX parecer com um dispositivo. Mas, o mais importante é que fornece um novo e poderoso modelo de programação, armazenamento de objetos, sem qualquer código adicional.Segundo, observe que o LBA de volume fica totalmente sem utilidade. A adição de uma camada de vias indiretas (indirection) normalmente adiciona flexibilidade, mas não é o caso aqui: na verdade, estamos traduzindo do inglês para o francês e daí para o alemão, quando poderíamos simplesmente traduzir diretamente e de maneira fácil do inglês para o alemão. O francês intermediário não tem valor intrínseco. Não é visível para os aplicativos, não é visível para a matriz RAID e não tem qualquer função administrativa. É somente overhead.Portanto, o ZFS eliminou essa camada inteira. Há somente três camadas distintas no ZFS: ZPL (ZFS POSIX Layer, camada POSIX do ZFS), que fornece a semântica do sistema de arquivos POSIX tradicional; DMU (Data Management Unit, unidade de gerenciamento de dados), que fornece um armazenamento de objetos transacionais para fins gerais e SPA (Storage Pool Allocator, alocador de pool de armazenamento), que fornece a alocação de blocos virtuais e a transformação de dados (replicação, compactação e criptografia imediata). A pilha de conversão geral do ZFS tem esta aparência:        ZPL: nome do arquivo em objeto        DMU: objeto em DVA (endereço virtual de dados)        SPA: DVA em LBA de discoA DMU permite que tanto o arquivo como o bloco acessem um pool comum de armazenamento físico. O acesso do arquivo se faz por meio do ZPL, enquanto o acesso do bloco é simplesmente um mapeamento direto para um único objeto DMU. Também estamos desenvolvendo novos métodos de acesso a dados que usam os recursos transacionais da DMU de maneiras mais interessantes; falaremos mais sobre isso outro dia.A arquitetura do ZFS elimina toda uma camada de conversão e, junto com ela, toda uma classe de metadados (LBAs de volume). Ele também elimina a necessidade de controladoras RAID de hardware. Ao mesmo tempo, fornece uma nova interface útil, armazenamento de objetos, que anteriormente era inacessível porque estava escondida dentro de um monolítico sistema de arquivos.Dessa maneira, não creio ter violado nada. E você?

Andrew Morton chamou o ZFS de "violação desenfreada de camadas" porque combina a funcionalidade de um sistema de arquivos, um gerenciador de volumes e uma controladora RAID. Acho que isso depende de...

ZFS

¿Infracción incontrolada de capas?

Andrew Morton ha calificado a ZFS como una "infracción incontrolada de capas" porque combina la funcionalidad de un sistema de archivos, un administrador de volúmenes y un controlador de RAID. Supongo que todo depende del significado del término infracción. Al diseñar ZFS observamos que la norma de estratificación de la pila de almacenamiento lleva consigo una sorprendente cantidad de lógica innecesariamente compleja y duplicada. También encontramos que al refactorizar el problema un poco, es decir, al cambiar los límites entre las capas, podíamos simplificar aún más el proceso.Un ejemplo de matemáticas (mi bagaje real) puede servirnos de prólogo clarificador.Supogamos que tenemos que calcular la suma de n=1 a infinito, de 1/n(n+1).Desarrollándolo término a término, tenemos:        1/(1\*2) + 1/(2\*3) + 1/(3\*4) + 1/(4\*5) + ...Es decir,        1/2 + 1/6 + 1/12 + 1/20 + ...¿A qué sumamos la serie infinita? Puede parecer un problema bastante arduo, pero sólo porque no lo estamos viendo de la forma correcta. Con un poquito de inteligencia es facil observar que hay distintas formas de expresar cada término:        1/n(n+1) = 1/n - 1/(n+1)Por ejemplo,        1/(1\*2) = 1/1 - 1/2        1/(2\*3) = 1/2 - 1/3        1/(3\*4) = 1/3 - 1/4Por lo tanto, nuestra suma puede expresarse como:        (1/1 - 1/2) + (1/2 - 1/3) + (1/3 - 1/4) + (1/4 - 1/5) + ...Bien, veamos ahora el patrón: cada término que restamos, lo añadimos de nuevo. Únicamente en el Congreso esto no cuenta como trabajo. Por tanto, si sólo reordenamos el paréntesis, es decir, si infringimos la estratificación descontroladamente utilizando la asociatividad para refactorizar la aritmética a través de los términos adyacentes de las series, tenemos:        1/1 + (-1/2 + 1/2) + (-1/3 + 1/3) + (-1/4 + 1/4) + ...o         1/1 + 0 + 0 + 0 + ...En otras palabras,        1.¿A que queda bien?Los matemáticos tienen un término para esto. Cuando se reordenan los términos de una serie hasta que se anula, se dice que es una serie telescópica, por analogía con un telescopio de mano contraíble. En pocas palabras, es lo que ZFS hace: contrae la pila de almacenamiento. Esto es lo que hace posible tener un sistema de archivos, un administrador de volúmenes, un RAID de doble paridad, compresión, instantáneas, clones y un montón de de otras muchas cosas útiles en tan sólo 80.000 líneas de código.Un sistema de almacenamiento es más completo que esta sencilla analogía, pero en realidad aplica la misma idea a un nivel más alto. Podría pensarse en cualquier pila de almacenamiento como una serie de traducciones de un esquema nombres a otro. En última instancia, es la traducción de un nombre de archivo a una LBA (dirección de bloque lógico) de disco. El aspecto que suele tener es más o menos así: sistema de archivos (superior): nombre de archivo a objeto (inodo)       sistema de archivos (inferior): objeto a LBA de volumen        administrador de volúmenes: LBA de volumen a LBA de matriz        controlador de RAID: LBA de matriz a LBA de discoEsta es la pila que estamos a punto de refactorizar.Primero, observe que la capa del sistema de archivos tradicional es demasiado monolítica, y sería mejor separar la parte nombre de archivo a objeto (la mitad superior) de la parte objeto a LBA de volumen (la mitad inferior) para que podamos reutilizar el mismo código de la mitad inferior para admitir otros tipos de almacenamiento, como objetos o destinos iSCSI que no tienen nombres de archivo. Estas clases de almacenamiento podrían hablar directamente a la capa de objetos, lo que es mucho más eficaz que pasar a través de algo así como /dev/lofi, que es lo que hace que POSIX parezca un dispositivo. Pero lo más importante de todo, es que ofrece un potente modelo de programación nuevo -- almacenamiento de objetos -- sin necesidad de ningún otro código adicional.Segundo, la LBA de volumen es absolutamente inútil. Por lo general, añadir una capa de dirección suele ser una forma de dar más flexibilidad, pero no es el caso: de hecho, estamos traduciendo de inglés a francés y de francés a alemán cuando podemos traducir directamente de inglés a alemán sin el menor problema. El francés intermedio no tiene un valor intrínseco. No es visible para las aplicaciones, no es visible para la matriz RAID y no desempeña ninguna función administrativa. Sólo está ahí arriba.Por eso, ZFS ha desplegado el telescopio de todas las capas. ZFS tiene sólo tres capas bien diferenciadas: la ZPL (ZFS POSIX Layer), que ofrece la semántica del sistema de archivo POSIX tradicional; la DMU (unidad de gestión de datos), que ofrece un almacén de objetos transaccionales de uso general; y la SPA (asignador de lugares de almacenamiento), que ofrece asignación virtual de bloques y transformaciones de datos (replicación, compresión y pronto encriptación). La pila de traducción general de ZFS es similar a:        ZPL: nombre de archivo a objeto        DMU: objeto a DVA (dirección virtual de datos)        SPA: DVA a LBA de discoLa DMU permite que tanto el archivo como el bloque accedan a un lugar común de almacenamiento físico. El acceso al archivo se realiza a través de ZPL, mientras que el bloque se conduce directamente hacia un único objeto DMU. También estamos desarrollando nuevos métodos de acceso a datos que utilizan la capacidad transaccional de DMU de formas mucho más interesantes y de las que trataremos otro dia.La arquitectura ZFS elimina toda una capa de transacción y, junto con ella, una clase entera de metadatos (las LBA de volúmenes), además de eliminar la necesidad de utilizar controladores RAID para hardware. Al mismo tiempo, ofrece una nueva interfaz útil -- almacenamiento de objetos -- totalmente inaccesible hasta ahora por encontrarse enterrada en un sistema de archivos monolítico.Así pues, no creo haber infrigido nada. ¿Y usted?

Andrew Morton ha calificado a ZFS como una "infracción incontrolada de capas" porque combina la funcionalidad de un sistema de archivos, un administrador de volúmenes y un controlador de RAID. Supongo...

ZFS

泛滥的分层违规?

众所周知,Andrew Morton 将 ZFS 称为“泛滥的分层违规(rampant layering violation)”,因为它组合了文件系统、卷管理器和 RAID 控制器的功能。我假设它的表意重点在于词违规。在设计 ZFS 时,我们观察到,存储堆栈的标准分层引入了大量不必要的复杂性和重复逻辑。我们发现对这个问题进行一些重构,也就说,更改层之间的边界,我们可以让整个事情变得非常简单。我们首先使用数学(我的实际专业)中的一个例子作为开场白。假设您必须计算 1/n(n+1) 的和(其中 n=1 到无穷大)。逐项展开,我们得到:        1/(1\*2) + 1/(2\*3) + 1/(3\*4) + 1/(4\*5) + ...也就是        1/2 + 1/6 + 1/12 + 1/20 + ...这个无穷序列总和是多少呢?看起来好像是很困难的问题,但这只是因为我们没有找到正确的方法。如果您比较聪明,可能会注意到可以用另一种方式表示每项:        1/n(n+1) = 1/n - 1/(n+1)例如,        1/(1\*2) = 1/1 - 1/2        1/(2\*3) = 1/2 - 1/3        1/(3\*4) = 1/3 - 1/4因此,我们的和可以表示为:        (1/1 - 1/2) + (1/2 - 1/3) + (1/3 - 1/4) + (1/4 - 1/5) + ...现在,注意模式:我们减去的每项,我们加回去。  只有在会议中才会将此视为工作。 所以如果我们只需重排列括号,也就是说,我们通过使用关联性在序列的相邻项之间重构算术,来蔓延打乱原始问题的分层 —— 我们得到了这个:        1/1 + (-1/2 + 1/2) + (-1/3 + 1/3) + (-1/4 + 1/4) + ...or        1/1 + 0 + 0 + 0 + ...或者说        1。这难道不酷吗?数学对此有一个术语。当您重新排列序列的项,以便它们相互抵消时,就称为缩放(telescoping) —— 就好像可重叠的手持望远镜。本质上,这就说 ZFS 所做的事情:它缩放存储堆栈。它允许我们在仅仅 80,000 行代码中拥有文件系统、卷管理器、单/双奇偶校验 RAID、压缩、快照、复制以及其他许多有用的内容。存储系统比这个简单的类比要复杂多了,但从更高的层次上看,它们确实应用了相同的思想。您可以将任何存储堆栈视为一系列从一个命名方案到另一个命名方案的转换,最终将文件名转换为磁盘 LBA(逻辑块地址)。通常如下所示: filesystem(upper): filename to object (inode)        filesystem(lower): object to volume LBA        volume manager: volume LBA to array LBA        RAID controller: array LBA to disk LBA这是我们将要重构的堆栈。首先,注意传统文件系统层太单调了。如果将文件文件-对象部分(上半部分)从对象-卷-LBA 部分(下半部分)分离出来会更好,这样我们就可以重用相同的下半部分代码来支持其他种类的存储,比如对象和 iSCSI 目标,它们没有文件名。这些存储类就可以直接与对象层对话。这比遍历类似 /dev/lofi 的结构要更加有效,它会让 POSIX 文件看起来像一个设备。但更重要的是,它提供了强大的新编程模型 —— 对象存储,而不需要再添加任何代码。其次,注意卷 LBA 完全没有用。添加间接层通常会增加灵活性,但在此处不适用:实际上,我们是将英语翻译为法语,然后再翻译为德语,而实际上我们可以简单地直接将英语翻译为德语。中间的法语没有任何内在价值。它对应用程序不可见,对 RAID 阵列不可见,它不提供任何管理功能。它只是负担。所以 ZFS 缩放了整个层。ZFS 中只有三个不同的层:ZPL (ZFS POSIX Layer),提供传统的 POSIX 文件系统语义;DMU (Data Management Unit),提供通用的事务对象存储;SPA (Storage Pool Allocator),提供虚拟块分配和数据转换(复制、压缩和快速加密)。整个 ZFS 转换堆栈如下所示:        ZPL: filename to object        DMU: object to DVA (data virtual address)        SPA: DVA to disk LBADMU 提供了对公用物理存储池的文件和块访问。文件访问遍历 ZPL,而块访问只是直接映射到单个 DMU 对象。我们还开发了新的数据访问方法,以更有效的方式使用 DMU 的事务能力(有关这部分,我们改天再谈)。ZFS 架构消除了整个转换层,而且同时消除了整个元数据类(卷 LBA)。它还消除了对硬件 RAID 控制器的需要。同时,它提供了一个有用的新接口 —— 对象存储,这在以前是不可访问的,因为它被埋葬在单调的文件系统中了。我确实没感到违规。您呢?

众所周知,Andrew Morton 将 ZFS 称为“泛滥的分层违规(rampant layering violation)”,因为它组合了文件系统、卷管理器和 RAID 控制器的功能。我假设它的表意重点在于词违规。在设计 ZFS 时,我们观察到,存储堆栈的标准分层引入了大量不必要的复杂性和重复逻辑。我们发现对这个问题进行一些重构,也就说,更改层之间的边界,我们可以让整个事情变得非常简单。我们首先...

ZFS

Mapas espaciales

Cada sistema de archivos debe registrar rigurosamenten dos cosas básicas: la ubicación de los datos y la ubicación del espacio libre.En principio, no parece estrictamente necesario saber dónde está el espacio libre: cada bloque está libre o asignado, de modo que el espacio libre se puede calcular si suponemos que todo es espacio libre al que se le va restando cada asignación. Para calcular el espacio asignado basta recorrer el sistema de archivos desde la raíz; todo bloque que no se pueda encontrar al atravesar el espacio desde la raíz es, por definición, libre.En la práctica, esta forma de localizar espacio libre sería insufrible porque cualquier sistema de archivos de un cierto tamaño tardaría una eternidad en averiguarlo. Para agilizar la asignación y liberación de bloques, el sistema de archivos necesita un método eficaz que le permita controlar la cantidad de espacio libre. En esta entrega examinaremos los métodos más comunes, las razones que dificultan su escalabilidad y los nuevos enfoques que se divisan para ZFS. Mapas de bitsLa forma más frecuente de representar el espacio libre es mediante un mapa de bits, o lo que es igual, una matriz de bits en la que el enésimo bit indica si el enésimo bloque está asignado o libre. El gasto general de un mapa de bits es bastante bajo: 1 bit por bloque. Para un bloque de tamaño 4 K, serían 1/(4096\*8) = 0,003% (el 8 viene de 8 bits por byte).Para un sistema de archivos de 1 GB, el mapa de bits es de 32 KB -- algo que encaja fácilmente en memoria y que se pueden escanear rápidamente para liberar espacio en disco. Para un sistema de archivos de 1 TB, el mapa de bits es de 32 MB -- todavía se puede encajar bien en memoria, pero ya no es tan pequeño ni tan rápido de escanear. Para un sistema de archivos de 1 PB, el mapa de bits es de 32 GB y, sencillamente, eso ya es algo que no cabe en la memoria de la mayoría de máquinas, además de que para escanear el mapa de bits haría falta leerlo desde el disco... y eso sí que resulta mucho más lento aún.Está claro que esto no es escalable en absoluto.Una solución aparentemente fácil podría ser dividir el mapa de bits en trozos pequeños y seguir la pista del número de bits de cada trozo. Por ejemplo, para un sistema de archivos de 1 PB con bloques de 4 K, se podría dividir el espacio libre en un millón de mapas de bits de 32 KB cada uno. La información resumida (el millón de enteros indicando la cantidad del espacio de cada mapa de bits) cabe en la memoria y eso hace que sea fácil encontrar un mapa de bits con espacio libre y que sea rápido escanear el mapa de bits.Pero sigue habiendo un problema fundamental: el mapa de bits debe actualizarse no sólo cada vez que se asigna un nuevo bloque, sino también cada vez que se libera un bloque antiguo. El sistema de archivos controla la ubicación de todas las asignaciones (decide en qué bloques se colocan los datos), pero no tiene ningún control sobre la ubicación de los libres. Algo tan simple como 'rm -rf' puede hacer que se liberen bloques por todo el disco. Con nuestro sistema de archivos de 1 PB del ejemplo, en el peor de los casos, la supresión de 4 GB de datos (un millón de bloques de 4 K) supondría leer cada mapa de bits del millón, modificarlo y escribirlo de nuevo. Total, dos millones de E/S en el disco para liberar apenas 4 GB -- es poco razonable, incluso en el peor de los casos de comportamiento.Más que ningún otro factor, esta es la razón de que los mapas de bits no sean escalables: por lo general, el espacio se libera aleatoriamente y los mapas de bits que no encajan en memoria ofrecen un comportamiento patológico cuando se accede a ellos de forma aleatoria.Árboles BOtro modo frecuente de representar el espacio libre es con un árbol B de inserciones. Una inserción es una región contigua de espacio libre descrita mediante dos enteros: desviación y longitud. El árbol B ordena las inserciones por desviación para lograr una asignación eficaz del espacio contiguo. Desafortunadamente, los árboles B de inserciones sufren la misma patología que los mapas de bits cuando deben enfrentarse a liberaciones aleatorias.¿Qué hacer entonces?Liberaciones diferidasUna forma de mitigar la patología de las liberaciones aleatorias consiste en aplazar la actualización de los mapas de bits o los árboles B, y mantener una lista de los bloques liberados recientemente. Cuando la lista alcanza un tamaño determinado, se puede ordenar, en memoria, y liberarse luego en los mapas de bits o árboles B subyacentes cuya ubicación sea algo mejor. No es ideal, pero ayuda.¿Y si llegamos más lejos?Mapas espaciales: listas de registros estructurados libresRecordemos que los sistemas de archivos con registros estructurados plantearon esta pregunta hace tiempo: ¿y si, en lugar de devolver periódicamente un registro de transacciones al sistema de archivos hacemos que el registro de transacciones sea el sistema de archivos?Bueno, esta misma pregunta podría aplicarse a nuestra lista de liberaciones diferidas: ¿y si en lugar de devolver la lista a un mapa de bits o un árbol B hacemos que la lista de liberaciones diferidas sea la representación del espacio libre?Esto es precisamente lo que hace ZFS, divide el espacio de cada dispositivo virtual en varios cientos de regiones llamadas metaslabs. Cada metaslab lleva asociado un mapa espacial en el que se describe el espacio libre que contiene. El mapa espacial no es sino un registro de asignaciones y espacios libres ordenados por tiempo, que libera espacio aleatoriamente con la misma eficacia que si lo hiciera de forma secuencial; la razón es que, sea cual sea la inserción que libera, la representa en el disco añadiendo la inserción (un par de enteros) al objeto de mapa espacial -- y estos añadidos son perfectamente localizables. De igual modo, las asignaciones se representan en el disco como inserciones añadidas al objeto de mapa espacial (por supuesto, con un conjunto de bits que las identifica como una asignación, no como espacio libre).Cuando ZFS decide asignar bloques a un determinado metaslab, primero lee el mapa espacial del metaslab en el disco y reproduce las asignaciones y los espacios libres en un árbol AVL de memoria con el espacio libre ordenado por el número de desviación. El resultado es una representación compacta del espacio libre que admite la asignacion eficaz de espacios contiguos. ZFS aprovecha también la ocasión para condensar el mapa espacial: si hay muchos pares de asignación libres para cancelar, ZFS sustituye el mapa espacial del disco por una versión más pequeña en memoria.Los mapas espaciales tienen algunas propiedades bastante curiosas:No es necesario inicializarlos: un mapa espacial sin entradas indica que no hay asignaciones ni espacios libres, por lo que todo es espacio libre.Son escalables: los mapas espaciales sólo añaden, y sólo el último bloque del objeto de mapa espacial necesita estar en memoria para poder garantizar un rendimiento excelente sin importar la cantidad de espacio que gestionen.No tienen patologías: los mapas espaciales son capaces de actualizar el espacio eficazmente al margen de cualquier patrón de asignaciones y liberaciones.Son igualmente eficaces en la localización de espacio libre, tanto si el lugar de almacenamiento está lleno como vacío (a diferencia de los mapas de bits que tardan más en escanear a medida que se va ocupando el espacio). Por último, señalar que cuando un mapa espacial se llena por completo aparece representado por una única inserción. Es decir, los mapas espaciales poseen la atractiva propiedad de que a medida que su capacidad de almacenamiento se aproxima al 100%, comienzan a evaporarse y permiten aprovechar hasta la última gota de espacio disponible.

Cada sistema de archivos debe registrar rigurosamenten dos cosas básicas: la ubicación de los datos y la ubicación del espacio libre.En principio, no parece estrictamente necesario saber dónde está...

ZFS

Mapas de espaço

Todo sistema de arquivos precisa controlar dois itens básicos: onde há dados e onde há espaço livre.Em princípio, controlar o espaço livre não é estritamente necessário: cada bloco está alocado ou livre, portanto, pode-se calcular o espaço livre pressupondo-se que tudo esteja livre e, depois, subtraindo-se tudo o que está alocado. Para saber o espaço alocado, percorra todo o sistema de arquivos desde a raiz. Qualquer bloco que não for encontrado nessa travessia desde a raiz estará, por definição, livre.Na prática, localizar espaço livre dessa forma seria intolerável porque seria uma operação extremamente demorada em qualquer sistema de arquivos de um certo tamanho. Para agilizar a alocação e a liberação de blocos, o sistema de arquivos precisa de um método eficiente que permita controlar o espaço livre. Nesta postagem, examinaremos os métodos mais comuns, os fatores que dificultam sua escalabilidade e a nova abordagem que desenvolvemos para o ZFS. BitmapsA maneira mais comum de representar o espaço livre é com um bitmap. Um bitmap é simplesmente uma matriz de bits, na qual o enésimo bit indica se o enésimo bloco está alocado ou livre. O overhead de um bitmap é bem baixo: 1 bit por bloco. Para um tamanho de bloco de 4K, isso significa 1/(4096\*8) = 0,003% (o 8 representa 8 bits por byte).Para um sistema de arquivos de 1 GB, o bitmap tem 32 KB, algo que cabe facilmente na memória e pode ser examinado rapidamente para encontrar espaço livre. Para um sistema de arquivos de 1 TB, o bitmap tem 32 MB, ainda ajustável na memória, porém não mais trivial em termos de tamanho ou de tempo de exame. Para um sistema de arquivos de 1 PB, o bitmap tem 32 GB e simplesmente não cabe na memória da maioria das máquinas. Isso significa que o exame do bitmap requer a sua leitura do disco, que é um processo ainda mais lento.Evidentemente, isso não é escalável.Uma solução aparentemente óbvia é dividir o bitmap em pequenas partes e controlar o número de bits definidos em cada parte. Por exemplo, para um sistema de arquivos de 1 PB com blocos de 4K, o espaço livre pode ser dividido em um milhão de bitmaps de 32 KB cada um. O resumo informativo (o milhão de inteiros que indicam quanto espaço existe em cada bitmap) cabe na memória e isso faz com que seja fácil localizar um bitmap com espaço livre e que seja rápido examinar esse bitmap.Mas ainda existe um problema fundamental: os bitmaps precisam ser atualizados não apenas quando um novo bloco for alocado, mas também quando um bloco antigo for liberado. O sistema de arquivos controla a localização das alocações (decide em quais blocos inserir novos dados), mas não tem controle sobre a localização das liberações. Algo tão simples como 'rm -rf' pode causar a liberação de blocos em todo o disco. Com nosso exemplo de sistema de arquivos de 1 PB, no pior caso, a remoção de 4 GB de dados (um milhão de blocos de 4K) poderia exigir a leitura, a modificação e a regravação de cada um dos um milhão de bitmaps. Isso representa dois milhões de entradas/saídas no disco para liberar míseros 4 GB, e isso simplesmente não é razoável, nem como comportamento de pior caso.Mais do que qualquer outro fator individual, este é o motivo pelo qual bitmaps não são escaláveis: as liberações são normalmente aleatórias e os bitmaps que não cabem na memória apresentam um desempenho patológico quando são acessados aleatoriamente.Árvores BUma outra maneira comum de representar o espaço livre é com uma árvore B de extensões. Uma extensão é uma região contígua de espaço livre descrita por dois inteiros: deslocamento e comprimento. A árvore B classifica as extensões por deslocamento, para obter uma alocação eficiente do espaço contíguo. Infelizmente, as árvores B de extensões sofrem da mesma patologia que os bitmaps quando confrontadas com liberações aleatórias.O que fazer?Liberações adiadasUma maneira de atenuar a patologia das liberações aleatórias consiste em adiar a atualização dos bitmaps ou das árvores B e, em vez disso, manter uma lista dos blocos liberados recentemente. Quando essa lista de liberações adiadas atingir um determinado tamanho, ela poderá ser classificada, na memória, e, depois, liberada para os bitmaps ou as árvores B subjacentes com uma localização um pouco melhor. Não é o ideal, mas ajuda.Mas e se formos mais adiante?Mapas de espaço: listas de liberações estruturadas em logLembre-se de que, há algum tempo, os sistemas de arquivos estruturados em log levantaram esta questão: e se, em vez de devolver um log de transações periodicamente ao sistema de arquivos, fizéssemos com que o log de transações fosse o sistema de arquivos?Bem, a mesma pergunta poderia ser feita com relação à nossa lista de liberações adiadas: e se, em vez de devolvê-la a um bitmap ou uma árvore B, fizéssemos com que a lista de liberações adiadas fosse a representação do espaço livre?Isso é precisamente o que o ZFS faz. Ele divide o espaço de cada dispositivo virtual em algumas centenas de regiões chamadas metaslabs. Cada metaslab tem um mapa de espaço associado, que descreve o espaço livre desse metaslab. O mapa de espaço é simplesmente um log de alocações e liberações, por ordem de tempo. Os mapas de espaço fazem liberações aleatórias e liberações seqüenciais com a mesma eficiência porque, independentemente da extensão que esteja sendo liberada, ela é representada no disco pela sua anexação (dois inteiros) ao objeto mapa de espaço, e as anexações têm uma localização perfeita. De maneira semelhante, as alocações são representadas no disco como extensões anexadas ao objeto mapa de espaço (com, obviamente, um conjunto de bits que as identifica como uma alocação, e não como espaço livre).Quando o ZFS decide alocar blocos de um metaslab específico, primeiro ele lê o mapa de espaço do metaslab no disco e reproduz as alocações e as liberações em uma árvore AVL de memória com o espaço livre classificado por deslocamento. Isso gera uma representação compacta, na memória, do espaço livre que aceita a alocação eficiente de espaço contíguo. O ZFS também aproveita a oportunidade para condensar o mapa de espaço: se houver muitos pares alocação-liberação que se neutralizam mutuamente, o ZFS substituirá o mapa de espaço no disco pela versão menor na memória.Os mapas de espaço apresentam várias propriedades interessantes:Não exigem inicialização: um mapa de espaço sem entradas indica que não houve alocações nem liberações, logo, todo o espaço está livre.São escaláveis: como os mapas de espaço são somente para anexação, apenas o último bloco do objeto mapa de espaço precisa estar na memória para assegurar um excelente desempenho, não importa quanto espaço seja gerenciado.Não apresentam patologias: os mapas de espaço podem ser atualizados com eficiência, independentemente do padrão de alocações e liberações.São igualmente eficientes para encontrar espaço livre quer o pool esteja vazio ou cheio (ao contrário dos bitmaps, que levam mais tempo para serem examinados à medida que ficam cheios). Por fim, observe que quando um mapa de espaço está completamente cheio, ele é representado por uma única extensão. Portanto, os mapas de espaço têm a fascinante propriedade de que, à medida que o pool de armazenamento se aproxima de sua capacidade máxima, eles começam a evaporar, disponibilizando, assim, até a última gota do espaço em disco para informações úteis.

Todo sistema de arquivos precisa controlar dois itens básicos: onde há dados e onde há espaço livre.Em princípio, controlar o espaço livre não é estritamente necessário: cada bloco está alocado ou...

ZFS

空间图

每个文件系统都必须跟踪两个基本的内容:数据的位置,空闲空间的位置。原则上,跟踪空闲空间不是严格必需的:每个块要么已分配,要么空闲,所以可以通过假设所有空间都空闲,然后减去已分配的空间就可以计算出空闲空间;已分配的空间可以通过从根遍历整个文件系统来找到。根据定义,不能通过从根遍历找到的任何块都是空闲的。实际上,按这种方式找空闲空间将是无法忍受的,因为它对于任何较大的文件系统来说花的时间太长了。要快速分配和释放块,文件系统需要有效的方式来跟踪空闲空间。在本文中,我们将检测最常用的方法,为什么它们没有很好扩展,以及我们为 ZFS 设计的新方法。位图最常见的表示空闲空间的方法是使用位图。位图位组成的数组,数组元素中的第 N 个位表示第 N 个块是已经分配还是空闲。位图的开销非常低:每个块对应 1 位。对于 4K 的块大小,是 1/(4096\*8) = 0.003%。(8 表示每位 8 个字节。)对于 1GB 的文件系统,位图是32KB,这很容易放入内存,而且可以快速扫描来找到空闲空间。对于 1TB 的文件系统,位图是 32MB,仍可装入内存,但在大小或扫描时间上就不那么小了。对于 1PB 的文件系统,位图是 32GB,大多数机器上都无法装入内存。这意味着扫描位图需要从磁盘中读取,仍然比较慢。很显然,这无法扩展。一个无缝的明显的对策是将位图分为小的组块,并跟踪每个组块中的位集数。例如,对于 1PB 文件系统(使用 4K 大小的块),空闲空间可以划分为 1 百万个位图,每个大小为 32KB。摘要信息(指明每个位图中有多少空间的百万整数)适合装入内存,所以很容易找到具有空闲空间的位图,并且能够快速浏览此位图。但还有一个基本的问题:不仅在分配新块时必须更新位图,而且在释放旧块时也必须更新位图。文件系统控制分配的位置(它决定要将新数据放入哪个块),但它无法控制空闲空间的位置。类似 rm -rf 的操作就可以导致整个磁盘片的块被释放。使用我们的 1PB 文件系统示例,在最坏的情况下,删除 4GB 的数据(1 百万个 4K 块)可能需要读取、修改并重新写出百万位图中的每一位。也就是说,要用 2 百万个磁盘 I/O 来释放少得可怜的 4GB,这岂止是不合理,这简直是最坏的行为。除了其他任何因素之外,位图无法扩展的主要原因是:释放通常是随机的,无法装入内存的位图在被随机访问时将异常执行。B 树另一种常见的表示空闲空间的方法是使用 B 树区间。一个区间是由两个整数(偏移量和长度)描述的一段连续的空闲空间区域。B 树按偏移量排序区间,因此连续空间分配是高效的。不幸的是,在面临随机释放时,B 树区间将出现与位图同样的问题。怎么办?延迟释放减轻随机释放问题的一种方法是延迟更新位图或 B 树,并保持一个最近释放的块列表。当延迟的释放列表达到一定大小时,可以在内存中对其进行排序,然后释放到位置好点的底层位图或 B 树中。不够理想,但也有用。但我们怎样才能做的更好?空间图:日志结构的释放列表回忆一下,日志结构的文件系统很久以前就提出了这个问题:如果不是定期将事务日志折叠回文件系统中,而是让事务日志成为文件系统会怎么样呢?好,可以对我们的延迟释放列表提出相同的问题:如果不是将其折叠回位图或 B 树中,而是让延迟释放列表成为空闲空间表示形式会怎么样呢?这正是 ZFS 要实现的内容。ZFS 将每个虚拟设备上的空间划分到几百个称为 metaslab 的区域中。每个 metaslab 具有一个关联的空间图,描述 metaslab 的空闲空间。空间图就是一个按时间顺序记录分配和释放的日志。空间图使得随机释放就像顺序释放一样高效,因为不管释放哪个区间,它在磁盘上都是通过将区间(一对整数)附加到空间图对象来表示的,而附加所表示的位置明确。同样地,分配在磁盘上表示为附加到空间图对象上的区间(当然,还有一个指明这是分配而非释放的位集)。当 ZFS 决定释放特定 metaslab 中的块时,它首先从磁盘中读取 metaslab 的位图,并将分配和释放按偏移量顺序重新放到空闲空间的内存 AVL 树中。这生成了对空闲空间的简洁内存表示,可以支持有效的连续空间分配。ZFS 还利用此机会来压缩空间图:如果有很多分配-释放对相互抵消,则 ZFS 将用更小的内存版本来替换磁盘空间图。空间图具有几个优秀的特性:它们不需要初始化:不带条目的空间图表示还没有任何分配和释放,所以所有空间是空闲的。它们可扩展:因为空间图只能附加,只有最后一块空间图对象需要位于内存中,以保证良好的性能,无论管理着多少空间都没有影响。它们没有问题:空间图在更新时是高效的,不管分配和释放使用哪种模式。它们在查找空闲空间时是相当高效的,不管池是空还是满(与位图不同,位图在满时将花费很长的时间来扫描)。 最后,注意当空间图完全用光时,它由单个区间来表示。因此,空间图有一个吸引人的特性:在存储池使用率接近 100% 时,空间图开始消失,这让每一点磁盘空间都可用于存放有用的信息。

每个文件系统都必须跟踪两个基本的内容:数据的位置,空闲空间的位置。 原则上,跟踪空闲空间不是严格必需的:每个块要么已分配,要么空闲,所以可以通过假设所有空间都空闲,然后减去已分配的空间就可以计算出空闲空间;已分配的空间可以通过从根遍历整个文件系统来找到。根据定义,不能通过从根遍历找到的任何块都是空闲的。实际上,按这种方式找空闲空间将是无法忍受的,因...

General

How to Lose a Customer

For over a year I have been the proud and happy owner of a Garmin GPS unit -- the Nuvi 360.  I have practically been a walking billboard for the company.  Go ahead, ask me about my Nuvi!That changed today, permanently.  When I powered on the Nuvi this morning, it alerted me that its map database was over a year old and should be updated.  That makes sense, I thought -- indeed, how nice of them to remind me!  So I brought the Nuvi inside, plugged it into my Mac, and went to Garmin's website to begin the update.Wait a minute, what's this?  They want to charge $69 for the update!  Excuse me?  This isn't new functionality I'm getting, it's a bug fix.  The product I bought is a mapping device.  Its maps are now "out of date", as Garmin puts it -- well, yes, in the same way that the phlogiston theory is "out of date".  The old maps are wrong, which means that the product has become defective and should be fixed.  Given the (somewhat pathetic) fact that the Nuvi doesn't automatically update its maps from Web or satellite sources, the least Garmin could do to keep their devices operating correctly in the field is provide regular, free fixes to the map database.  I didn't buy a GPS unit so I could forever navigate 2005 America.But wait, it gets better.You might imagine that getting the update would require supplying a credit card number to get a license key, downloading the map update, and then using the key to activate it.  Nope!  You have to order a physical DVD from Garmin, which takes 3-5 weeks to ship.  3-5 weeks!  Any reason they can't include a first-class postage stamp as part of the $69 shakedown?  And seriously, if you work for Garmin and you're reading this, check out this cool new technology.  It really works.  Swear to God.  You're soaking in it.Assuming you ordered the DVD, you would not discover until after it arrived -- because this is mentioned nowhere on Garmin's website -- that the DVD will only work for one device.  Yes, that's right -- after going to all the trouble to get a physical copy of the map update, you have to get on their website to activate it, and it's only good for one unit.  So to update my wife's unit as well as my own, I'd have to order two DVDs, for $138.  That's offensive.  Even the RIAA doesn't expect me to buy two copies of every CD just because I'm married.  And the only reason I know about this is because I checked Amazon first, and found many reviewers had learned the hard way and were livid about it.  Garmin's policy is bad, but their failure to disclose it is even worse.Moreover, the 2008 map update isn't a one-time purchase.  There's an update every year, so it's really a $138/year subscription.  That's $11.50/month.  For maps.  For a mapping device.  That I already paid for.What does one get for this $11.50/month map subscription?  According to the reviews on Amazon, not much.  Major construction projects that were completed several years ago aren't reflected in the 2008 maps, and Garmin still hasn't fixed the long-standing bug that any store that's part of a mall isn't in their database.  (Want to find the nearest McDonald's?  No dice.  You just have to know that the nearest McDonald's is in the XYZ Shopping Center, and ask for directions to that.  This is really annoying in practice.)I can get better information from Google maps, continuouslyupdated, with integrated real-time traffic data, for free, forever --and my iPhone will happily use that data to plot time-optimal routes. (In fact, all the iPhone needs is the right antenna and a SIRF-3chipset to make dedicated GPS devices instantly obsolete.  This is soobvious it can't be more than a year out.  I can live with the stale maps until then, and have a $138 down payment on the GPSiPhone earning interest while I wait.)And so, starting today, that's exactly what I'll do.I don't mind paying a reasonable fee for services rendered.  I do mindgetting locked into a closed-source platform and being forced to pay monopoly rentsfor a proprietary, stale and limited version of data that's already available to thegeneral public.  That business model is so over.Everything about this stinks, Garmin.  You tell me, unexpectedly, that I have to pay for routine map updates.  You make the price outrageous.  You don't actually disclose what's in the update.  (Several Amazon reviewers say the new maps are actually worse.)  You make the update hard to do.  You needlessly add to our landfills by creating single-use DVDs.  You have an unreasonable licensing policy.  And you hide that policy until after the purchase.Way to go, Garmin.  You have pissed off a formerly delighted customer, and that is generally a one-way ticket.  You have lost both my business and my respect.  I won't be coming back.  Ever.

For over a year I have been the proud and happy owner of a Garmin GPS unit -- the Nuvi 360.  I have practically been a walking billboard for the company.  Go ahead, ask me about my Nuvi!That changed...

ZFS

Space Maps

Every filesystem must keep track of two basic things: where your data is, and where the free space is.In principle, keeping track of free space is not strictly necessary: every block is either allocated or free, so the free space can be computed by assuming everything is free and then subtracting out everything that's allocated; and the allocated space can be found by traversing the entire filesystem from the root.  Any block that cannot be found by traversal from the root is, by definition, free.In practice, finding free space this way would be insufferable because it would take far too long for any filesystem of non-trivial size.  To make the allocation and freeing of blocks fast, the filesystem needs an efficient way to keep track of free space.  In this post we'll examine the most common methods, why they don't scale well, and the new approach we devisedfor ZFS. BitmapsThe most common way to represent free space is by using a bitmap.  A bitmap is simply an array of bits, with the Nth bit indicating whether the Nth block is allocated or free.  The overhead for a bitmap is quite low: 1 bit per block.  For a 4K blocksize, that's 1/(4096\*8) = 0.003%.  (The 8 comes from 8 bits per byte.)For a 1GB filesystem, the bitmap is 32KB -- something that easily fits in memory, and can be scanned quickly to find free space.  For a 1TB filesystem, the bitmap is 32MB -- still stuffable in memory, but no longer trivial in either size or scan time.  For a 1PB filesystem, the bitmap is 32GB, and that simply won't fit in memory on most machines.  This means that scanning the bitmap requires reading it from disk, which is slower still.Clearly, this doesn't scale.One seemingly obvious remedy is to break the bitmap into small chunks, and keep track of the number of bits set in each chunk.  For example, for a 1PB filesystem using 4K blocks, the free space can be divided into a million bitmaps, each 32KB in size.  The summary information (the million integers indicating how much space is in each bitmap) fits in memory, so it's easy to find a bitmap with free space, and it's quick to scan that bitmap.But there's still a fundamental problem: the bitmap(s) must be updated not only when a new block is allocated, but also when an old block is freed.  The filesystem controls the locality of allocations (it decides which blocks to put new data into), but it has no control over the locality of frees.  Something as simple as 'rm -rf' can cause blocks all over the platter to be freed.  With our 1PB filesystem example, in the worst case, removing 4GB of data (a million 4K blocks) could require each of the million bitmaps to be read, modified, and written out again.  That's two million disk I/Os to free a measly 4GB -- and that's just not reasonable, even as worst-case behavior.More than any other single factor, this is why bitmaps don't scale: because frees are often random, and bitmaps that don't fit in memory perform pathologically when they are accessed randomly.B-treesAnother common way to represent free space is with a B-tree of extents.  An extent is a contiguous region of free space described by two integers: offset and length.  The B-tree sorts the extents by offset so that contiguous space allocation is efficient.  Unfortunately, B-trees of extents suffer the same pathology as bitmaps when confronted with random frees.What to do?Deferred freesOne way to mitigate the pathology of random frees is to defer the update of the bitmaps or B-trees, and instead keep a list of recently freed blocks.  When this deferred free list reaches a certain size, it can be sorted, in memory, and then freed to the underlying bitmaps or B-trees with somewhat better locality.  Not ideal, but it helps.But what if we went further?Space maps:  log-structured free listsRecall that log-structured filesystems long ago posed this question: what if, instead of periodically folding a transaction log back into the filesystem, we made the transaction log be the filesystem?Well, the same question could be asked of our deferred free list: what if, instead of folding it into a bitmap or B-tree, we made the deferred free list be the free space representation?That is precisely what ZFS does.  ZFS divides the space on each virtual device into a few hundred regions called metaslabs.  Each metaslab has an associated space map, which describes that metaslab's free space.  The space map is simply a log of allocations and frees, in time order.  Space maps make random frees just as efficient as sequential frees, because regardless of which extent is being freed, it's represented on disk by appending the extent (a couple of integers) to the space map object -- and appends have perfect locality.  Allocations, similarly, are represented on disk as extents appended to the space map object (with, of course, a bit set indicating that it's an allocation, not a free).When ZFS decides to allocate blocks from a particular metaslab, it first reads that metaslab's space map from disk and replays the allocations and frees into an in-memory AVL tree of free space, sorted by offset.  This yields a compact in-memory representation of free space that supports efficient allocation of contiguous space.  ZFS also takes this opportunity to condense the space map: if there are many allocation-free pairs that cancel out, ZFS replaces the on-disk space map with the smaller in-memory version.Space maps have several nice properties:They don't require initialization: a space map with no entries indicates that there have been no allocations and no frees, so all space is free.They scale: because space maps are append-only, only the last block of the space map object needs to be in memory to ensure excellent performance, no matter how much space is being managed.They have no pathologies: space maps are efficient to update regardless of the pattern of allocations and frees.They are equally efficient at finding free space whether the pool is empty or full (unlike bitmaps, which take longer to scan as they fill up).Finally, note that when a space map is completely full, it is represented by a single extent.  Space maps therefore have the appealing property that as your storage pool approaches 100% full, the space maps start to evaporate, thus making every last drop of disk space available to hold useful information.

Every filesystem must keep track of two basic things: where your data is, and where the free space is.In principle, keeping track of free space is not strictly necessary: every block is either...

ZFS

Rampant Layering Violation?

Andrew Morton has famously called ZFS a "rampant layering violation" because it combines the functionality of a filesystem, volume manager, and RAID controller.  I suppose it depends what the meaning of the word violate is.  While designing ZFS we observed that the standard layering of the storage stack induces a surprising amount of unnecessary complexity and duplicated logic.  We found that by refactoring the problem a bit -- that is, changing where the boundaries are between layers -- we could make the whole thing much simpler.An example from mathematics (my actual background) provides a useful prologue.Suppose you had to compute the sum, from n=1 to infinity, of 1/n(n+1).Expanding that out term by term, we have:        1/(1\*2) + 1/(2\*3) + 1/(3\*4) + 1/(4\*5) + ...That is,        1/2 + 1/6 + 1/12 + 1/20 + ...What does that infinite series add up to?  It may seem like a hard problem, but that's only because we're not looking at it right.  If you're clever, you might notice that there's a different way to express each term:        1/n(n+1) = 1/n - 1/(n+1)For example,        1/(1\*2) = 1/1 - 1/2        1/(2\*3) = 1/2 - 1/3        1/(3\*4) = 1/3 - 1/4Thus, our sum can be expressed as:        (1/1 - 1/2) + (1/2 - 1/3) + (1/3 - 1/4) + (1/4 - 1/5) + ...Now, notice the pattern: each term that we subtract, we add back.  Only in Congress does that count as work.  So if we just rearrange the parentheses -- that is, if we rampantly violate the layering of the original problem by using associativity to refactor the arithmetic across adjacent terms of the series -- we get this:        1/1 + (-1/2 + 1/2) + (-1/3 + 1/3) + (-1/4 + 1/4) + ...or        1/1 + 0 + 0 + 0 + ...In others words,        1.Isn't that cool?Mathematicians have a term for this.  When you rearrange the terms of a series so that they cancel out, it's called telescoping -- by analogy with a collapsable hand-held telescope.  In a nutshell, that's what ZFS does: it telescopes the storage stack.  That's what allows us to have a filesystem, volume manager, single- and double-parity RAID, compression, snapshots, clones, and a ton of other useful stuff in just 80,000 lines of code.A storage system is more complex than this simple analogy, but at a high level the same idea really does apply.  You can think of any storage stack as a series of translations from one naming scheme to another -- ultimately translating a filename to a disk LBA (logical block address).  Typically it looks like this: filesystem(upper): filename to object (inode)        filesystem(lower): object to volume LBA        volume manager: volume LBA to array LBA        RAID controller: array LBA to disk LBAThis is the stack we're about to refactor.First, note that the traditional filesystem layer is too monolithic.  It would be better to separate the filename-to-object part (the upper half) from the object-to-volume-LBA part (the lower half) so that we could reuse the same lower-half code to support other kinds of storage, like objects and iSCSI targets, which don't have filenames.  These storage classes could then speak to the object layer directly.  This is more efficient than going through something like /dev/lofi, which makes a POSIX file look like a device.  But more importantly, it provides a powerful new programming model -- object storage -- without any additional code.Second, note that the volume LBA is completely useless. Adding a layer of indirection often adds flexibility, but not in this case: in effect we're translating from English to French to German when we could just as easily translate from English to German directly.  The intermediate French has no intrinsic value.  It's not visible to applications, it's not visible to the RAID array, and it doesn't provide any administrative function.  It's just overhead.So ZFS telescoped that entire layer away.  There are just three distinct layers in ZFS: the ZPL (ZFS POSIX Layer), which provides traditional POSIX filesystem semantics; the DMU (Data Management Unit), which provides a general-purpose transactional object store; and the SPA (Storage Pool Allocator), which provides virtual block allocation and data transformations (replication, compression, and soon encryption).  The overall ZFS translation stack looks like this:        ZPL: filename to object        DMU: object to DVA (data virtual address)        SPA: DVA to disk LBAThe DMU provides both file and block access to a common pool of physical storage.  File access goes through the ZPL, while block access is just a direct mapping to a single DMU object.  We're also developing new data access methods that use the DMU's transactional capabilities in more interesting ways -- more about that another day.The ZFS architecture eliminates an entire layer of translation -- and along with it, an entire class of metadata (volume LBAs).  It also eliminates the need for hardware RAID controllers.  At the same time, it provides a useful new interface -- object storage -- that was previously inaccessible because it was buried inside a monolithic filesystem.I certainly don't feel violated.  Do you?

Andrew Morton has famously called ZFS a "rampant layering violation" because it combines the functionality of a filesystem, volume manager, and RAID controller.  I suppose it depends what the meaning...

General

A Near-Death Experience

Evidently, my previous post was just a tad too cheerful for some folks' taste.  But I speak with the optimism of a man who has cheated death.  And ironically, Pete's reference to George Cameron had a lot to do with it.Several years ago, George and a few other Sun folks went off to form 3par, a new storage company.  They all had Solaris expertise, and understood its advantages, so they wanted to use it inside their box.  But we weren't open-source at the time, and our licensing terms really sucked.  Both of us -- George at 3par, and me at Sun -- tried for months to arrange something reasonable.  We failed.  So finally -- because Sun literally gave them no choice -- 3par went with Linux.I couldn't believe it.  A cool new company wanted to use our product, and instead of giving them a hand, we gave them the finger.For many of us, that was the tipping point.  If we had any reservations about open-sourcing Solaris, that ended them.  It was a gamble, to be sure, but the alternative was certain death.  Even if the 3par situation had ended differently, it was clear that we needed to change our business practices.  To do that, we'd first have to change our culture.But cultures don't change easily -- it usually takes some traumatic event.  In Sun's case, watching our stock shed 95% of its value did the trick.  It was that total collapse of confidence -- that near-death experience -- that opened us up to things that had previously seemed too dangerous.  We had to face a number of hard questions, including the most fundamental ones: Can we make a viable business out of this wreckage?  Why are we doing SPARC?  Why not AMD and Intel?  Why Solaris?  Why not Linux and Windows?  Where are we going with Java?  And not rah-rah why, but really, why?In each case, asking the question with a truly open mind changed the answer.  We killed our more-of-the-same SPARC roadmap and went multi-core, multi-thread, and low-power instead.  We started building AMD and Intel systems.  We launched a wave of innovation in Solaris (DTrace, ZFS, zones, FMA, SMF, FireEngine, CrossBow) and open-sourced all of it.  We started supporting Linux and Windows.  And most recently, we open-sourced Java.  In short, we changed just about everything.  Including, over time, the culture.Still, there was no guarantee that open-sourcing Solaris would change anything.  It's that same nagging fear you have the first time you throw a party: what if nobody comes?  But in fact, it changed everything: the level of interest, the rate of adoption, the pace of communication.  Most significantly, it changed the way we do development.  It's not just the code that's open, but the entire development process.  And that, in turn, is attracting developers and ISVs whom we couldn't even have spoken to a few years ago.  The openness permits us to have the conversation; the technology makes the conversation interesting.After coming so close to augering into the ground, it's immensely gratifying to see the Solaris revival now underway.  So if I sometimes sound a bit like the proud papa going on and on about his son, well, I hope you can forgive me.Oh, and Pete, if you're reading this -- George Cameron is back at Sun now, three doors down the hall from me.  Small valley!

Evidently, my previous post was just a tad too cheerful for some folks'taste.  But I speak with the optimism of a man who has cheated death.  And ironically, Pete's reference to George Cameron had a...

General

Solaris Inside

When you choose an OS for your laptop, many things affect your decision: application support, availability of drivers, ease of use, and so on.But if you were developing a storage appliance, what would you want from the operating system that runs inside it?The first thing you notice is all the things you don't care about: graphics cards, educational software, photoshop... none of it matters. What's left, then?  What do you really need from a storage OS? And why isn't Linux the answer?  Well, let's think about that.You need something rock-solid, so it doesn't break or corrupt data.You need something that scales, so you can take advantage of all those cores the microprocessor folks will be giving you.You need really good tools for performance analysis, so you can figure out how to make your application scale as well as the OS does.You need extensive hardware diagnostic support, so that when parts of the box fail or are about to fail, you can take appropriate action.You need reliable crash dumps and first-rate debugging tools so you can perform first-fault diagnosis when something goes wrong.And you need a community of equally serious developers who can help you out.OpenSolaris gives you all of these: a robust kernel that scales to thousands of threads and spindles; DTrace, the best performance analysis tool on the planet; FMA (Fault Management Architecture) to monitor the hardware and predict and manage failures; mdb to analyze software problems; and of course the OpenSolaris community, a large, vibrant, professional, high signal-to-noise environment.The other operating systems one might consider are so far behind on so many of these metrics, it just seems like a no-brainer.Let's put it this way: if I ever leave Sun to do a storage startup, I'll have a lot of things to think about.  Choosing the OS won't be one of them.  OpenSolaris is the ideal storage development platform.

When you choose an OS for your laptop, many things affect your decision: application support, availability of drivers, ease of use, and so on.But if you were developing a storage appliance, what would...

General

The General-Purpose Storage Revolution

It happened so slowly, most people didn't notice until it was over.I'm speaking, of course, of the rise of general-purpose computing during the 1990s.  It was not so long ago that you could choose from a truly bewildering variety of machines.  Symbolics, for example, made hardware specifically designed to run Lisp programs.  We debated SIMD vs. MIMD, dataflow vs. control flow, VLIW, and so on.  Meanwhile, those boring little PCs just kept getting faster.  And more capable.  And cheaper.  By the end of the decade, even the largest supercomputers were just clusters of PCs. A simple, general-purpose computing device crushed all manner of clever, sophisticated, highly specialized systems.And the thing is, it had nothing to do with technology. It was all about volume economics.  It was inevitable.With that in mind, I bring news that is very good for you, very good for Sun, and not so good for our competitors:  the same thing that happened to compute in the 1990s is happening to storage, right now. Now, as then, the fundamental driver is volume economics, and we see it playing out at all levels of the stack: the hardware, the operating system, and the interconnect.First, custom RAID hardware can't keep up with general-purpose CPUs. A single Opteron core can XOR data at about 6 GB/sec.  There's just no reason to dedicate special silicon to this anymore.  It's expensive, it wastes power, and it was always a compromise: array-based RAID can't provide the same end-to-end data integrity that host-based RAID can. No matter how good the array is, a flaky cable or FC port can still flip bits in transit.  A host-based RAID solution like RAID-Z in ZFS can both detect and correct silent data corruption, no matter where it arises.Second, custom kernels can't keep up with volume operating systems. I try to avoid naming specific competitors in this blog -- it seems tacky -- but think about what's inside your favorite storage box. Is it open source?  Does it have an open developer community? Does it scale?  Can the vendor make it scale?  Do they even get a vote?The latter question is becoming much more important due to trends in CPU design.  The clock rate party of the 1990s, during which we went from 20MHz to 2GHz -- a factor of 100 -- is over.  Seven years into the new decade we're not even 2x faster in clock rate, and there's no sign of that changing soon.  What we are getting, however, is more transistors.  We're using them to put multiple cores on each chip and multiple threads on each core (so the chip can do something useful during load stalls) -- and this trend will only accelerate.Which brings us back to the operating system inside your storage device. Does it have any prayer of making good use of a 16-core, 64-thread CPU?Third, custom interconnects can't keep up with Ethernet.  In the time that Fibre Channel went from 1Gb to 4Gb -- a factor of 4 -- Ethernet went from 10Mb to 10Gb -- a factor of 1000.  That SAN is just slowing you down.Today's world of array products running custom firmware on custom RAID controllers on a Fibre Channel SAN is in for massive disruption. It will be replaced by intelligent storage servers, built from commodity hardware, running an open operating system, speaking over the real network.You've already seen the first instance of this: Thumper (the x4500) is a 4-CPU, 48-disk storage system with no hardware RAID controller. The storage is all managed by ZFS on Solaris, and exported directly to your real network over standard protocols like NFS and iSCSI.And if you think Thumper was disruptive, well... stay tuned.

It happened so slowly, most people didn't notice until it was over.I'm speaking, of course, of the rise of general-purpose computing during the 1990s.  It was not so long ago that you could choose...

ZFS

ZFS Block Allocation

Block allocation is central to any filesystem.  It affects not only performance, but also the administrative model (e.g. stripe configuration) and even some core capabilities like transactional semantics, compression, and block sharing between snapshots.  So it's important to get it right.There are three components to the block allocation policy in ZFS:Device selection (dynamic striping)Metaslab selectionBlock selectionBy design, these three policies are independent and pluggable.  They can be changed at will without altering the on-disk format, which gives us lots of flexibility in the years ahead.So... let's go allocate a block!1.  Device selection (aka dynamic striping).  Our first task is device selection.  The goal is to spread the load across all devices in the pool so that we get maximum bandwidth without needing any notion of stripe groups.  You add more disks, you get more bandwidth.  We call this dynamic striping -- the point being that it's done on the fly by the filesystem, rather than at configuration time by the administrator.There are many ways to select a device.  Any policy would work, including just picking one at random.  But there are several practical considerations:If a device was recently added to the pool, it'll be relatively empty.  To address such imbalances, we bias the allocation slightly in favor of underutilized devices.  This keeps space usage uniform across all devices.All else being equal, round-robin is a fine policy, but it's critical to get the granularity right.  If the granularity is too coarse (e.g. 1GB), we'll only get one device worth of bandwidth when doing sequential reads and writes.  If the granularity is too fine (e.g. one block), we'll waste any read buffering the device can do for us.  In practice, we've found that switching from one device to the next every 512K works well for the current generation of disk drives.That said, for intent log blocks, it's better to round-robin between devices each time we write a log block.  That's because they're very short-lived, so we don't expect to ever need to read them; therefore it's better to optimize for maximum IOPs when writing log blocks.  Neil Perrin integrated support for this earlier today.More generally, we'll probably want different striping policies for different types of data: large/sequential, small/random, transient (like the intent log), and dnodes (clumping for spatial density might be good).  This is fertile ground for investigation.If one of the devices is slow or degraded for some reason, it should be avoided.  This is work in progress.2. Metaslab selection.  We divide each device into a few hundred regions, called metaslabs, because the overall scheme was inspired by the slab allocator. Having selected a device, which metaslab should we use?  Intuitively it seems that we'd always want the one with the most free space, but there are other factors to consider:Modern disks have uniform bit density and constant angular velocity.  Therefore, the outer recording zones are faster (higher bandwidth) than the inner zones by the ratio of outer to inner track diameter, which is typically around 2:1.  We account for this by assigning a higher weight to the free space in lower-LBA metaslabs.  In effect, this means that we'll select the metaslab with the most free bandwidth rather than simply the one with the most free space.When a pool is relatively empty, we want to keep allocations in the outer (faster) regions of the disk; this improves both bandwidth and latency (by minimizing seek distances).  Therefore, we assign a higher weight to metaslabs that have been used before.All of these considerations can be seen in the function metaslab_weight().  Having defined a weighting scheme, the selection algorithm is simple:  always select the metaslab with the highest weight.3. Block selection.  Having selected a metaslab, we must choose a block within that metaslab.  The current allocation policy is a simple variation on first-fit; it  seems likely that we can do better.  In the future I expect that we'll  have not only a better algorithm, but a whole collection of algorithms, each optimized for a specific workload.  Anticipating this, the block allocation code is fully vectorized; see space_map_ops_t for details.The mechanism (as opposed to policy) for keeping track of free space in a metaslab is a new data structure called a space map, which I'll describe in the next post.

Block allocation is central to any filesystem.  It affects not only performance, but also the administrative model (e.g. stripe configuration) and even some core capabilities like transactional...

ZFS

You say zeta, I say zetta

On a lighter note, what is the Z in ZFS?I've seen the (non-)word 'zetabyte' many times in the press. It's also been noted that zeta is the last letter of the Greek alphabet, which will no doubt surprise many Greeks.So, here's the real story. When I began the (nameless) project, it needed a name. I had no idea what to call it. I knew that the Big Idea was to bring virtual memory concepts to disks, so things like VSS (Virtual Storage System) came to mind. The problem is, everything I came up with sounded like vapor. I don't know about you, but when I hear "Tiered Web Deployment Virtualization Engine" I assume it's either a vast steaming pile of complexity or a big fluffy cloud of nothing -- which is correct north of 98% of the time. So I didn't want a name that screamed "BS!" out of the gate. That actually ruled out a lot of stuff.At first I was hesitant to pick a name that ended in FS, because that would pigeon-hole the project in a way that's not quite accurate. It's much more than a filesystem, but then again, it is partly a filesystem, and at least people know what that is. It's a real thing. It's not a Tiered Web Deployment Virtualization Engine. I figured it would be better to correct any initial misimpression than to make no impression at all.So the hunt was on for something-FS. The first thing I did was to Google all 26 three-letter options, from AFS to ZFS. As it turns out, they've all been used by current or previous products, often many times over. But ZFS hadn't been used much, and certainly not by anything mainstream like (for example) AFS, DFS, NFS or UFS.I should mention that I ruled out BFS or BonwickFS, because it implies either sole authorship or a failure to share credit. Neither would be good.So in the end, I picked ZFS for the simplest of reasons: it sounds cool. It doesn't come with any baggage, like YFS (Why FS? Ha ha!). And you can even say it in hex (2f5).The next task was to retrofit the acronym -- that is, I had to come up with something for the Z to stand for. I actually got out my trusty old 1980 Random House Unabridged and looked through the entire Z section, and found nothing that spoke to me. Zero had a certain appeal (as in zero administrative hassle), but then again -- eh.OK, what does the web have to say? I don't recall exactly how I stumbled on the zetta prefix, but it seemed ideal: ZFS was to be a 128-bit filesystem, and the next unit after exabyte (the 64-bit limit is 16EB) is zettabyte. Perfect: the zettabyte filesystem.A bit of trivia (in case the rest of this post isn't quite trivial enough for you): the prefix 'zetta' is not of Greek or Latin origin --at least, not directly. The original SI prefixes were as follows:millikilo(1000\^1)micromega(1000\^2)nanogiga(1000\^3)picotera(1000\^4)femtopeta(1000\^5)attoexa(1000\^6)The demand for more extreme units actually began at the small end,so the SI people needed names for 1000\^-7 and 1000\^-8. For seven,they took the Latin "sept" and made "zepto" (septo wouldn't workbecause s for second is ubiquitous); for eight, they took the Greek"okto" and made "yocto" (octo wouldn't work because o looks like 0).For symmetry with zepto and yocto on the small side, they definedzetta and yotta on the big side. (I also suspect they were drinking heavily,and thought yotta was a real hoot.)But zettabyte wasn't perfect, actually. We (we were a team by now) found that when you call it the zettabyte filesystem, you have to explain what a zettabyte is, and by then the elevator has reached the top floor and all people know is that you're doing large capacity. Which is true, but it's not the main point.So we finally decided to unpimp the name back to ZFS, which doesn't stand for anything. It's just a pseudo-acronym that vaguely suggests a way to store files that gets you a lot of points in Scrabble.And it is, of course, "the last word in filesystems".

On a lighter note, what is the Z in ZFS? I've seen the (non-)word 'zetabyte' many times in the press. It's also been noted that zeta is the last letter of the Greek alphabet, which will no doubt...

ZFS

Smokin' Mirrors

Resilvering -- also known as resyncing, rebuilding, or reconstructing --is the process of repairing a damaged device using the contents of healthy devices.This is what every volume manager or RAID array must do when one of itsdisks dies, gets replaced, or suffers a transient outage.For a mirror, resilvering can be as simple as a whole-disk copy.For RAID-5 it's only slightly more complicated: instead of copying onedisk to another, all of the other disks in the RAID-5 stripe must beXORed together. But the basic idea is the same.In a traditional storage system, resilvering happens either in thevolume manager or in RAID hardware. Either way, it happens well belowthe filesystem.But this is ZFS, so of course we just had to be different.In a previous post I mentioned thatRAID-Zresilvering requires a different approach, because it needs thefilesystem metadata to determine the RAID-Z geometry. In effect, ZFSdoes a 'cp -r' of the storage pool's block tree from one disk to another.It sounds less efficient than a straight whole-disk copy, and traversinga live pool safely is definitely tricky (more on that in a future post).But it turns out that there are so many advantages to metadata-drivenresilvering that we've chosen to use it even for simple mirrors.The most compelling reason is data integrity. With a simple disk copy,there's no way to know whether the source disk is returning good data.End-to-end data integrityrequires that each data block be verifiedagainst an independent checksum -- it's not enough to know that eachblock is merely consistent with itself, because that doesn't catch commonhardware and firmware bugs like misdirected reads and phantom writes.By traversing the metadata, ZFS can use its end-to-end checksums to detectand correct silent data corruption, just like it does during normal reads.If a disk returns bad data transiently, ZFS will detect it and retry the read.If it's a 3-way mirror and one of the two presumed-good disks is damaged,ZFS will use the checksum to determine which one is correct, copy the datato the new disk, and repair the damaged disk.A simple whole-disk copy would bypass all of this data protection.For this reason alone, metadata-driven resilvering would be desirableeven it it came at a significant cost in performance.Fortunately, in most cases, it doesn't. In fact, there are severaladvantages to metadata-driven resilvering:Live blocks only.ZFS doesn't waste time and I/O bandwidth copying free disk blocksbecause they're not part of the storage pool's block tree.If your pool is only 10-20% full, that's a big win.Transactional pruning. If a disk suffers a transient outage,it's not necessary to resilver the entire disk -- only the parts thathave changed. I'll describe this in more detail in a future post,but in short: ZFS uses the birth time of each block to determinewhether there's anything lower in the tree that needs resilvering.This allows it to skip over huge branches of the tree and quicklydiscover the data that has actually changed since the outage began.What this means in practice is that if a disk has a five-secondoutage, it will only take about five seconds to resilver it.And you don't pay extra for it -- in either dollars or performance --like you do with Veritas change objects. Transactional pruningis an intrinsic architectural capability of ZFS.Top-down resilvering. A storage pool is a tree of blocks.The higher up the tree you go, the more disastrous it is to lose ablock there, because you lose access to everything beneath it.Going through the metadata allows ZFS to do top-down resilvering.That is, the very first thing ZFS resilvers is the uberblock and thedisk labels. Then it resilvers the pool-wide metadata; then eachfilesystem's metadata; and so on down the tree. Throughout the processZFS obeys this rule: no block is resilvered until all of its ancestorshave been resilvered.It's hard to overstate how important this is. With a whole-disk copy,even when it's 99% done there's a good chance that one of the top 100blocks in the tree hasn't been copied yet. This means that from anMTTR perspective, you haven't actually made any progress: a seconddisk failure at this point would still be catastrophic.With top-down resilvering, every single block copied increasesthe amount of discoverable data. If you had a second disk failure,everything that had been resilvered up to that point would be available.Priority-based resilvering. ZFS doesn't do this one yet, butit's in the pipeline. ZFS resilvering follows the logical structureof the data, so it would be pretty easy to tag individual filesystemsor files with a specific resilver priority. For example, on a fileserver you might want to resilver calendars first (they're importantyet very small), then /var/mail, then home directories, and so on.What I hope to convey with each of these posts is not just the mechanicsof how a particular feature is implemented, but to illustrate how all theparts of ZFS form an integrated whole. It's not immediately obvious,for example, that transactional semantics would have anything to do withresilvering -- yet transactional pruning makes recovery from transientoutages literally orders of magnitude faster. More on how thatworks in the next post.

Resilvering -- also known as resyncing, rebuilding, or reconstructing -- is the process of repairing a damaged device using the contents of healthy devices.This is what every volume manager or RAID...

ZFS

SEEK_HOLE and SEEK_DATA for sparse files

A sparse file is a file that contains much less data than itssize would suggest. If you create a new file and thendo a 1-byte write to thebillionth byte, for example, you've just created a 1GB sparse file.By convention, reads from unwritten parts of a file return zeroes.File-based backup and archiving programs like tar, cpio, and rsynccan detect runs of zeroes and ignore them, so that the archives theyproduce aren't filled with zeroes. Still, this is terribly inefficient.If you're a backup program, what you really want is a list of thenon-zero segments in the file. But historically there's been no wayto get this information without looking at filesystem-specific metadata.Desperately seeking segmentsAs part of the ZFS project, we introduced two general extensions tolseek(2): SEEK_HOLE and SEEK_DATA. These allow you to quickly discoverthe non-zero regions of sparse files. Quoting from the new man page: o If whence is SEEK_HOLE, the offset of the start of the next hole greater than or equal to the supplied offset is returned. The definition of a hole is provided near the end of the DESCRIPTION. o If whence is SEEK_DATA, the file pointer is set to the start of the next non-hole file region greater than or equal to the supplied offset. [...] A "hole" is defined as a contiguous range of bytes in a file, all having the value of zero, but not all zeros in a file are guaranteed to be represented as holes returned with SEEK_HOLE. Filesystems are allowed to expose ranges of zeros with SEEK_HOLE, but not required to. Applications can use SEEK_HOLE to optimise their behavior for ranges of zeros, but must not depend on it to find all such ranges in a file. The existence of a hole at the end of every data region allows for easy programming and implies that a virtual hole exists at the end of the file. Applications should use fpathconf(_PC_MIN_HOLE_SIZE) or pathconf(_PC_MIN_HOLE_SIZE) to determine if a filesystem supports SEEK_HOLE. See fpath- conf(2). For filesystems that do not supply information about holes, the file will be represented as one entire data region.Any filesystem can support SEEK_HOLE / SEEK_DATA. Even a filesystemlike UFS, which has no special support for sparseness, can walk itsblock pointers much faster than it can copy out a bunch of zeroes.Even if the search algorithm is linear-time, at least the constantis thousands of times smaller.Sparse file navigation in ZFSA file in ZFS is a tree of blocks. To maximize the performance ofSEEK_HOLE and SEEK_DATA, ZFS maintains in each block pointer afill count indicating the number of data blocks beneath itin the tree (see below). Fill counts reveal where holes and datareside, so that ZFS can find both holes and data in guaranteedlogarithmic time. L4 6 ----------------------------------- L3 5 0 1 ----------- ----------- ----------- L2 3 0 2 0 0 1 --- --- --- --- --- --- L1 111 101 001An indirect block tree for a sparse file, showing the fill count ineach block pointer. In this example there are three block pointersper indirect block. The lowest-level (L1) block pointers describeeither one block of data or one block-sized hole, indicated by afill count of 1 or 0, respectively. At L2 and above, each blockpointer's fill count is the sum of the fill counts of its children.At any level, a non-zero fill count indicates that there's data below.A fill count less than the maximum (3L-1 in this example)indicates that there are holes below. From any offset in the file,ZFS can find the next hole or next data in logarithmic time by followingthe fill counts in the indirect block tree.PortabilityAt this writing, SEEK_HOLE and SEEK_DATA are Solaris-specific.I encourage (implore? beg?) other operating systems to adoptthese lseek(2) extensions verbatim (100% tax-free)so that sparse file navigation becomes a ubiquitousfeature that every backup and archiving program can rely on.It's long overdue.Technorati Tags:OpenSolarisSolarisZFS

A sparse file is a file that contains much less data than its size would suggest. If you create a new file and then do a 1-byte write to thebillionth byte, for example, you've just created a 1GB...

ZFS

ZFS End-to-End Data Integrity

The job of any filesystem boils down to this: when asked to read a block,it should return the same data that was previously written to that block.If it can't do that -- because the disk is offline or the data has beendamaged or tampered with -- it should detect this and return an error.Incredibly, most filesystems fail this test. They depend onthe underlying hardware to detect and report errors. If a disksimply returns bad data, the average filesystem won't even detect it.Even if we could assume that all disks were perfect, the data would stillbe vulnerable to damage in transit: controller bugs, DMA parity errors,and so on. All you'd really know is that the data was intact when itleft the platter. If you think of your data as a package, this wouldbe like UPS saying, "We guarantee that your package wasn't damagedwhen we picked it up." Not quite the guarantee you were looking for.In-flight damage is not a mere academic concern: even something as mundane as abad power supplycan cause silent data corruption.Arbitrarily expensive storage arrays can't solve the problem. The I/O pathremains just as vulnerable, but becomes even longer: after leaving the platter,the data has to survive whatever hardware and firmware bugs the arrayhas to offer.And if you're on a SAN, you're using a network designed by disk firmwarewriters. God help you.What to do? One option is to store a checksum with every disk block.Most modern disk drives can be formatted with sectors that are slightlylarger than the usual 512 bytes -- typically 520 or 528. These extrabytes can be used to hold a block checksum. But making good use of thischecksum is harder than it sounds: the effectiveness of a checksumdepends tremendously on where it's stored and when it's evaluated.In many storage arrays (see theDell|EMC PowerVault paperfor a typical example with an excellent description of the issues),the data is compared to its checksum inside the array.Unfortunately this doesn't help much. It doesn't detect common firmwarebugs such as phantom writes (the previous write never made it to disk) becausethe data and checksum are stored as a unit -- so they're self-consistenteven when the disk returns stale data.And the rest of the I/O path from the array to the host remains unprotected.In short, this type of block checksum provides a good way to ensure thatan array product is not any less reliable than the disks it contains,but that's about all.NetApp's block-appended checksum approach appears similar but is in factmuch stronger. Like many arrays, NetApp formats its drives with 520-bytesectors. It then groups them into 8-sector blocks: 4K of data (the WAFLfilesystem blocksize) and 64 bytes of checksum. When WAFL reads a blockit compares the checksum to the data just like an array would,but there's a key difference: it does this comparison afterthe data has made it through the I/O path, so it validates that theblock made the journey from platter to memory without damage in transit.This is a major improvement, but it's still not enough. A block-levelchecksum only proves that a block is self-consistent; it doesn't provethat it's the right block. Reprising our UPS analogy,"We guarantee that the package you received is not damaged.We do not guarantee that it's your package."The fundamental problem with all of these schemes is that they don'tprovide fault isolationbetween the data and the checksum that protects it.ZFS Data AuthenticationEnd-to-end data integrity requires that each data block be verifiedagainst an independent checksum, after the data has arrivedin the host's memory. It's not enough to know that each block is merelyconsistent with itself, or that it was correct at some earlier pointin the I/O path. Our goal is to detect every possible form of damage,including human mistakes like swapping on a filesystem disk or mistypingthe arguments to dd(1). (Have you ever typed "of=" when you meant "if="?)A ZFS storage pool is really just a tree of blocks.ZFS provides fault isolation between data and checksum by storing thechecksum of each block in its parent block pointer -- not in the blockitself. Everyblock in the tree contains the checksums for all its children,so the entire pool is self-validating. [The uberblock (the root of thetree) is a special case because it has no parent; more on how we handlethat in another post.]When the data and checksum disagree, ZFS knows that the checksum can betrusted because the checksum itself is part of some other block that'sone level higher in the tree, and that block has already been validated.ZFS uses its end-to-end checksums to detect and correct silent datacorruption. If a diskreturns bad data transiently, ZFS will detect it and retry the read.If the disk is part of a mirror orRAID-Zgroup, ZFS will both detect and correct the error: it will use the checksumto determine which copy is correct, provide good data to the application,and repair the damaged copy.As always, note that ZFS end-to-end data integrity doesn't requireany special hardware.You don't need pricey disks or arrays,you don't need to reformat drives with 520-byte sectors, and you don't have tomodify applicationsto benefit from it. It's entirely automatic, and it works with cheap disks.But wait, there's more!The blocks of a ZFS storage pool form aMerkle tree in whicheach block validates all of its children. Merkle trees have been provento provide cryptographically-strong authentication for any component ofthe tree, and for the tree as a whole.ZFS employs 256-bit checksums for every block,and offers checksum functions ranging from the simple-and-fastfletcher2 (the default) to the slower-but-secureSHA-256.When using a cryptographic hash like SHA-256, the uberblock checksum providesa constantly up-to-date digital signature for the entire storage pool.Which comes in handy if you ask UPS to move it.Technorati Tags:OpenSolarisSolarisZFS

The job of any filesystem boils down to this: when asked to read a block, it should return the same data that was previously written to that block.If it can't do that -- because the disk is offline or...

ZFS

RAID-Z

The original promise of RAID (Redundant Arrays of Inexpensive Disks)was that it would provide fast, reliable storage using cheap disks.The key point was cheap; yet somehow we ended uphere. Why?RAID-5 (and other data/parity schemes such as RAID-4, RAID-6, even-odd,and Row Diagonal Parity) never quite delivered on the RAID promise -- and can't --due to a fatal flaw known as the RAID-5 write hole. Whenever you update thedata in a RAID stripe you must also update the parity, so that all disks XORto zero -- it's that equation that allows you to reconstruct data when adisk fails. The problem is that there's no way to update two or more disksatomically, so RAID stripes can become damaged during a crash or power outage.To see this, suppose you lose power after writing a data block but beforewriting the corresponding parity block. Now the data and parity for thatstripe are inconsistent, and they'll remain inconsistent forever (unlessyou happen to overwrite the old data with a full-stripe write at some point).Therefore, if a disk fails, the RAID reconstruction process will generategarbage the next time you read any block on that stripe. What's worse,it will do so silently -- it has no idea that it's giving you corrupt data.There are software-only workarounds for this, but they're so slow thatsoftware RAID has died in the marketplace. Current RAID products all dothe RAID logic in hardware, where they can use NVRAM to survive power loss.This works, but it's expensive.There's also a nasty performance problem with existing RAID schemes.When you do a partial-stripe write -- that is, when you update less datathan a single RAID stripe contains -- the RAID system must read the old dataand parity in order to compute the new parity. That's a huge performance hit.Where a full-stripe write can simply issue all the writes asynchronously,a partial-stripe write must do synchronous reads before it can even startthe writes.Once again, expensive hardware offers a solution: a RAID arraycan buffer partial-stripe writes in NVRAM while it's waiting for thedisk reads to complete, so the read latency is hidden from the user.Of course, this only works until the NVRAM buffer fills up. No problem,your storage vendor says! Just shell out even more cash for more NVRAM.There's no problem your wallet can't solve.Partial-stripe writes pose an additional problem for a transactionalfilesystem like ZFS. A partial-stripe write necessarily modifies live data,which violates one of the rules that ensures transactional semantics. (It doesn't matter if you lose power during a full-stripewrite for the same reason that it doesn't matter if you lose power duringany other write in ZFS: none of the blocks you're writing to are live yet.)If only we didn't have to do those evil partial-stripe writes...Enter RAID-Z.RAID-Z is a data/parity scheme like RAID-5, but it uses dynamic stripe width.Every block is its own RAID-Z stripe, regardless of blocksize. This meansthat every RAID-Z write is a full-stripe write. This, when combined with thecopy-on-write transactional semantics of ZFS, completely eliminates theRAID write hole. RAID-Z is also faster than traditional RAID because it never has to doread-modify-write.Whoa, whoa, whoa -- that's it? Variable stripe width? Geez, that seemspretty obvious. If it's such a good idea, why doesn't everybody do it?Well, the tricky bit here is RAID-Z reconstruction. Because the stripesare all different sizes, there's no simple formula like "all the disksXOR to zero." You have to traverse the filesystem metadata to determinethe RAID-Z geometry. Note that this would be impossible if the filesystemand the RAID array were separate products, which is why there's nothinglike RAID-Z in the storage market today. You really need an integratedview of the logical and physical structure of the data to pull it off.But wait, you say: isn't that slow? Isn't it expensive to traverseall the metadata? Actually, it's a trade-off. If your storage poolis very close to full, then yes, it's slower. But if it's not tooclose to full, then metadata-driven reconstruction is actually fasterbecause it only copies live data; it doesn't waste time copyingunallocated disk space.But far more important, going through the metadata means that ZFScan validate every block against its 256-bit checksum as it goes.Traditional RAID products can't do this; they simply XOR the datatogether blindly.Which brings us to the coolest thing about RAID-Z: self-healing data.In addition to handling whole-disk failure, RAID-Z can also detectand correct silent data corruption. Whenever you read a RAID-Z block,ZFS compares it against its checksum. If the data disks didn't returnthe right answer, ZFS reads the parity and then does combinatorialreconstruction to figure out which disk returned bad data. It thenrepairs the damaged disk and returns good data to the application.ZFS also reports the incident through Solaris FMA so that the systemadministrator knows that one of the disks is silently failing.Finally, note that RAID-Z doesn't require any special hardware.It doesn't need NVRAM for correctness, and it doesn't need write bufferingfor good performance. With RAID-Z, ZFS makes good on the original RAIDpromise: it provides fast, reliable storage using cheap, commodity disks.For a real-world example of RAID-Z detecting and correcting silentdata corruption on flaky hardware, check outEric Lowe's SATA saga.The current RAID-Z algorithm is single-parity, but the RAID-Z conceptworks for any RAID flavor. A double-parity version is in the works.One last thing that fellow programmers will appreciate: the entireRAID-Z implementationis just 599 lines.Technorati Tags:OpenSolarisSolarisZFS

The original promise of RAID (Redundant Arrays of Inexpensive Disks) was that it would provide fast, reliable storage using cheap disks. The key point was cheap; yet somehow we ended uphere. Why? RAID-5...

ZFS

Thank You

I was originally planning to blog about RAID-Z today, but I can't.There's been such a tremendous outpouring of energy and passion for theZFS launch today that the only thing I can think about is this: thank you.Eric SchrockandDan Pricehave been tireless in their efforts to get theOpenSolaris ZFS communityup and running.Bryan Cantrillhas rounded up all theZFS blog entriesfrom today, which run the gamutfrom informative to surprising to downright funny. And for me,as the papa bear, every one of them is also personally touching.Thank you for using ZFS during the early days, for providing insightson how to make it better, and for taking the time to write up yourpersonal experiences and spread the word.I'm incredibly proud of the ZFS team, and deeply grateful: no one personcan do something on this scale. Thank you for making the leap of faith tojoin me in this effort, to create something out of nothing, to take an ideafrom vision to reality. It has been an amazing and wonderful experience.To Cathy, Andrew, David, and Galen: thank you for support, encouragement,patience, and love. Six years is a long time to wait for Daddy to finishhis project. But somehow, you managed to understand how important thiswas to me, and for you, that was good enough: you've been a constant sourceof energy the whole way. I can't imagine doing it without you.Awww, now I'm getting all weepy.Please come back tomorrow and I promise we'll have that chat about RAID-Z.Technorati Tag: OpenSolarisTechnorati Tag: SolarisTechnorati Tag: ZFS

I was originally planning to blog about RAID-Z today, but I can't. There's been such a tremendous outpouring of energy and passion for theZFS launch today that the only thing I can think about is...

ZFS

ZFS: The Last Word in Filesystems

Boo!Halloween has been a special day for ZFS since its inception.On 10/31/2001, we got the user-level prototype working.On 10/31/2002, we got the first in-kernel mount.And today, 10/31/2005, we integrated into Solaris. ZFS will hit the street in a couple of weeks via Solaris Express.We (the ZFS team) will have much more to say about ZFS in the coming weeks. But tonight, I just want to tell you what it was like to drive this thing home.The ZFS team is distributed: we have people working in Menlo Park, California; Broomfield, Colorado; and several other places. This week, we flew everyone in to Menlo Park and took over a giant conference room.The first thing you notice is the heat. These rooms are made for 100 watt humans, not multi-gigahertz CPUs and associated paraphernalia. And, like any big company, Sun is all about saving money in the dumbest ways -- like turning off the A/C at night, and outsourcing the people who could possibly turn it back on.At first, things went pretty well. We comandeered the Nob Hill conference room, which has a long table and lots of power and network taps. We brought in a bunch of machines and created 'Camp ZFS'. Each new box amped up the heat level, to the point that it became difficult to think. So we grabbed a 36-inch fan from one of the labs to get the air flowing. That was a huge help, although it sounded like you were wearing a pair of lawn mowers as headphones.On Sunday, we plugged in one more laptop. That was it -- we blew the circuit breaker! So here we are, less than 24 hours from our scheduled integration date, and all of our computers are without power -- and the room containing the circuit breakers was locked. (Thanks, OSHA!)So we took a three-pronged approach: (1) went through the Approved Process to get power restored (ETA: April); (2) hunted down someone from campus security to get us key access to the electrical room (ETA: Sunday night); and (3) sent our manager to Home Depot to buy a bunch of 100-foot extension cords so we could, if necessary, run Nob Hill off of the adjacent lab's power grid (ETA: 30 minutes).All three came through. We ran half of the load over extension cords to the lab, the other half on the Nob Hill circuit. It took a bit of experimentation to find a load balance that would stay up without tripping the breaker again. Apparently, we had angered it. (Even now, I'm typing this blog entry courtesy of a shiny new yellow extension cord.)Meanwhile, the clock was ticking.At the end of a large project like this, it's never the technology that kills you -- it's the process, the cleanup of home-grown customizations, the packaging, the late-breaking code review comments, the collapsing of SCCS deltas, stuff like that. With power back up, we slogged on until about 4AM. Everything looked good, so we went home to sleep. Actually, some people just crashed on the couches in my office, and Bill's office next door.By 10AM Monday we were back, making sure that all the final tests had run successfully, and working through the last bits of paperwork with the Solaris release team. After five years of effort, it was time to type 'putback'.Denied! The permissions on a directory were wrong.Fix them up, try again.Denied! One more TeamWare directory with wrong permissions. Fine, fix that too.Last try... and there it goes! 584 files, 92,000 lines of change, 56 patents, 5 years... and there it is. Just like that.Fortunately we were prepared for either success or failure. We had brought in a massive array of vodka, tequila, wine... you name it, we had it. And not in small quantities.As I said at the beginning, we'll have lots more to say in the coming days. But right now, it's time to sleep!Jeff

Boo! Halloween has been a special day for ZFS since its inception. On 10/31/2001, we got the user-level prototype working. On 10/31/2002, we got the first in-kernel mount. And today, 10/31/2005, we...

Slab Allocator

Now It Can Be Told

For thirty years, people have speculated on the identity of Deep Throat.Last week the mystery was finally revealed: the man called Deep Throatwas not John Dean, not G Gordon Liddy, not Al Haig -- no, it was noneother than Mark Felt. That's right, Mark Felt.I'm sorry -- who? Who the f\*\*\* is Mark Felt? Felt, F-E-L-T? Let methink for a minute... Felt... Felt... nope, never heard of him. Ever.You've got to be kidding me. I've waited thirty years for this?Well, if you think that revelation was a letdown, just keep scrolling:because while the chattering classes in Washington were playing theDeep Throat parlor game, an even less compelling question was naggingat far fewer people: where did theslab allocatorget its name?About 20 years ago Kellogg's ran a commercial for Special K cerealwith the tag line, "Can you pinch an inch?" The implication wasthat you were overweight if you could pinch more than an inch of faton your waist -- and that hoovering a bowl of corn flakes would help.Back in high school I was watching TV with some friends, and thiscommercial came on. The voice intoned: "Can you pinch an inch?"Without missing a beat, Tommy, who weighed about 250 pounds, reachedfor his midsection and offered his response: "Hell, I can grab a slab!"Fast forward 10 years. I was debugging a heap corruption bug in theSolaris 2.2 kernel. The kernel had actually crashed in the allocatoritself, as often happens when something corrupts the heap. Trying todisentangle the state, I had the crash dump in one window and the sourcecode for the Solaris 2.2 kernel memory allocator in another.The code had all the hallmarks of what we in the industry call "swill":mysterious hard-coded constants, global locks, fixed-size arrays,unions, macros that implicitly reference global state, and variablenames that are at once long and uninformative. A small taste:mutex_enter(&kma_lock);if ((listp->fl_slack >= 2) || (tmpsiz == max)) { listp->fl_slack -= 2; HEADFREE(listp, bufp); if (tmpsiz < max) bufp->fb_union.fb_state = DELAYED; else { LOOKUP(addr, bufp->fb_union.fb_poolp); if (--(bufp->fb_union.fb_poolp->bp_inuse) == 0 && bufp->fb_union.fb_poolp != Km_NewSmall && bufp->fb_union.fb_poolp != Km_NewBig) { if (Km_IdleI < NIDLEP) { if ((bufp->fb_union.fb_poolp->bp_status & BP_IDLE) == 0) { Km_Idlep[Km_IdleI++] = ...and on and on it went.All of this might have been tolerable if the allocator performed well,or was space-efficient, or had some other redeeming virtue. But no.It was big, fat, slow, and had to die. I went home that night determinedto burn it to the ground. (The allocator, not my home.)The basic idea for the new allocator was to grab a page of memory,carve it up into equal-size chunks, and use a reference count tokeep track of how many chunks were allocated. When the referencecount went to zero, the page could be freed.That worked fine for small buffers (say 1/8 of a page or smaller),but wouldn't quite work for larger buffers: those would require morethan one page. So I couldn't just grab a page; I'd have to grab a ...something. "Grab" must have been a mental trigger: all of a sudden Iremembered Tommy, and how much I loved that line, and that sealed it:we would grab a slab, and this would be called the slab allocator.Now you know. And Mark Felt is looking pretty dang interesting.Technorati Tag: OpenSolarisTechnorati Tag: Solaris

For thirty years, people have speculated on the identity of Deep Throat. Last week the mystery was finally revealed: the man called Deep Throatwas not John Dean, not G Gordon Liddy, not Al Haig -- no,...

ZFS

128-bit storage: are you high?

One gentle reader offered this feedback on our recent ZFS article:64 bits would have been plenty ... but then you can't talk out of your ass about boiling oceans then, can you?Well, it's a fair question. Why did we make ZFS a 128-bit storage system? What on earth made us think it's necessary? And how do we know it's sufficient?Let's start with the easy one: how do we know it's necessary?Some customers already have datasets on the order of a petabyte, or 250 bytes. Thus the 64-bit capacity limit of 264 bytes is only 14 doublings away. Moore's Lawfor storage predicts that capacity will continue to double every9-12 months, which means we'll start to hit the 64-bit limit inabout a decade. Storage systems tend to live for several decades,so it would be foolish to create a new one without anticipating theneeds that will surely arise within its projected lifetime.If 64 bits isn't enough, the next logical step is 128 bits.That's enough to survive Moore's Law until I'm dead, and after that,it's not my problem. But it does raise the question: what are thetheoretical limits to storage capacity?Although we'd all like Moore's Law to continue forever, quantummechanics imposes some fundamental limits on the computation rateand information capacity of any physical device. In particular,it has been shown that 1 kilogram of matter confined to 1 literof space can perform at most 1051 operations per secondon at most 1031 bits of information [see Seth Lloyd,"Ultimate physical limits to computation." Nature 406, 1047-1054(2000)]. A fully-populated 128-bit storage pool would contain2128 blocks = 2137 bytes = 2140bits; therefore the minimum mass required to hold the bits would be(2140 bits) / (1031 bits/kg) = 136 billionkg.That's a lot of gear.To operate at the 1031 bits/kg limit, however, theentire mass of the computer must be in the form of pure energy.By E=mc2, the rest energy of 136 billion kg is1.2x1028 J. The mass of the oceans is about 1.4x1021 kg. It takes about 4,000 J to raise thetemperature of 1 kg of water by 1 degree Celcius, and thus about400,000 J to heat 1 kg of water from freezing to boiling.The latent heat of vaporization adds another 2 million J/kg.Thus the energy required to boil the oceans is about2.4x106 J/kg \* 1.4x1021 kg = 3.4x1027 J. Thus, fully populating a 128-bitstorage pool would, literally, require more energy than boilingthe oceans.

One gentle reader offered this feedback on our recent ZFS article: 64 bits would have been plenty ... but then you can't talk out of your ass about boiling oceans then, can you? Well, it's a fair...

Oracle

Integrated Cloud Applications & Platform Services