A high-performance Directed-Acyclic-Graph JIT in Go

Overview

GAG - A Directed-Acyclic-Graph JIT in Go

GAG is a library I created while developing https://isobot.io to experiment with different ways of implementing the core runtime.

It intends to be a fast, highly parallel, DAG JIT, while still maintaining the balance between performance and usability.

While the runtime is included in this library, a significantly more complex type system would need to be implemented ontop of GAG before it would likely be useful for any such similar use case.

Concepts

Similar to traditional DAGs, there are 4 fundamental primatives in GAG:

  • Graph
    • A collection of Nodes & Edges
  • Vertex
    • A field on a node
  • Edge
    • A connection between two vertex
  • Node
    • A unit of work with inputs and outputs, analagous to a function

Execution

Unlike traditional Flow-Based Programming, GAG includes the concept of "executing" or "running" a node. This fundamentally controls the flow of the graph's execution. Nodes can include an Execution type in their Output field which will be linked to the next node at runtime.

Caching

GAG also caches the Output fields of any node that has already been run. In the future when the JIT is improved this may only conditionally occur when it is optimal.

Examples

A rather trival graph that simply adds 2 numbers together to compare the sum and panic depending on the result could be represented as such:

&Graph{
	Nodes: []Node{
		{Name: "Adder"},
		{Name: "Comparer"},
		{Name: "Panicer"},
	},
	Edges: []Edge{
		{Output: Vertex{Raw: 1}, Input: Vertex{ID: 0, Field: "Number1"}},
		{Output: Vertex{Raw: 2}, Input: Vertex{ID: 0, Field: "Number2"}},
		{Output: Vertex{ID: 0, Field: "Sum"}, Input: Vertex{ID: 1, Field: "Number1"}},
		{Output: Vertex{Raw: 4}, Input: Vertex{ID: 1, Field: "Number2"}},
		{Output: Vertex{ID: 1, Field: "Greater"}, Input: Vertex{ID: 2}},
	},
}

Where the implementation of the Adder and Comparer nodes look like:

type Adder struct {
	Input struct {
		Number1 int
		Number2 int
	}

	Output struct {
		Sum int
	}
}

func (a *Adder) Run(ctx *Context) error {
	a.Output.Sum = a.Input.Number1 + a.Input.Number2
	return nil
}

type Comparer struct {
	Input struct {
		Number1 int
		Number2 int
	}

	Output struct {
		Greater Execution
		Less    Execution
	}
}

func (c *Comparer) Run(ctx *Context) error {
	if c.Input.Number1 > c.Input.Number2 {
		return c.Output.Greater(ctx)
	}

	return c.Output.Less(ctx)
}

The graph can also be visually represented like:
graph
Or in isobot.io: iso-graph

TODO

  • Allow tainting specific outputs to invalidate downstream caches
  • Additional node lifecycle methods
  • Further performance improvements
  • Build out a more real-world benchmarking test suite

WARNINGS

There is lots of unsafe non-standard reflection going on in this project. It is not nearly tested enough to be used in production, and there are likely many dragons hiding in the code itself.

You might also like...
Graph and alert on '.rrd' data using grafana, RRDTool and RRDSrv.

Grafana RRD Datasource A grafana datasource for reading '.rrd' files via RRDTool and RRDsrv. With this datasource you will be able to create grafana d

K8s-graph - Kubernetes ownerReferences graphs
K8s-graph - Kubernetes ownerReferences graphs

k8s-graph Kubernetes ownerReferences dependency graph. Running Suppose you have

Show dependency graph of docker images/containers
Show dependency graph of docker images/containers

docker-graph Show dependency graph of docker images/containers like this: Orange is images and green is containers. Features Collect docker images, co

The server-side reproduction, similar the one of https://popcat.click, improve the performance and speed.

PopCat Echo The server-side reproduction, similar the one of https://popcat.click, improve the performance and speed. Docker Image The docker image is

Kubernetes Node Performance Validator

