Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How to make any immutable data structure distributed

unison-lang.org

Post reply on HN
Print view View original

21–30 of 54 posts

Re: How to make any immutable data structure distributed

#21

Post by rlmark »

lidatong wrote: post #13
pchiusano wrote: post #4

One of the authors of the article here, happy to answer any questions about it!

I had a few questions: 1. The posts mention Spark, but were you (the Unison team) also inspired by dataflow / stream processing engines (e.g. Flink, Beam, Timely Dataflow etc.) or any other technologies? 2. Relatedly, are there any plans to add a stream processing API? Or perhaps that would belong in a 3rd-party library? 3. Broadly, where do you think (in your opinion) Unison fits in the ecosystem of tooling? Is Unis…

Hi there! I can't speak to questions 1-3, but with regards to question 4, some of the examples we generated were born from early mistakes I had stumbled into when writing the `Tree` functions, so I have some thoughts. It would be interesting to codify the behavior of evaluating the `Tree` in more types, but looking back, the thing that would have helped me most in avoiding some of the missteps might have been a richer test interpreter, where I could have "mocked" a network of, say, 3 nodes and distributed the `Tree` across them, emitting information about where the data was being moved, and where the various functions were being applied. We had actually briefly thought about writing such an interpreter for the purpose of this article and it's still something I'd like to do at some point.

Re: How to make any immutable data structure distributed

#22

Post by armchairhacker »

skyde wrote: post #20
jltsiren wrote: post #15

I dislike the term "immutable data structure", because it has two widely used conflicting meanings: 1. Read-only data structures, which are used by everyone in every language all the time. 2. Persistent data structures, which make the underlying immutable structures kind of mutable by creating new versions and reusing parts from the old versions of the structure.

lol the word "persistent" is itself ambiguous an have conflicting meaning: 1- https://en.wikipedia.org/wiki/Persistence_(computer_science) In computer science, persistence refers to the characteristic of state of a system that outlives (persists more than) the process that created it. 2- https://en.wikipedia.org/wiki/Persistent_data_structure In computing, a persistent data structure or not ephemeral data structure i…

I usually distinguish "readonly" values (references which block mutation, but you can mutate via another reference) and "immutable" values (what OP calls persistent, where modification may copy-on-write but you're certain the original reference won't mutate).

Re: How to make any immutable data structure distributed

#23

Post by runT1ME »

Scarbutt wrote: post #11
runT1ME wrote: post #6

I really think this is where pure FP shines. If you look at the architecture of something like Apache Beam, while you describe your computations in a language like Java or Python, you're really using a DSL for creating an immutable DAG that processes chunks of immutable data, persisiting each chunk (being loose with terms here) for durability, 'modifying' it in the immutable sense and then passing it on to the next e…

Besides performance, what other cons exists for immutable data structures in a single standalone system?

It's awkward to work with fully nested structures. Think about having a map of customer objects which have a list of addresses and you need to update everyone's first address to be capitalized for some raeson. You'd really want a fully fleshed out lens library and maybe even macros for auto generating them on your concrete data structures to make it easy to 'update' (via a persistent structure) without having to deal with all the cruft of doing it by hand.

Re: How to make any immutable data structure distributed

#24

Post by zomglings »

lidatong wrote: post #12

I think there were a lot of great ideas presented in these small examples. 1. Explicitly marking non-local _data_ vs. in-memory. A very cool idea -- languages and libraries I've used all seem to try to make this transparent (unsuccessfully, as indicated by the random serialization errors you get) 2. Making the noise around serialization and RPC transparent to the user 3. Bring the code to the data, not the data to th…

Your use of the word transparent confused me a little. It seems you are using it in the sense that details that are being made transparent are being hidden from the user.

But if you make something transparent to the user, it could also mean that you are directly exposing that thing to the user. (Right? I could be wrong about this.)

Just confused me and thought it might be useful to you to know that. Not trying to be an asshole.

Re: How to make any immutable data structure distributed

#25

Post by pchiusano »

lidatong wrote: post #13
pchiusano wrote: post #4

One of the authors of the article here, happy to answer any questions about it!

