vCorfu: A cloud-scale object store on a shared log

https://blog.acolyer.org/2017/05/03/vcorfu-a-cloud-scale-object-store-on-a-shared-log/

• distributed shared log (CORFU)
• vCorfu combines a distributed shared log as in CORFU
with materialized streams that store replicas of ojbect-specific subsets of the log data (one stream per object)
• => vCorfu uses state machine replication to reconstruct the state of an object by replaying the log.
• With materialized stream we don’t store the whole log: just the updates
• but we still have full log
• Like Corfu. vCorfu uses a sequencer to issue log address tokens
• Like Corfu, vCorfu uses a client-side mapping (layouts) how offsets in the global log or in a given materialize stream map to replicas
• Like Corfu, vCorfu moves from one configuration (layout) to another using epochs, sealing, Paxos-based protocol to ensure all replicas agree on the current layout.
• !!!Recovery: vCorfu can tolerate failures as long as a log replica and stream relpica do not fail simultaneously. Log -> stream or stream -> log
• 4 roundtrips to write an update
• Client runtime
• local object view - remote object view
• Composable state machine replication (hash map of hash maps)

IMHO:

• Сложная логика записи (4 раундтрипа для записи)
• «Уникальная форма устойчивости к падениям» (упадут все stream replicas -> можно восстановить из логов)
• client runtime, что сложно
• client-side state machine
• аннотации в программе для

Efficient memory disaggregation with Infiniswap

https://blog.acolyer.org/2017/05/05/efficient-memory-disaggregation-with-infiniswap/

• Why
• Быстрая сеть
• Использовать память удаленной машины вместо локального диска
• RDMA: remote direct memory access: CPU удаленной машины не используется
• Для OS - virtual block device, поэтому не надо изменять приложения и OS
• Надо иметь несбалансированные ноды (Google, Facebook: 70% машин кластеров несбалансированы)
• Использование памяти на каждой ноде должно быть стабильным (изменение < 10% по памяти за след. 10секунд : P = 0.74)
• Выигрыш может быть очень большим 99%-ile latency increase by 71.5x и 21.5x для VoltDB и Memcached
• Практика:
  • 56Gbps, 32-nodes RDMA cluster with infiniswap
  • VoltDB, Memcached, PowerGraph, GraphX, Apache Spark
  • throughput: 4x-15.4x
  • tail latency: 5.4x - 61x
  • 1.47x cluster memory utilization
• How it works
• Two components: block device (kernel module) and daemon
• Block device divides the address space into slabs and maps them across many machines’ remote memory. Paging happens at page granualrity via RDMA
• page-outs - written to remote memory with RDMA and async to disk
• page-in - read from memory (if mapped) or from local disk
• if a remote machine fails - infiniswap relies on the remaining remote memory and the local backup disk.
• No coordinator -> no single point of failure
• Exponential Moving average of page activity: 20 per second -> hot -> mark for remote mapping
• Two choices (one of machines that have slab of this block device - and one of that don’t). Who has the lowest memory usage - will be used.

Google Federated Learning

http://muratbuffalo.blogspot.ru/2017/04/paper-summary-federated-learning.html https://research.googleblog.com/2017/04/federated-learning-collaborative.html

• Распределенное? - автономное? обучение
• Все устройства учатся распределенно, не отправляя в гугл личные данные
• Загружает текущую модель, локально ее модифицирует - и отправляет патч обратно.
• Пришлось придумать, как это должно работать, когда устройства часто не в сети, имеют маленькую пропускную способность и большие latency.
• Сделали paper «Federated Average Algorithm» (https://arxiv.org/abs/1602.05629), который требует 10-100x меньше коммуникаций, по сравнению с наивной версией fedrated «Стохастического Градиентного Спуска» (https://en.wikipedia.org/wiki/Stochastic_gradient_descent)
• Общая идея - телефоны достаточно мощные, чтобы пересылать не простые градиентные шаги, больше шагов локально - меньше объем передачи.
• Загрузка долгая - компактизация результатов (100x)
• Применяется как для обучения deep networks, так и для других задач
• Запуск на миллионах устройств - тоже сложная задача. По сути, на каждом устройстве запускается локальная версия TensorFlow. работа осуществляется, когда подключено к питанию и бесплатной (?) сети.
• Secure Aggregation Protocol (http://eprint.iacr.org/2017/281), который позволяет произвести расшифровку данных, только одновременно для 100s-1000s пользовательских телефонов, но не для индивидуальных данных с одного телефона
• Итого, гугл получает два плюса (учится на пользовательских данных + использует чужие CPU), пользователь -только один (его данные не используются, но в целом система улучшается)

Paper “Communication-Efficient Learning of Deep Networks from Decentralized Data”

https://arxiv.org/pdf/1602.05629.pdf

• Узкое место смартфонов - передача данных. Передать все данные в облако - не получится, можно провести первичную обработку и послать результаты
• upload rate = 1/3 of download rate - нужно максимально компактизировать данные при отправке
• применяется для приложений:
  • классификация изображений: предсказание, какие скорее всего будут посмотрены и пошарены
  • моделирование языка: улучшение распознавания голоса и введение текста на клавиатурах телефонов
  • Гугл уже применяет распределенное обучение для GBoard клавиатуры для андроида для улучшения введения текстов
• Алгоритм:
  • Sync update scheme in rounds of communications
  • Set of K clients (with local datasets)
  • At the beginning of each round, peek C of workers
  • global alg state is sent to C workers (actually, model parameters)
  • each worker perform local computation based on the global state and its local dataset, and sends an update to the server.
  • Server applies updates to the global state (by averaging) and repeat the round
• Alg is the same as usual, differences:
  • subset of workers
  • workers work on local dataset, may do multiple iterations on the local-model-update
  • the model, not the gradients is transmitted back
• Alg parameters:
  • C, workers number
  • E, number of training passes each worker makes over its local dataset
  • B, local minibatch size (B== infinity -> full local dataset is used)