Reading rollup, 2014-12-26.

| categories: reading

  • Epidemic broadcast trees - Leitâo et al.

    This came up in the context of Riak scalability; IIUC it's part of the 2.0 series. Basho have report from RICON 2013 on this.

    Plumtree: "push-lazy-push multicast tree."

    Combines an eager gossip push strategy (along the spanning tree path) with a lazy gossip pull strategy (for recovery). You have a gossip overlay network (where each node has a partial view of the whole set), and a tree of nodes built on top of that. Cuts in the tree can be healed quickly by using the underlying (pull) network.

    "The links used for eager push are selected in such a way that their closure effectively builds a broadcast tree embedded in the random overlay network."

    Heh, GRAFT and PRUNE messages. :o)

    They include detailed descriptions of simulations backing up their claims.


    "There is an inherent trade-off between epidemic and deterministic tree-based broadcast primitives. Tree-based approaches have a small message complexity in steady-state but are very fragile in the presence of faults. Gossip, or epidemic, protocols have a higher message complexity but also offer much higher resilience. This paper proposes an integrated broadcast scheme that combines both approaches. We use a low cost scheme to build and maintain broadcast trees embedded on a gossip-based overlay. The protocol sends the message payload preferably via tree branches but uses the remaining links of the gossip overlay for fast recovery and expedite tree healing. Experimental evaluation presented in the paper shows that our new strategy has a low overhead and that is able to support large number of faults while maintaining a high reliability."

  • Software Testing with QuickCheck - John Hughes

    I'm working with Erlang these days, so I've been able to get an evaluation license for Erlang QuickCheck.

    This paper is a tutorial, working from simple property-based tests through to testing properties of a stateful system using abstract state machines to model its behaviour.

    It's lucidly written: in tandem with the QuickCheck library documentation, I was able to work fairly confidently through the examples and most of the exercises, despite the work requiring the occasional brain-flip.

    I'm really enjoying the property-based testing approach, and this implementation has clearly had a lot of work and thought put into it. It feels like cheating to be able to do testing that feels so (executably!) formal and complete in this little code.

  • AQD: Remembrancer |

    "A Quite Disposition" is James Bridle's "weak AI for gathering information about drones". It's a fascinating project. The Remembrancer is a free newspaper built automatically from the database.

    "In this world, we must take responsibility not only for our own actions, but the actions of the vast non-human assemblages we have built around us—from corporations to complex software systems—and acknowledge the moral and physical limits of our technologies, and ourselves."

Generated from pinboard by pinroll.

Reading rollup, 2014-09-27.

| categories: reading

Some news: I will start writing code for Hosted Graphite next week.

It's a (mostly) remote position, which makes it possible for me to spend winter in France with the family. We found a lovely place to live in an old medieval town on the Vienne. Spinning up a little French fluency now, remarkable how fast it comes when you've got a definite goal. :o)

Hat-tip (as is often the case!) to for the first two links below.

  • Coreutils viewer


    A Linux tool to show progress for cp, rm, dd, ...

    It simply scans /proc for interesting commands, and then uses the fd/ and fdinfo/ directories to find opened files and seek position, and reports status for the biggest file.

  • In Search of an Understandable Consensus Algorithm - Diego Ongaro and John Ousterhout, Stanford University

    A great read. Lucid description of the replicated state machine problem, issues with Paxos, and how Raft works. Interesting that the primary goal was understandability. Maybe that should be the case for all software and algorithms ...

  • There's Just No Getting around It: You're Building a Distributed System - Mark Cavage, Joyent

    Good worked example of basic requirements & back-of-the-envelope work for an image resizing service. Separation of services, API-focused design: familiar approach.

    "the goal is simply to highlight the realities and look at the basics required to build a distributed system... Too many applications are being built by stringing together a distributed database system with some form of application, and hoping for the best."

    "Drawing parallels to a previous generation, services are the new process; they are the correct abstraction level for any discrete functionality in a system."

Generated from pinboard by pinroll.

Reading rollup, 2014-09-16.

| categories: reading