I had a few questions: 1. The posts mention Spark, but were you (the Unison team) also inspired by dataflow / stream processing engines (e.g. Flink, Beam, Timely Dataflow etc.) or any other technologies? 2. Relatedly, are there any plans to add a stream processing API? Or perhaps that would belong in a 3rd-party library? 3. Broadly, where do you think (in your opinion) Unison fits in the ecosystem of tooling? Is Unis…

So what we were going for with the core API is that it should be expressive enough for all kinds of distributed programming tasks, not just Spark-like or batch computing stuff.

We’re planning on doing several of these articles to show different applications. I think some distributed stream processing library would be super cool and there are lots of sources of inspiration for that like you mention. It would be a more interesting translation than the Spark-like stuff though. Likely using the channels ability for message passing.

> By the way, I really loved the FP in Scala book, it was my first step into FP -- thank you and Runar for writing it

That’s great to hear!

Re: How to make any immutable data structure distributed

#26

Post by dwohnitmok »

romero-jk wrote: post #17
Guvante wrote: post #14

Earlier quoted context omitted.

Sharing immutable data is hard. Mutable throw you throw a lock on it and mutate in place. How do you share mutations when you can't change anything? To be clear it is certainly a solvable problem (as this post shows) but it can make things difficult.

This is how clojure does it: https://clojure.org/reference/atoms It's very costly though.

Is it particularly costly compared to locks?

Under the hood it's a effectively a single CAS instruction that loops on failure (which only occurs under contention, but then you have waiting with locks too).

Re: How to make any immutable data structure distributed

#27

Post by melony »

Scarbutt wrote: post #11
runT1ME wrote: post #6

I really think this is where pure FP shines. If you look at the architecture of something like Apache Beam, while you describe your computations in a language like Java or Python, you're really using a DSL for creating an immutable DAG that processes chunks of immutable data, persisiting each chunk (being loose with terms here) for durability, 'modifying' it in the immutable sense and then passing it on to the next e…

Besides performance, what other cons exists for immutable data structures in a single standalone system?

Memory usage, the fancier data structures (most of which are pioneered by Okasaki) in newer FP frameworks and languages are often very memory hungry.

Re: How to make any immutable data structure distributed

#28

Post by Guvante »

nyanpasu64 wrote: post #18
Guvante wrote: post #14

Earlier quoted context omitted.

Sharing immutable data is hard. Mutable throw you throw a lock on it and mutate in place. How do you share mutations when you can't change anything? To be clear it is certainly a solvable problem (as this post shows) but it can make things difficult.

Sharing mutable data without a mutex (which suffers from unbounded contention) is hard. Approaches that work include updating persistent data structures and sharing the new copy, or sharing diff objects over a lock-free queue.

Sharing a new copy isn't always easy though. That is why lens are a thing. Unfortunately lens are (last I checked) still not quite easy to grow.

The point is neither copying the whole structure nor diffs are as easy as mutex + inner mutation.

Re: How to make any immutable data structure distributed

#29

Post by anonymousDan »

pchiusano wrote: post #4

One of the authors of the article here, happy to answer any questions about it!

Could you point to some resources on how the underlying (distributed) runtime is architected/works? Also, is it primarily designed to support 'bringing the code to the data', or can it also support 'bringing the data to the code' a la snowflake?

Re: How to make any immutable data structure distributed

#30

Post by rklaehn »

melony wrote: post #27
Scarbutt wrote: post #11

Earlier quoted context omitted.

Besides performance, what other cons exists for immutable data structures in a single standalone system?

Memory usage, the fancier data structures (most of which are pioneered by Okasaki) in newer FP frameworks and languages are often very memory hungry.

Nothing wrong with using incredibly un-fancy data structures, like arrays, in a FP way. You just need to make sure that you don't do operations that modify individual elements, but work in large batches. So no for loops inserting elements one by one, but map, filter, flatmap...

Most good FP data structures will be tree like, but with a low branching factor and chunky leafs. Now of course that does not save you from lots of memory consumption if you use a language/platform where even primitives are boxed, like the JVM. But that is a completely separate topic.

Post reply on HN