Skip to content

Instantly share code, notes, and snippets.

View Horusiath's full-sized avatar

Bartosz Sypytkowski Horusiath

View GitHub Profile
@Horusiath
Horusiath / lib.rs
Created June 26, 2024 19:10
varint encoding and length-prefix int encoding
#[inline]
fn zigzag_encode(from: i64) -> u64 {
((from << 1) ^ (from >> 63)) as u64
}
// see: http://stackoverflow.com/a/2211086/56332
// casting required because operations like unary negation
// cannot be performed on unsigned integers
#[inline]
@Horusiath
Horusiath / DESIGN.md
Last active June 21, 2023 18:21
Yggdrassil design document

Yggdrassil design document

This paper discusses some ideas of how to extend HyParView/Plumtree beyond the most straightforward implementation. It presents the goals that we wanted to have in mind when building actual implementation in Rust.

Motivation

While Partisan - the original and probably the most widely adopted implementation of HyParView+Plumtree - value proposition relies on building huge clusters (having >10 000 nodes) capable of broadcasting messages via self-healing broadcast trees, its network protocol seems to limit its possibilities to centralized solutions - like services living in data centres or at the edge, where peer discoverability and reachability is in control of their developers/operators. Other issue is that when exchanging neighbors/shuffle peers, plumtree blindly replaces them with current passive view without checking if they are reachable for the current peer in the first place.

We think, that adopting HyParView/Plumtree in Rust with extensible API could expand its capabil

@Horusiath
Horusiath / Prolog.fs
Last active May 17, 2024 15:12
Yata move algorithm
namespace Demos
open System
type ReplicaId = String
[<RequireQualifiedAccess>]
module Array =
@Horusiath
Horusiath / delta_encoding.rs
Last active April 30, 2022 07:19
Various approaches to optimize serialized data size
use crate::session::{SessionDeserialize, SessionSerialize};
use serde::de::{Error, SeqAccess, Visitor};
use serde::ser::SerializeStruct;
use serde::{Deserialize, Deserializer, Serialize, Serializer};
use std::fmt::Formatter;
/// A sample record of time-series data.
#[derive(Debug, Eq, PartialEq, Serialize, Deserialize)]
pub struct Record {
/// A number of milliseconds since UNIX_EPOCH.
@Horusiath
Horusiath / RTree.fs
Last active October 26, 2022 13:55
RTree implementation for 2D spatial data
(*
An immutable R-Tree implementation in F#.
Based on: https://github.com/swimos/swim-rust/tree/main/swim_utilities/swim_rtree (licensed on Apache 2.0)
Author: Bartosz Sypytkowski <b.sypytkowski at gmail.com>
*)
namespace Demos.RTree
@Horusiath
Horusiath / HashRings.fs
Last active May 17, 2024 15:12
Hash rings implementations in F#
module Demo.HashRings
open System
open System.Collections.Generic
/// Range is a tuple describing (s,e] - where `s` is start
/// (exclusive) index, while `e` is end (inclusive) index.
type Range = ValueTuple<int,int>
[<RequireQualifiedAccess>]
@Horusiath
Horusiath / Dht.fs
Last active May 11, 2022 04:01
Consistent hash ring and virtual bucket hash ring implementations
module Demo.Dht
open System
open System.Collections.Generic
/// Range is a tuple describing (s,e] - where `s` is start
/// (exclusive) index, while `e` is end (inclusive) index.
type Range = ValueTuple<int,int>
[<RequireQualifiedAccess>]
@Horusiath
Horusiath / Ramp.fs
Last active May 17, 2024 15:11
RAMP Hybrid transaction protocol implementation using Akka.NET in F#
module Demo.Ramp
open System
open Akka.Actor
open Akkling
/// A Lamport clock timestamp used as transaction identifier - sequence number with unique node identifier.
/// Original paper implementation uses combination of hybrid logical clock with node id encoded together into uint64.
type TxnId = DateTime * int

Requirements:

  • Pull up bar
  • Dumbells (mine had regulated weight: 40kg total)
  • Rubber band (mine is 25kg)
  • Workout 2 uses gymnastics rings
  • Workouts 9 and 10 use bars with higher weights

Warmup

@Horusiath
Horusiath / Protocols.fs
Last active June 21, 2023 18:20
Plumtree + Hyparview implementation in F#
namespace Protocols
open System
open System.Runtime.ExceptionServices
type Endpoint = string
type TTL = int
type Binary = byte[]
type MessageId = Guid
type Round = uint64