Experimental chill

Wide LRC codes

Я как-то писал в канале про Erasure Codes, в том числе про LRC, который в какой-то степени стал стандартом. Напомню, что про Erasure Codes можно думать как redundancy technique -- если у вас есть данные, их можно поделить на 2 части, посчитать xor, теперь при выпадении любой из 3 получившихся частей, мы можем восстановить данные полностью. В итоге потратили 1.5x места, но redundancy 2 (при выпадении любого 1 куска данные восстанавливаются). Если копать глубже, то дополнительные k частей получаются умножением на матрицу (n + k) x n над полем F_2 или F_256, а при выпадении любых k, матрицу можно обратить и восстановить данные. Вопрос в нахождении матрицы, но так получается, что k можно брать достаточно маленьким по сравнению с n и фактически можно достигнуть любой практической redundancy k потратив (1+eps) места. LRC идут дальше, они стараются группировать некоторые из n частей вместе, чтобы обращение матрицы было частичным -- скажем, поделим всё на 12 частей, у первых 6 посчитаем XOR, у вторых 6 посчитаем XOR, попробуем найти матрицу 16 x 12, где две строки это такие линейные преобразование и ещё 2, чтобы матрица была полностью обратима. Теперь если выпал один чанк данных, то можно скачать 6 других восстановить по XOR, если два чанка в двух разных группах, то тоже всё сработает, а если выпало 3 или 2 в одной группе, ну что ж поделать, скачаем всё и обратим матрицу. Но такие случаи реже случаются, поэтому инженерия любит такое дело. Такие группы называют локальными группами, а дополнительные чанки у локальных групп -- локальные чанки, а дополнительные чанки для всей операции -- глобальные чанки.

На FAST'23 вышла статья в Google про широкие LRC коды. Это такие коды, которые делят на очень много частей, чтобы получить большую redundancy и потратить поменьше места. Холодный storage может делить данные на сотни частей и делать всего десятки дополнительных чанков получая redundancy в 6-7 c оверхедом на весь сторадж процентов в 10% (например, (96, 4, 5) делит на 96 частей, бьёт на 4 локальные группы с 5 глобальными чанками). Хоть и теория кодов очень хорошо изучена, на практике становится слегка сложно с балансом двух вещей

* Находить обратимые матрицы с свойствами локальных чанков
* Сделать операции локальных чанков достаточно простыми, скажем, обычный XOR ок, но что-то сложнее уже слегка путает инженеров. Простота также полезна для миграций -- можно ли как можно больше посчитанных чанков сохранить

Обычно LRC коды изучают как сделать операции над локальными чанками. Статья от Google показывает, что можно сделать слегка лучше -- смотреть на локальные группы как функцию не только от изначальных данных, но и от глобальных чанков, а можно также смотреть как на функцию от данных, глобальных и локальных. Так становится чуть проще размазать локальные чанки по всем данным. Определение и трюк слегка self-referential в том плане, что локальные чанки определяются через локальные, но статья считает некоторую математику, которая сходится.

Зачем это надо?

В статье можно увидеть только слегка лучше результаты по метриками redundancy, average cost of repair и тд. Цифры не ахти в сравнении и никакой супер революции этот LRC метод не привносит. Он рассказывает историю как продвинуть рисёрч слегка дальше по достаточно практичной теме как LRC коды.

Keep on pushing, статья рассказывает хорошую историю.

https://www.usenix.org/system/files/fast23-kadekodi.pdf
https://www.youtube.com/watch?v=pfnSYWEf5q4

www.group-telegram.com/it/experimentalchill.com/244

12.2K viewsMay 22, 2023 at 11:42

Wide LRC codes

Я как-то писал в канале про Erasure Codes, в том числе про LRC, который в какой-то степени стал стандартом. Напомню, что про Erasure Codes можно думать как redundancy technique -- если у вас есть данные, их можно поделить на 2 части, посчитать xor, теперь при выпадении любой из 3 получившихся частей, мы можем восстановить данные полностью. В итоге потратили 1.5x места, но redundancy 2 (при выпадении любого 1 куска данные восстанавливаются). Если копать глубже, то дополнительные k частей получаются умножением на матрицу (n + k) x n над полем F_2 или F_256, а при выпадении любых k, матрицу можно обратить и восстановить данные. Вопрос в нахождении матрицы, но так получается, что k можно брать достаточно маленьким по сравнению с n и фактически можно достигнуть любой практической redundancy k потратив (1+eps) места. LRC идут дальше, они стараются группировать некоторые из n частей вместе, чтобы обращение матрицы было частичным -- скажем, поделим всё на 12 частей, у первых 6 посчитаем XOR, у вторых 6 посчитаем XOR, попробуем найти матрицу 16 x 12, где две строки это такие линейные преобразование и ещё 2, чтобы матрица была полностью обратима. Теперь если выпал один чанк данных, то можно скачать 6 других восстановить по XOR, если два чанка в двух разных группах, то тоже всё сработает, а если выпало 3 или 2 в одной группе, ну что ж поделать, скачаем всё и обратим матрицу. Но такие случаи реже случаются, поэтому инженерия любит такое дело. Такие группы называют локальными группами, а дополнительные чанки у локальных групп -- локальные чанки, а дополнительные чанки для всей операции -- глобальные чанки.

На FAST'23 вышла статья в Google про широкие LRC коды. Это такие коды, которые делят на очень много частей, чтобы получить большую redundancy и потратить поменьше места. Холодный storage может делить данные на сотни частей и делать всего десятки дополнительных чанков получая redundancy в 6-7 c оверхедом на весь сторадж процентов в 10% (например, (96, 4, 5) делит на 96 частей, бьёт на 4 локальные группы с 5 глобальными чанками). Хоть и теория кодов очень хорошо изучена, на практике становится слегка сложно с балансом двух вещей

* Находить обратимые матрицы с свойствами локальных чанков
* Сделать операции локальных чанков достаточно простыми, скажем, обычный XOR ок, но что-то сложнее уже слегка путает инженеров. Простота также полезна для миграций -- можно ли как можно больше посчитанных чанков сохранить

Обычно LRC коды изучают как сделать операции над локальными чанками. Статья от Google показывает, что можно сделать слегка лучше -- смотреть на локальные группы как функцию не только от изначальных данных, но и от глобальных чанков, а можно также смотреть как на функцию от данных, глобальных и локальных. Так становится чуть проще размазать локальные чанки по всем данным. Определение и трюк слегка self-referential в том плане, что локальные чанки определяются через локальные, но статья считает некоторую математику, которая сходится.

Зачем это надо?

В статье можно увидеть только слегка лучше результаты по метриками redundancy, average cost of repair и тд. Цифры не ахти в сравнении и никакой супер революции этот LRC метод не привносит. Он рассказывает историю как продвинуть рисёрч слегка дальше по достаточно практичной теме как LRC коды.

Keep on pushing, статья рассказывает хорошую историю.

https://www.usenix.org/system/files/fast23-kadekodi.pdf
https://www.youtube.com/watch?v=pfnSYWEf5q4

BY Experimental chill