On holiday in France. It's nice here!

  • Postel's Principle is a Bad Idea. - programming is terrible

    Lots of interesting references here, and memorable quotes (as is often the way with tef's posts).

    "If some data means two different things to different parts of your program or network, it can be exploited - Interoperability is achieved at the expense of security."

    Examples from the Perl/C interface, TCP/IP, confused deputy, XSS.

    "Notably, HTML5 gained a standardized parser, not for security reasons, but to ensure that bad HTML looks the same on every browser."

    "Interoperability doesn't just mean working in the same way, but failing in the same way too."

  • How To Design A Good API and Why it Matters - Joshua Bloch

    Sensible notes on API design from someone who has very much been in the trenches.

    • Public APIs are forever: one chance to get it right.
    • Make it easy to do the right thing, difficult to the wrong thing, easy to evolve.
    • Just powerful enough to satisfy requirements.
    • Gather requirements, and make a 1-page spec. Share. Pretend to code against it. Take example programs very seriously.
    • Aim to displease everyone equally.
    • Do one thing and do it well. Good names drive development.
    • When in doubt, leave it out.
    • Don't let implementation details "leak" into API. Design serialized forms carefully.
    • Minimize accessibility of everything.
    • Documentation matters. Document everything in your public API.
    • Bad decisions can limit performance; but don't warp the API to gain performance. Good design usually coincides with good performance.
    • API must coexist peacefully with the platform: transliterated APIs are almost always broken.
    • Minimize mutability. Prefer immutable; if mutable, keep state space small & well-defined.
    • Don't make the client do anything the module could - reduce boilerplate.
    • Don't violate the principle of least astonishment.
    • Provide programmatic access to all data available in string form!
    • Use consistent parameter ordering across methods.
    • Avoid return values that demand exceptional processing (e.g. return an empty collection instead of not_found).

  • Actually using ed - Arabesque

    Cute tutorial on using ed. Fun to work through. There's a lot of other interesting stuff at this site, e.g. the "Unix as IDE" series.

  • Nine Nines Article: Erlang Scalability

    A set of notes on things that may limit an Erlang system's scalability:

    • Avoid NIFs if possible; e.g. use MessagePack rather than JSON;
    • Be careful what BIFs you use (example of erlang:decode_packet/3 in Cowboy);
    • Use binaries rather than lists, including for buffering/streaming;
    • Don't hesitate to create a custom pool of processes to do what a single gen_server might; similarly, a custom supervisor might sometimes be the right thing.
    • Use ets public or protected tables for LOLSPEED(tm).

  • How Stacks are Handled in Go - Daniel Morsing

    Clearly-written details of how goroutine stacks work (and how they soon will).

    Now: "segmented" stacks grow by allocating new segments with accounting information to find the previous outgrown. This can cause a "hot split" issue where the stack keeps growing and shrinking at the segment boundary, and releasing the new stack segment each time is expensive.

    Soon: "stack copying" creates a new segment double the size, and copies the old data to it. There's some accounting work that needs to be done here for pointers to stack data, and the Go devs are currently rewriting a pile of the runtime in Go to make this doable.

    This will also enable concurrent garbage collection in future - something which really helps in Erlang - though there are open issues with how this will work for shared heap objects in Go. I tend to prefer the Erlang shared-nothing approach ...

Generated from pinboard by pinroll.

Reading rollup, 2014-09-06.

| categories: reading

  • Debuggers: Russ Cox

    Debuggers post about a lock concurrency problem in code on Plan9. As always, Cox writes brilliantly and clearly about deep technical topics. Note the links to debugging history notes at the end.

  • The Discovery of Debugging - Brian Hayes

    Linked from rsc's article above. Great history piece on EDSAC and its first programmers.

    Software was very much the "stunted sibling" of hardware in the earliest years. "It appeared that programming might be tedious but not fundamentally difficult. A crucial discovery was yet to be made: the discovery of debugging."

    "The human reader passes over such errors without even seeing them, unconsciously filling in the intended meaning, but the machine is resolutely literal. It does only what it is told to do."

    Nice description of the hellish misery of encoding programs for the EDSAC. :o) By September 1949 (6 months in), then-student David J. Wheeler had already written a basic relocatable-code loading facility, basically a linker, amazing.

    Some really nice insight into the early days here. I wonder if there's something that comes *after* software - scalable architectures, maybe? - that we just haven't thought much about yet because we're so obsessed with the software itself.

  • Pitfalls of Object Oriented Programming - Tony Albrecht

    Deck about memory layout in high-performance games and how OO paradigms screw with optimal (columnar, for caching) layout of data in memory. Well worth a read, though these are problems I don't really want to have. :o)

Generated from pinboard by pinroll.

Reading rollup, 2014-08-26.

| categories: reading

I signed up for Pinboard a little over a month ago, finally cleared my "must read this" email labels to it, and haven't looked back. I find myself spending a lot of time in it now, reading documents and taking notes. Recommended.

Following jmason's example, I thought I'd start rolling some of the links I'm reading into blog posts, starting with older stuff.

My pins are private, so I haven't bothered including tags, and I'm doing this on a pull basis rather than daily. :o)

Generated from pinboard by pinroll.