2019 SBTB Rust Scala

# Rust and Scala, Sitting in a Tree

## Scale by the Bay - Nov 2019

http://velvia.github.io/presentations/2019-sbtb-rust-scala

---

# About me

* http://github.com/filodb/FiloDB
* http://github.com/velvia
* [@evanfchan](https://twitter.com/Evanfchan)
* [IG: @platypus.arts](http://instagram.com/platypus.arts)

---

# How I Got Into Rust

* FiloDB - in memory TSDB
  * 100 billion compressed data points on single node
  * Up to 1 million samples / second, per node
  * 100% Scala
* Storing data on heap was not feasible
  * Object graphs had >50% overhead
  * nasty and unpredictable GC issues

???
Thought I'd talk about something a bit more universal than in memory DBs..

* Moved most objects off-heap
* .red[*but managing offheap memory manually is hard!*]
* Byte-level high performance data manipulation is nasty in JVM and very error prone

???
I have a confession to make.  The last three years, I stood on stage proclaiming how great
of a TSDB we wrote, and how awesome we are able to squeeze awesome performance with offheap memory.  And they were great innovations - but they led to some really nasty long term code debt and problems.
And if you look at other JVM projects like Spark, HBase, Cassandra, etc. they all have hit similar bumps and gone in similar direction - more offheap, less JVM objects.

---

# How I Got Into Rust (II)

2018 [SBTB: Brian Cantrill](https://www.youtube.com/watch?v=2wZ1pCpJUIM)

* Rust: "Pick 3 - performance, safety, and high-level abstractions"
* Structs for efficient + safe low level data processing
* Provably correct native memory management and concurrency
* Super high performance ceiling with SIMD
* Takes great advantage of architectural trends
  * CPUs not getting faster
  * Safe concurrency, GPU, SIMD, efficient memory use, XPoint, etc.

<!-- ---

# Rust and Values

* Pick 3 - performance, safety, and high-level abstractions
* "It’s basically C++ with newer syntax that guides programmer towards safety still allowing low-level control, how does it do it?" .red[*]

What are Scala's values?

-->
---

# Memory Model and Memory Safety

---

# JVM Memory Model

.left-column[
  ### Stack
  * Primitives
  * References to objects
]
.right-column[
  ### Heap
  * Objects - everything non-primitive
]

---

# JVM Memory Model - GC

<div class="mermaid">
  graph LR
  OBJ1 --> OBJ2
  OBJ2 --> OBJ3
  OBJ2 --> Array4
  Array4 --> Elem0
  Array4 --> Elem1
</div>

Automatic cleanup of "dead" objects

???
JVM has the best garbage collection tech, hands down.
Makes many things super convenient.
Really good fit for short- and medium- term data.
Solves reliable sharing of data.
Does have a cost.

---

# Rust Memory Model

.left-column[
  ### Stack
  * Primitives
  * Structs (fixed size)
  * Fixed size arrays
  * Pointers/references
]
.right-column[
  ### Heap
  * Vecs (lists, arrays)
  * Strings
  * Dynamic-sized objects

Rust has no GC - how does it manage heap memory?
]

---

# Rust Memory Model: Safety

Simple principle:

### Allow mutation only if someone has *unique* access to data.

If your Rust program compiles, then it is free of memory corruption bugs and data races. Period.

---

# Rust: Ownership

```rust
// invalid
let x = String::from("hello");
let y = x;
println!("{}", x);
```

* x is initial owner
* ownership transferred to y -
  * x goes out of scope, deallocated
* last line does not compile: as x is no longer owner
* single ownership guarantees no reference possible after memory freed
* Scoping and ownership ensure objects are valid when referenced

???
for strings, data is not copied

---

# Rust: Borrowing

```rust
let x = String::from("hello");
let y = &x ;
println!("{}", x);
println!("{}", y);
```

* Unlimited number of immutable references / readers
* Only one mutable reference `&mut T` allowed

???
* and only those with unique ownership can create a mutable ref
* References cannot outlive the scope of original variable

---

# Using Type System for Safety

Traits in Rust to prevent memory and concurrency safety issues at compile time:

* `T: Copy` - primitives and structs are copied, independent mutation possible
* `T: Send` - one thread at a time has exclusive ownership/borrowing
* `T: Sync` - multi-threaded ownership/sharing

---

# Safety by Default

---

# Immutability

### Scala: Surface-level immutability, opt-in

```scala
  val map = new collection.mutable.HashMap[String, String]()
  map += "mykey" -> "myvalue"
```

* `val` just means reference is immutable, but object itself is mutable
* Programmer has to opt-in to immutability

---

# Immutability

### Rust: Immutable by default, Deep Immutability

```rust
use std::collections::HashMap;
fn test() {
    let map = HashMap::new();
    map.insert("key1", "value1");
}
```

Compile error:

```rust
error[E0596]: cannot borrow `map` as mutable, as it is not declared as mutable
  --> src/lib.rs:16:5
   |
15 |     let map = HashMap::new();
   |         --- help: consider changing this to be mutable: `mut map`
16 |     map.insert("key1", "value1");
   |     ^^^ cannot borrow as mutable
```

???
Rust does not allow mutation by default.  One has to opt-in to mutation by declaring `let mut`
Note that all APIs have strong notions of mutability baked in.
BTW notice that types are not needed when declaring HashMap, Rust has more advanced type derivation...

---

# Immutability: Objects vs References

```rust
use std::collections::HashMap;
fn test() {
    let mut map = HashMap::new();
    map.insert("key1", "value1");
    let immut_ref = &map ;
    immut_ref.insert("key2", "value2");
}
```

Compile error: immutable ref for mutable object

```rust
error[E0596]: cannot borrow `*immut_ref` as mutable, as it is behind a `&` reference
  --> src/lib.rs:18:5
   |
17 |     let immut_ref = &map ;
   |                     ---- help: consider changing this to be a mutable reference: `&mut map`
18 |     immut_ref.insert("key2", "value2");
   |     ^^^^^^^^^ `immut_ref` is a `&` reference, so the data it refers to cannot be borrowed as mutable
```

???
Notice that `rustc` gives you a help in the error message as to how it can be solved.

---

# Thread Safety

### Scala Actor Example

```scala
class MyActor extends Actor {
  val map = new collections.mutable.HashMap[String, String]
  def receive = {
    case Mutate(k, v) =>
      someFuture.map {
        // Uh oh, this is a diff thread, but easy to forget!
        map += (k, v)
      }
  }
}
```

Common mistake - use a non-thread-safe data structure mutably in another thread

???
So you go, Actors can only process a single message at a time, I can use mutable.HashMap right?

---

# Thread Safety - Rust

`rustc` prevents:
* Sharing an invalid/freed reference across threads
* Using a mutable reference in another thread

```rust
    let mut map = HashMap::new();
    map.insert("key1", "value1");
    let shared_ref = Arc::new(map);
    let h = {
        let shared1 = Arc::clone(&shared_ref);
        thread::spawn(move || shared1.insert("key1", "val1").is_some())
    };
```

```rust
error[E0596]: cannot borrow data in an `Arc` as mutable
  --> src/lib.rs:23:31
   |
23 |         thread::spawn(move || shared1.insert("key1", "val1").is_some())
   |                               ^^^^^^^ cannot borrow as mutable
   |
   = help: trait `DerefMut` is required to modify through a dereference, but it is not implemented for `std::sync::Arc<std::collections::HashMap<&str, &str>>`
```

???
Unless a construct like RwLock or Cow is used

---

# Async/Await - Safe Sharing

Using async/await, Rust can prove safe async borrowing

```rust
use futures::executor::block_on;

// Compiles to an asynchronous future
async fn map_insert(map: &mut HashMap<&str, &str>) {
    map.insert("key1", "val1");
}

pub fn async_map_update() {
    let mut map = HashMap::new();
    map.insert("key1", "value1");
    // Diff thread can async borrow reference as lifetime can be verified
    block_on(map_insert(&mut map));
}
```

---

# Aside: Asynchronous stack traces in Rust

```rust
thread 'async-task-driver' panicked at 'nested async panic!', src/main.rs:42:5
stack backtrace:
...
   8: async_stack_traces::blow_up::{{closure}}
             at src/main.rs:42
...
  15: async_stack_traces::bar::{{closure}}
             at src/main.rs:37
...
  22: async_stack_traces::foo::{{closure}}
             at src/main.rs:32
...
```

---

# Actix - Actors for Rust

```rust
// this is our Message
struct Sum(usize, usize);

// we have to define the response type for `Sum` message
impl Message for Sum {
    type Result = usize;
}

// Actor definition
struct Summator;

impl Actor for Summator {
    type Context = Context<Self>;
}

// now we need to define `MessageHandler` for the `Sum` message.
impl Handler<Sum> for Summator {
    type Result = usize;   // <- Message response type

fn handle(&mut self, msg: Sum, ctx: &mut Context<Self>) -> Self::Result {
        msg.0 + msg.1
    }
}
```

???
Actix is an actor framework for Rust.
Notice how there are no classes in Rust, but what you do is implement different traits.
Here there are three diff traits for actors - Message Actor and Handler.
Also notice the `&mut self`.  Every method declares if it needs mutable or immutable version of self.
This is why there are mutability checks everywhere.

---

# Safe Numeric Processing

* Rust does not coerce `Ints` to `Longs` automatically
* Explicit signed and unsigned types
  * Scala: you have to pick shift operator (`>>` vs `>>>`) depending on signedness
  * Opt-in correctness  :(
  * Rust: `u16 >>` is unsigned shift, `i16 >>` is a signed shift.  Type and compiler enforced!
* Different methods for handling overflows
  * `checked_add`
  * `overflowing_add`
  * `saturating_add`
* 128-bit primitive type is kinda cool

Some of this is of course possible in Scala too, via Spire for example.

---

# Performance AND Abstrations

---

# Structs and Performance

```scala
final case class ChunkQueryInfo(info: ChunkSetInfo,
                                tsReader: LongDataReader, valueReader: VectorDataReader)
final case class ChunkSetInfo(id: Long, startTime: Long, endTime: Long,
                              numRows: Int, chunks: Seq[ChunkPointer])
val chunksToQuery: Seq[ChunkQueryInfo]
```

16 byte header per object:

<div class="mermaid">
  graph LR;
  CQI(16B:ChunkQueryInfo) --> CSI(16B:ChunkSetInfo)
  CQI --> VDR(16B:VectorDataReader)
  CSI --> Seq(16B:Seq of ChunkPointer)
  Seq --> Item1[java.lang.Long]
  Seq --> Item2[java.lang.Long]
</div>

For chunks length of 2, each `ChunkQueryInfo` has ~128 bytes overhead

???
Example1: Scala object graph, from FiloDB, bunch of case classes
Really big deal for data processing and databases.
Overhead maybe as big as data fields themselves

---

# Structs in Rust

```rust
struct ChunkQueryInfo {
  info: ChunkSetInfo,
  ts_reader: LongDataReader,
  valueReader: VectorDataReader
}
struct ChunkSetInfo {
  id: u64,
  start_time: u64,
  end_time: u64,
  num_rows: u32,
  chunks: Vec<&Chunk>
}
```

* Structs are inlined - no object header overhead
* 112 bytes saved per `ChunkQueryInfo`
* Returning structs on stack super cheap + fast

???
I've found myself, SO many times, choosing a hack in FiloDB just to avoid object allocations on returns.  This is a serious JVM deficiency for high-performance code.
* In Scala, we ended up moving above graph to offheap, which made debugging and readability much much harder

---

# Scala: Functional Transform Example

```scala
object CountEvens {
  def apply(numbers: Seq[Int]): Int =
    numbers.filter(n => (n % 2) == 0).length
}
```

* Allocate `scala.Function1` for inner closure
* For each number:
  * Box number into `java.lang.Integer`
  * Pass object into closure `apply` method:
    * Unbox the integer
    * Calculate `n % 2 == 0`
    * Box result into `java.lang.Boolean`
  * Keep only numbers where above condition true
* Count total elements

---

# Rust: Performance AND Abstractions

```rust
pub fn count_evens(nums: Vec<i32>) -> usize {
    nums.iter().filter(|&x| x % 2 == 0).count()
}
```

Rust is able to fully optimize nice functional transforms with inlining and no boxing.

* For each number:
    * Calculate `n % 2 == 0`
  * Keep only numbers where above condition true
* Count total elements

---

# Use case: Rust in Data Processing

Safe + fast as C + abstractions + easy SIMD => WIN!

* [Timely Dataflow](https://github.com/TimelyDataflow/timely-dataflow) - distributed data-parallel compute engine
* [DataFusion](https://arrow.apache.org/blog/2019/02/04/datafusion-donation/) - Apache Arrow's query engine
* [Weld](https://github.com/weld-project/weld) - Stanford's hi-perf IR for analytics

* [MinSQL](https://github.com/minio/minsql/blob/master/README.md)
* [Sled](https://github.com/spacejam/sled) - lock-free database engine
* [Ripgrep](https://github.com/BurntSushi/ripgrep) - insanely fast grep utility

* [Are we learning yet?](http://www.arewelearningyet.com) - list of ML Rust crates

---

# Lessons Learned

* Getting past borrow checker and compiler errors is hard at first.
  * Discord, Rust community everywhere is super helpful
* Rust doesn't have REPL :(
* JVM/Scala is probably more productive for many use cases. But where Rust is good, it's really good

* Cargo is fairly awesome build tool.  Sorry, way ahead of SBT.
* Learning Rust has improved my programming everywhere
* Rust works because safety is *universal* and *pervasive*, and the community has made it a priority
  * Partial safety is not real safety
  * Rust forces safety to be IN YOUR FACE ALL THE TIME.

???
 especially about what it means to be safe.
* Being welcoming and inclusive has to be a foundational value of a community, hard to add it after the fact
In your face  - maybe that's the way it should be

---

# Rust vs Scala, or Rust + Scala?

.left-column[
  ### Rust Standalone
  * Complete, standalone Rust app
  * Good for trying out in microservice architecture
]
.right-column[
  ### Rust + Scala
  * Use Scala for what it's good at: coordination, networking, distributed systems
  * Embed some Rust for high-performance data processing / concurrency with no bugs
  * Use Rust as a .so / .dylib within JVM
]

---

# Rust + Scala

* [JnrFFI](https://github.com/jnr/jnr-ffi) - call into Rust via C FFI.
  * Fast, simple, no SWAG/headers to compile
* [j4rs](https://astonbitecode.github.io/blog/post/j4rs_0.6.0/) for calling Java from Rust
* [JavaCPP](https://github.com/bytedeco/javacpp)

* [GraalVM](http://graalvm.org) - Super promising direct integration of LLVM bitcode and JVM

Example:
* Use Scala/JVM for Zookeeper, distributed coordination, integration layers
* Use Rust for high-performance, memory-heavy portion

---

# Taking Safety back to Scala from Rust

```scala
  final case class U8(addr: Long) extends AnyVal {
    // Simple pointer math, by # of U8 elements (bytes)
    final def add(offset: Int): U8 = U8(addr + offset)
    //scalastyle:off method.name
    final def +(offset: Int): U8 = U8(addr + offset)

final def getU8: Int = UnsafeUtils.getByte(addr) & 0x00ff

final def asU16: U16 = U16(addr)
    final def asI32: I32 = I32(addr)
    final def asMut: MutU8 = MutU8(addr)
  }

final case class MutU8(addr: Long) extends AnyVal {
    final def set(num: Int): Unit = UnsafeUtils.setByte(addr, num.toByte)
  }
```

For offheap data management: explicit Ptr type >> using Longs or type aliases; separate Mutable type; explicit conversions to different widths

---

# Interesting Rust Crates/Frameworks

* https://www.arewewebyet.org
* http://crates.io
* Web Frameworks - Actix, Rocket, Gotham, Iron, Nickel
* Networking/HTTP - H2, Hyper, Tokio
* Fast text processing - nom, pest, regex

IDE Support - IntelliJ-Rust, VSCode, Sublime/Emacs/VIM/Atom + Racer

BTW....

* Swift on Linux is also a thing...  https://swift.org/server/

---

# Thank You Very Much