Kubernetes Node Performance Evaluator This repository contains a set of tools for testing the performance of all the nodes in a kubernetes cluster. Wh

This library provides a metrics package which can be used to instrument code, expose application metrics, and profile runtime performance in a flexible manner.

This library provides a metrics package which can be used to instrument code, expose application metrics, and profile runtime performance in a flexible manner.

False-sharing-demo - Demo for performance effects of CPU cache false-sharing

Example of CPU cache false-sharing in Go. A simple example where 2 integer varia

Grafana Tempo is a high volume, minimal dependency distributed tracing backend.
Grafana Tempo is a high volume, minimal dependency distributed tracing backend.

Grafana Tempo is an open source, easy-to-use and high-scale distributed tracing backend. Tempo is cost-efficient, requiring only object storage to ope

PolarDB Stack is a DBaaS implementation for PolarDB-for-Postgres, as an operator creates and manages PolarDB/PostgreSQL clusters running in Kubernetes. It provides re-construct, failover swtich-over, scale up/out, high-available capabilities for each clusters.
PolarDB Stack is a DBaaS implementation for PolarDB-for-Postgres, as an operator creates and manages PolarDB/PostgreSQL clusters running in Kubernetes. It provides re-construct, failover swtich-over, scale up/out, high-available capabilities for each clusters.

PolarDB Stack开源版生命周期 1 系统概述 PolarDB是阿里云自研的云原生关系型数据库,采用了基于Shared-Storage的存储计算分离架构。数据库由传统的Share-Nothing,转变成了Shared-Storage架构。由原来的N份计算+N份存储,转变成了N份计算+1份存储

Owner
V-X
V-X
A Golang based high performance, scalable and distributed workflow framework

Go-Flow A Golang based high performance, scalable and distributed workflow framework It allows to programmatically author distributed workflow as Dire

Vanu 691 Jan 6, 2023
topolvm operator provide kubernetes local storage which is light weight and high performance

Topolvm-Operator Topolvm-Operator is an open source cloud-native local storage orchestrator for Kubernetes, which bases on topolvm. Supported environm

Alauda.io 24 Nov 24, 2022
An high performance and ops-free local storage solution for Kubernetes.

Carina carina 是一个CSI插件,在Kubernetes集群中提供本地存储持久卷 项目状态:开发测试中 CSI Version: 1.3.0 Carina architecture 支持的环境 Kubernetes:1.20 1.19 1.18 Node OS:Linux Filesys

BoCloud 10 May 18, 2022
A batch scheduler of kubernetes for high performance workload, e.g. AI/ML, BigData, HPC

kube-batch kube-batch is a batch scheduler for Kubernetes, providing mechanisms for applications which would like to run batch jobs leveraging Kuberne

Kubernetes SIGs 1k Jan 6, 2023
Carina: an high performance and ops-free local storage for kubernetes

Carina English | 中文 Background Storage systems are complex! There are more and more kubernetes native storage systems nowadays and stateful applicatio

null 557 Dec 30, 2022
A golang CTF competition platform with high-performance, security and low hardware requirements.

CTFgo - CTF Platform written in Golang A golang CTF competition platform with high-performance, security and low hardware requirements. Live Demo • Di

CTFgo 2 Oct 20, 2022
StoneWork is a high-performance, all-(CNFs)-in-one network solution.

StoneWork, high-performance dataplane, modular control-plane solution StoneWork is used by PANTHEON.tech to integrate its CNFs on top of a single shar

PANTHEON.tech 22 Dec 23, 2022
A high performance online bookstore system.

HPOB 高性能网上书店 A high performance online bookstore system. Introduction 介绍 一个基于Gin、gorm、viper、zap等库的web服务器,实现了网上书店相关接口。 Summary 概要 使用go语言编写的,基于gin、gorm、

邹永赫 2 Apr 27, 2022
High-performance GitHub webhook events toolset for Go :rocket:

githubevents GitHub webhook events toolset for Go githubevents is a webhook events toolset for the Go programming language inspired by octokit/webhook

Christian Bargmann 38 Dec 24, 2022