Tango-style backpointers, checkpoint data, and splicing

In the corfurl + Tango prototype in the Machi source code repo, I started work on a mechanism that would “splice” the backpointers to point to a checkpoint that was itself stored in the CORFU log.

New mutations can be interleaved in any order with the checkpoint data (avoiding a checkpoint-must-fit-in-fixed-number-of-pages problem and also a damn-we-cannot-store-our-checkpoint-inside-of-CORFU problem). New data pages and checkpoint data pages can be interleaved in any order.

Labels for CORFU page numbers 0-10 appear below below each page name. Also, to clarify the ASCII art:

backpointer-example

  • cpdata-B points to cpdata-A (page 7 -> page 5).
  • cpdata-A points to checkpoint-start (page 5 -> page 3).
  • new2 points to new1 (page 6 -> page 4)
  • cpdata-B doesn’t have a Tango backpointer pointing to it, except for the splice semantics of the checkpoint-done page.

In an ideal world, the ‘checkpoint-done’ has some ‘splice’ info that says when you follow a backpointer to old2’s page, then do not go there but instead go to cpdata-B’s page and follow the backpointers only as far as checkpoint-start.

The result: new4 -> new3 -> checkpoint splice info, let’s remember that!
-> new2 -> new1 -> Hey! Our splice memory says to jump elsewhere
-> cpdata-B -> cpdata-A -> checkpoint-start -> HALT

And in the reverse direction, we have exactly our two checkpoint pages, in order, followed by four new pages, in order.

If the checkpoint-done page is never written, then backward traversals will never see the checkpoint data pages or checkpoint-start. It’s as if they don’t exist. They don’t, because they’re never spliced into the backpointer chain. The GC needs to be aware of this, though. The GC process would have to keep a map of, “Hey, I skipped some pages entirely, perhaps I should GC them….?”

That would probably work, right? {shrug} Not fully implemented, tested, or proven. Useful? Not sure, probably?

For more information:

Posted in Uncategorized | Tagged | Comments Off on Tango-style backpointers, checkpoint data, and splicing

Protected: Eavesdropping on a September 2015 discussion about Chain Replication

This content is password protected. To view it please enter your password below:

Posted in Uncategorized | Tagged , , | Comments Off on Protected: Eavesdropping on a September 2015 discussion about Chain Replication

Protected: The first sake/nihonshu that I loved

This content is password protected. To view it please enter your password below:

Posted in Uncategorized | Tagged , , , | Comments Off on Protected: The first sake/nihonshu that I loved

Moving to Tokyo and making choices about language study

“It’s odd, not everyone speaking English here.  It’s almost as if this weren’t America at all.”  — Me, joking very intentionally while thinking of The Onion news article, “Perky ‘Canada’ has its own government, laws”.

Joking aside, my work environment doesn’t force me to use Japanese, so I have the luxury of choice. I have nothing but deep respect for émigrés, ex-pats, refugees, and migrants who find themselves in a sink-or-swim language “school” of hard-knocks-life.

Back when I first started visiting Japan on business trips, my boss was Chinese by way of Australia and the United States and now living in Tokyo.  He had a theory about learning Chinese and Japanese written language.  He believed that, after a certain age, children lost the ability to learn the “pattern matching” that reading & understanding Japanese or Chinese requires.  After all, there are a bit over 2,000 different kanji characters that all Japanese high school students are required to master by graduation day. For example, “graduation day” could be written “卒業式の日” in Japanese kanji. Continue reading

Posted in Uncategorized | Tagged , | Comments Off on Moving to Tokyo and making choices about language study

A third year in Japan

This week marks the beginning of our third year living and working in Japan.  Thanks, Louise, for pushing me to leave Minneapolis for a while.  The last two years have been gratifying, tremendously delicious, educational, routine, and … aw, enough of the adjective festival.  Many thanks, Uncle Basho, for sending us here and giving me and opportunity to work with amazing people!

I’ve got a lot of wish list items added to my “todo before leaving Japan” list. (It just keeps getting longer and longer….)  One that hopped to the top of the list has been a deeper exploration of hobby photography.  Let me digress for a moment. Continue reading

Posted in None-of-the-above | Tagged , , | Comments Off on A third year in Japan

Humming consensus, an animated example with an asymmetric network partition

Hi, all.  It’s been a happy & productive day working on some new code.  I’ve done it brute-force style, but it’s nice to see results.  Visual images are cool, and animation is very cool.  My animation quality is horrible, so that reduces coolness to something mediocre.  But I’m still excited because it’s a first!  It’s my first animated case study of humming consensus.  It’s also my first description of a case study, please don’t let that stop you from reading more.

Continue reading

Posted in Uncategorized | Tagged , | Comments Off on Humming consensus, an animated example with an asymmetric network partition

On “Humming Consensus”, an allegory, part 2

Part 2, you ask?  There isn’t a part 2.  The Lamport fan fiction ends at part 1, I’m sorry.

The good news is that there’s something more concrete than allegory to follow up on.  The work is still in progress, but the description over at the Machi source repository at GitHub is place to look.  That link is fixed at a version as of mid-March 2015.  If you’d like to see the latest version instead, give it a try.

 

Posted in Uncategorized | Tagged , , | Comments Off on On “Humming Consensus”, an allegory, part 2

On “Humming Consensus”, an allegory

“We reject kings, presidents, and voting.
We believe in rough consensus and running code.”

— David Clark, about the IETF

And to quote a paragraph from the introduction of https://tools.ietf.org/html/rfc7282:

To reinforce that we do not vote, we have also adopted the tradition of “humming”: When, for example, we have face-to-face meetings and the chair of the working group wants to get a “sense of the room”, instead of a show of hands, sometimes the chair will ask for each side to hum on a particular question, either “for” or “against”.

In my imagination, I see a kind of humming consensus, somewhat in the sprit of the IETF’s humming consensus. A network partition means that not all participants can hear the pitch/notes of the hummers on the other side of the partition. Yet despite partitions where not everyone can hear everyone else, we can determine a rough consensus that is good enough to solve some distributed systems problems.

Continue reading

Posted in None-of-the-above | Tagged , , | 1 Comment

Hand-crafted IP packets with Form RFC 791

In a fit of silliness, I wrote a Tweet earlier today:

Hand-crafted IP packets with Form RFC 791: “Print legibly and press hard. You are making up to 255 copies.”

It’s probably the most popular Tweet I’ve ever written.  The image to go along with it is an oldie but a goodie, which probably explains why it’s been such a big hit.

rfc791-formHere is a link to the original Tweet.
Edit 2014-05-26: I am flabbergasted. As of today, Twitter claims that message has had 86.5K total views, 1,945 retweets, and 1,145 favorites. If only I were one tenth as witty as that Post-It note….
^-^

Posted in None-of-the-above | Tagged | Comments Off on Hand-crafted IP packets with Form RFC 791

Irises!

This gallery contains 10 photos.

Lots of irises, last June at the Koishikawa Korakuen garden, near the Tokyo Dome stadium.  (a.k.a., a demo try explore the use of the WordPress gallery feature).

More Galleries | Comments Off on Irises!