osukhoroslov / dslab Goto Github PK

Иногда хочется делать какие-то изменения в коде, периодически проверяя, что ход симуляции не поменялся (рефакторинг). Один из вариантов -- один раз посчитать некий хеш симуляции и сделать тест на него. Здесь хешем может быть хеш последовательности обработанных event-ов, тогда нужен будет дополнительный trait (в идеале Hash, но можно и любой, позволяющий дампать в строку, например Debug)

• Простая модель с разделением общей пропускной способности сети, без учета топологии
• Сетевые хосты и привязка акторов к хостам
• Поддержка моделирования топологии сети (хосты, каналы, коммутаторы...)
• Моделирование передач данных с учётом топологии (маршруты, разделение пропускной способности каналов)

Почему у нас нет DagSimulation.load_network()? Давайте добавим аналогично DagSimulation.load_resources()? Тогда пример из README немного упростится.

У сети надо добавить поддержку отправки события актору с задержкой равной latency (или 0 если на одном хосте). См. метод send здесь: https://github.com/osukhoroslov/sim-project/blob/main/examples/master-workers/src/network.rs

See for example this study: https://ieeexplore.ieee.org/document/8411026

• Create generic StorageResource trait.
• Implement this trait for Disk and SharedDisk.
• Support mounting arbitrary StorageResource implementation in FileSystem.
• Try to merge Disk and SharedDisk into a single implementation (the only difference is concurrency level, which can be enforced based on configuration parameter).

• Examples: Lustre, GlusterFS, HDFS
• Multiple disks + management layer + file system

• Perform series of experiments to analyze the performance of I/O operations on different kinds of disks.
• Validate and calibrate the used disk storage models.
• Identify possible improvements of these models.

Related work:

• https://hal.inria.fr/hal-01197128/document
• https://simgrid.org/tutorials/simgrid-io-ccgrid.pdf
• https://simgrid.org/doc/latest/Calibrating_the_models.html#i-o-calibration
• https://github.com/simgrid/simgrid/blob/master/docs/source/tuto_disk/tuto_disk.cpp

It is licensed under GPL 2.0 or later, which is unacceptable for us. Try to use other crate for parsing dot files with more permissive license.

• Implement a model for cloud storage service, such as S3
• The internal implementation of service is unknown (black box)
• Use empirical distribution of bandwidth?

• Сделать базовый lib crate с моделью DAG и пример использования
• Разбить текущий runner на generic runner + интерфейс scheduler-а, с помощью которого можно будет реализовывать разные алгоритмы планирования DAG
• Добавить реализации нескольких алгоритмов (см. примеры из pysimgrid)
• Реализовать визуализацию расписания выполнения DAG (пример)
• Поддержать чтение DAG из файлов в основных legacy-форматах (DAX, DOT, что-то еще?)
• Поддержкать чтение конфигурации системы (ресурсы, сеть) из файла (здесь формат можно сделать свой)
• Поддержать запуск пакетных экспериментов (пример) и обработку их результатов (пример)

... that can be used in different contexts.

Encapsulates CPU and (local) storage models, can be attached to network.

The effective activity throughput (used e.g. to compute activity remaining work) is computed as throughput * factor, where throughput is computed using the throughput sharing model.

By default factor=1. To model various phenomena (e.g. variation of throughput or dependence of throughput of activity size) it should be possible to override the factor per each activity using the provided implementation of ThrougputFactorFunction trait, which takes activity size (volume) and SimulationContext (to access time and RNG).

This should generalize and replace BWModel from dslab-storage.

Details of implementation in SimGrid:

• https://github.com/simgrid/simgrid/blob/c6f2914980450d19e7b47590a88698bb2b30e5c6/include/simgrid/kernel/resource/Action.hpp#L261
• https://github.com/simgrid/simgrid/blob/76ec29f832083ef95c56afbd1e11fc29856a0770/src/kernel/resource/Action.cpp#L99
• https://github.com/simgrid/simgrid/blob/2516bc5bf0760874f7ccd2b878657e6ab442649d/docs/source/tuto_disk/tuto_disk.cpp#L149
• https://github.com/simgrid/simgrid/blob/master/examples/cpp/network-factors/s4u-network-factors.cpp

На практике запрос от пользователя может приходить сразу на запуск группы ВМ. Хочется такие сценарии поддерживать, например размещать ВМ в запросе с учётом ограничений типа placement strategies.

See #88 (comment)

... that can be reused in different domain-specific models.

Physical machines -> Racks -> Network topology

