[ANN] interval tree clock

[stephan.h...@gmail.com]

Hi there,

I've studied a paper about interval tree clocks lately and had a lot of fun to implement it in golang.

Results here: https://github.com/fgrid/itc

I'd really like to get some feedback.

Best regards,

Stephan Heinze.

[Jonathan Lawlor]

I've never used or written distributed event ordering code, so take my feedback with a huge grain of salt, or perhaps as a request for clarification instead of criticism.

"nitpick-y" stuff:

Almost none of the public types or functions are commented, which makes it a bit harder to work through the code.  I'd definitely have an easier time with it if you had done so.  It is succinct enough that I didn't have a huge amount of trouble though.

Many of the functions both modify inputs and return them, which looks odd to me.  See for example:

func (s *Stamp) enc(packer *BitPacker) *BitPacker {
s.id.enc(packer)
s.event.enc(packer)
return packer
}

It is obvious from examining the code that the BitPacker returned is the same as the input, which begs the question of why it was returned at all.  I would suggest this instead:

func (s *Stamp) enc(packer *BitPacker) {
s.id.enc(packer)
s.event.enc(packer)
}

Also, the name "BitPacker" is not idiomatic.  Usually names with -er suffixes are intended to be interfaces with a single method - see the Stringer interface, which is satisfied by types which implement a String method.  In BitPacker's case, it is a type instead of an interface, and there is no BitPack method.

I'm also a little concerned about the grow(i *id, e *event) function, which seems to have a magic number 99,999 in it, which gets sent to an ignored output later on?  I don't know what's happening there.

On to more interesting stuff that I know substantially less about:

How do you think this would fit into the typical Go method of determining causality - specifically, channels?  Do you see this being used as a synchronization method among pools of goroutines that communicate with each other (basically, the actor model)?  Do you think it would be composed with other types, and then sent along the channels?  It would be very interesting to me to see an example using goroutines to see what kind of idioms show up.  How would you handle cases where sending a clock update to another goroutine blocks?

In any case, I found this quite interesting to read and I'll probably go through the code & paper a few more times.

[Stephan Heinze]

I've never used or written distributed event ordering code, so take my feedback with a huge grain of salt, or perhaps as a request for clarification instead of criticism.

That's exactly what I want :-)

 

"nitpick-y" stuff:

Almost none of the public types or functions are commented, which makes it a bit harder to work through the code.  I'd definitely have an easier time with it if you had done so.  It is succinct enough that I didn't have a huge amount of trouble though.

Gotcha. You're right - my bad.

Many of the functions both modify inputs and return them, which looks odd to me.  See for example:

func (s *Stamp) enc(packer *BitPacker) *BitPacker {
s.id.enc(packer)
s.event.enc(packer)
return packer
}

Aye - that might look odd, but it's with purpose to enable method chaining. In stamp.Pack() is such a chain:

func (s *Stamp) Pack() []byte {
 return s.enc(NewBitPacker()).Pack()
}

 

It is obvious from examining the code that the BitPacker returned is the same as the input, which begs the question of why it was returned at all.  I would suggest this instead:

func (s *Stamp) enc(packer *BitPacker) {
s.id.enc(packer)
s.event.enc(packer)
}

Also, the name "BitPacker" is not idiomatic.  Usually names with -er suffixes are intended to be interfaces with a single method - see the Stringer interface, which is satisfied by types which implement a String method.  In BitPacker's case, it is a type instead of an interface, and there is no BitPack method.

I see. I'll have to find a better name for those 2: BItPacker/BItUnPacker.

 

I'm also a little concerned about the grow(i *id, e *event) function, which seems to have a magic number 99,999 in it, which gets sent to an ignored output later on?  I don't know what's happening there.

You're right - that's short cut ... the paper states "a large constant - larger than tree height". That's a TODO.

And the output is NOT ignored. It's the 'cost' of the operation and this has impact in which order the left/right trees will grow.

 

On to more interesting stuff that I know substantially less about:

How do you think this would fit into the typical Go method of determining causality - specifically, channels?  Do you see this being used as a synchronization method among pools of goroutines that communicate with each other (basically, the actor model)?  Do you think it would be composed with other types, and then sent along the channels?  It would be very interesting to me to see an example using goroutines to see what kind of idioms show up.  How would you handle cases where sending a clock update to another goroutine blocks?

In any case, I found this quite interesting to read and I'll probably go through the code & paper a few more times.

I think, it's about distributed systems in the meaning of different machines, processes or may be goroutines. The noSQL database cassandra synchronizes hearbeat-state and application-state between nodes with version vectors .... one use case for such an ITC.

Thank you so much for your feedback.

[Stephan Heinze]

I've pushed some updates right now.

Tried to clarify the exported API.

Added little documentation and renamed examples to appear in godoc too.

Learned a lot.

Remaining TODOs: The magic constant (tree height) and discussion about method chaining.

Is method chaining against the 'usual' golang-style?

[Carlos Castillo]

Method chaining isn't strictly against go-style, but there are three problems I can see:

1. Method chaining is less common in go due to multiple return values, and their importance in error handling. If you return two or more values, you can't chain the calls and/or handle the error. If you forgo returning an error (or panic instead) it is seen often as a poor design choice. The exception in this case being Must* functions (see regexp or text/template), which give the user a tool to either accept panic on failure (and enabling chains) or write standard error handling code.
2. This isn't *method* chaining anyway, since the method is returning a parameter passed to the call, whereas most method chaining involves methods returning their receiver, or a field of the receiver. As a result this behaviour is somewhat unexpected.
3. Go favours code clarity / readability over terseness. Method chaining when obvious doesn't strictly violate this, but the odd chaining pattern (see #2) makes it hard to follow what's going on, and client code could be considered clearer when represented in multiple lines instead of trying to take advantage of the chaining method provided.

[Ibrahim M. Ghazal]

Another reason is gofmt. I find method chaining interacts badly with
automatic code formatting, especially when the code formatter wraps
lines or joins split lines .

> --
> You received this message because you are subscribed to the Google Groups
> "golang-nuts" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to golang-nuts...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

[Stephan Heinze]

You're right - looks 'cleaner' without chaining.

Will have to think about error handling.