... that can be reused in different contexts (e.g. modeling k8s cluster or FaaS cloud).

Should implement dynamic resource allocation and scheduling of CPU time between containers running on machine.

В сеть надо добавить привязку акторов к хостам, с тем чтобы потом учитывать её при вычислении времени передач - если акторы находятся на одном хосте, то время передачи должно вычисляться особым образом.

См. пример того, как это может выглядеть в https://github.com/osukhoroslov/sim-project/blob/main/examples/master-workers/src/network.rs. Здесь если акторы на одном хосте, то время передачи берется 0, но для общности лучше завести параметры local_latency и local_bandwidth.

• Реализовать базовую модель с хостами и планировщиком
• Реализовать продвинутую модель с несколькими планировщиками и placement store
• Добавить поддержку моделирования динамического потребления ресурсов ВМ, сбор и передачу этой информации планировщикам через мониторинг
• Реализовать несколько алгоритмов размещения и миграции ВМ
• Поддержать чтение и использование открытых датасетов (Azure, Huawei)
• Поддержать чтение конфигурации облака из файла
• Поддержать проведение пакетных экспериментов (конфиг системы + датасет + набор алгоритмов)
• Добавить тесты на корректность учёта используемых ресурсов (например, что в конце во всех store свободные ресурсы равны суммарным)

@vetand дописывайте сюда задачи по мере появления идей

Throughput function implementation instantiated from table with experimental results (similar to this example)

DHT

• Chord: https://github.com/simgrid/simgrid/tree/master/examples/cpp/dht-chord
• Kademlia: https://github.com/simgrid/simgrid/tree/master/examples/cpp/dht-kademlia

BitTorrent

• https://github.com/simgrid/simgrid/tree/master/examples/cpp/app-bittorrent

Gossip & Epidemic Protocols

• https://flopezluis.github.io/gossip-simulator/
• https://www.serf.io/docs/internals/simulator.html
• https://github.com/saurabh1907/gossip-protocol-simulator-distributed-systems

Load Balancing

• https://brooker.co.za/blog/2012/01/17/two-random.html
• https://www.youtube.com/watch?v=6NdxUY1La2I
• https://www.youtube.com/watch?v=kpvbOzHUakA
• https://github.com/zehuamama/balancer
• https://github.com/fufuok/balancer

Caching

• https://hyeontaek.com/papers/loadbal-socc2011.pdf
• https://www.usenix.org/system/files/osdi20-yang.pdf

Tail Latency

• https://www.barroso.org/publications/TheTailAtScale.pdf
• https://brooker.co.za/blog/2021/04/19/latency.html
• https://brooker.co.za/blog/2021/10/20/simulation.html

Circuit Breaker

• https://martinfowler.com/bliki/CircuitBreaker.html
• https://dl.acm.org/doi/pdf/10.1145/3542929.3563466

Cluster Scheduler

• https://www.bigdataschool.ru/blog/yarn-scheduler-how-does-it-works.html
• https://data-flair.training/blogs/hadoop-schedulers/
• https://eduwrench.ics.hawaii.edu/pedagogic_modules/batch_scheduling/

Replication

• Chain replication: https://www.cs.cornell.edu/home/rvr/papers/OSDI04.pdf

Consensus

• RAFT: https://raft.github.io/raft.pdf
• MultiPaxos in RAFT terms: https://arxiv.org/pdf/2004.05074.pdf

Other

• eduWRENCH Examples: https://github.com/wrench-project/eduwrench

Currently variation is supported by Disk and degradation is supported by SharedDisk. The goal is to support them both in a single storage model.

See related issues #125 #126.

memory_load > 1 will lead to OOMs

#113 (comment)

Currently compute and storage support only elementary activities consisting of fixed work (flops, bytes).

Real applications consist of a mix of such activities. Some typical cases can be supported as ready-to-use workload models.

See for example workloads in OpenDC:

• https://github.com/atlarge-research/opendc/tree/master/opendc-simulator/opendc-simulator-compute/src/main/kotlin/org/opendc/simulator/compute/workload
• https://github.com/atlarge-research/opendc/tree/master/opendc-experiments/opendc-experiments-compute/src/main/kotlin/org/opendc/experiments/compute/internal

• #75 (comment)
• #75 (comment) (second part)

See Figure 4 in this paper.

Implementation is SimGrid: https://github.com/simgrid/simgrid/blob/master/src/plugins/file_system/s4u_FileSystem.cpp

See also #198 for idea how to model remote storage reads/writes.

1. Implement more power models (see models from OpenDC, CloudSim, SimGrid)
2. Move models from dslab-iaas to dslab-models (generic models) to extend their reuse in the future.

Related work:

• Modeling, Prediction and Optimization of Energy Consumption of MPI Applications using SimGrid (Chapter 8)
• Predicting the Energy Consumption of MPI Applications at Scale Using a Single Node

Useful links about DVFS:

• https://en.wikipedia.org/wiki/Dynamic_frequency_scaling
• https://research.spec.org/icpe_proceedings/2021/companion/p95.pdf
• https://blog.cloudflare.com/hertzbleed-explained/
• https://www.kernel.org/doc/html/v4.14/admin-guide/pm/cpufreq.html

Known attempts to model DVFS in simulators:

• Simgrid: plugin, thesis (see Chapter 9)
• OpenDC: governors

Impact on power models:

• How does DVFS interact with the host energy model?

See https://wta.atlarge-research.com/

Do we need to rename crates to publish them later?

https://stackoverflow.com/questions/72348259/cargo-package-doesnt-work-with-rusts-workspace

Currently if step_for_duration is called with duration D and there is no event at time + D the time after simulation equals the time of the last event. It is proposed to advance the simulation time to time + D which is more natural.

Physical Machine -> Rack -> Cluster -> Datacenter -> AZ -> Region

Сейчас в примере iaas-traces надо передавать тип и путь к датасету через опции командной строки, а имя конфиг файла зашито. Удобнее передавать программе путь к конфиг файлу (тогда можно написать свой конфиг), а тип и путь к датасету указывать внутри конфига. Предлагаю поддержать это и переделать пример.

See 4.1 in Millions of Tiny Databases

Possible directions:

• (Hard) Take some existing framework for building distributed applications (e.g. gRPC) and build mocks of network, storage, clocks etc.
• (Easy) Create a simple similar framework and support running apps built against it in simulation. See original dslib from 2020: https://github.com/osukhoroslov/distsys-course-hse/tree/master/2020/dslib
• (Medium) Create a feature-rich framework, which can be used in production systems, like Coyote actors: https://www.microsoft.com/en-us/research/uploads/prod/2021/09/poolmanager-coyote.pdf

#68 (comment)
https://github.com/osukhoroslov/sim-project/tree/feat/storage/rational

Automate the search of simulation model parameters to optimize the simulation accuracy.

Related work:

• https://scholarspace.manoa.hawaii.edu/server/api/core/bitstreams/1c530555-04b0-4f72-bbfa-37c31590d44e/content

• Простой API + модель хранилища с вычислением времен операций только по объему данных (см. master-workers)
• Файловый API в духе SimGrid
• Продвинутая модель с эмпирическим распределением bandwidth и зависимостью от числа конкурентных операций (см. статью)

SimGrid

• Modeling I/O: the realistic way
• Статья и туториал
• Disk: API, код
• File System: API, код

The log output format should be consistent across the framework, system actors and user code.

Сделать отдельные счётчики для:

• всех событий (уже есть)
• сработавших событий
• отмененных событий

Также было бы полезно считать количество событий каждого типа.

Related work:

• CloudSim: Cloudlet Schedulers
• OpenDC: Space Shared, Fair Share

Linux CPU schedulers:

• http://retis.sssup.it/luca/KernelProgramming/Slides/kp_scheduler.pdf
• https://www.scaler.com/topics/operating-system/process-scheduling/
• http://cobweb.cs.uga.edu/~maria/classes/x730-Spring-2018/project4-scheduler.html
• CFS: https://nihal111.github.io/CFS-visualizer/
• Nest: https://www.phoronix.com/news/Nest-Linux-Scheduling-Warm-Core

Сейчас миграция ВМ никак не влияет на её производительность, в частности нет никакого даунтайма, ВМ мгновенно переносится с одного сервера на другой. Необходимо немного усложнить модель, добавить даунтайм и увеличить использование CPU.

• emit_resp(event, delay) - send event to event source (dest=from)
• emit_now(event, dest) - send event immediately (delay=0.)
• emit_resp_now(event)- send event to event source immediately
• emit_self(event, delay)- send event to self (dest=ctx.id)

Related work:

• A CPU Contention Predictor for Business-Critical Workloads in Cloud Datacenters

Implementations:

• OpenDC: stealTime metric, example,

• Currently we cannot use dot-parser which is licensed under GPL 2.0 or later
• Implement new dot parser using other library or own solution
• Uncomment montage example in examples/dag

Modeling of interference between VMs in OpenDC:

• Model
• Example
• cpuLostTime metric