3 ms·

First, CockroachDB's time api is based on the Hybrid Logical Clocks paper: http://www.cse.buffalo.edu/tech-reports/2014-04.pdf http://www.cse.buffalo.edu/tech-r

First, CockroachDB's time api is based on the Hybrid Logical Clocks paper: http://www.cse.buffalo.edu/tech-reports/2014-04.pdf http://www.cse.buffalo.edu/tech-reports/2014-04.pdf This paper is one of the most interesting published in the last couple of years IMO. I remain surprised at how many people have overlooked it. I'm not sure why this blog post makes no mention of the work, in the past the Cockroach folks have been quite explicit about crediting the research documents they're drawing from. Second, cloudera has a patent on this work: http://www.freepatentsonline.com/y2015/0156262.html http://www.freepatentsonline.com/y2015/0156262.html

tlipcon 11y ago
Kudu uses a similar algorithm which we call HybridTime. You can read the tech report here: http://pdsl.ece.utexas.edu/david/hybrid-time-tech-report-01.pdf http://pdsl.ece.utexas.edu/david/hybrid-time-tech-report-01.... and the source here: https://github.com/apache/incubator-kudu/blob/master/src/kudu/server/hybrid_clock.h https://github.com/apache/incubator-kudu/blob/master/src/kud... Both are probably more readable than patent-ese :)
- jasonwatkinspdx 11y ago
  I know I'm diping my toe in some history here, but is there a sense of how the patent situation is going to shake out? I think this general family of algorithm is very important.
  - tlipcon 11y ago
    Agreed -- personally I'm against offensive use of patents like this as well, and it's my understanding that Cloudera doesn't intend to use this patent offensively. If it did, I would be upset and would consider leaving the company - I know many other employees feel the same way. The reason I agree to help write patent applications as an engineer is that I've seen the distraction and damages caused by patent trolls (or even other companies) and the importance of having a defensive portfolio. Disclaimer: Obviously I'm not speaking for the company or making any promises here :) -Todd
monochromatic 11y ago
That's a pending patent application, not (yet, anyway) an actual patent.
nickpsecurity 11y ago
Far as the patent, why would one want to claim knowledge of a patent if willful infringement gives so much extra damages? ;)
hnkimb3558 11y ago
CockroachDB's time api is based on the Hybrid Logical Clocks paper. We credit it on our design doc (https://github.com/cockroachdb/cockroach/blob/master/docs/design.md https://github.com/cockroachdb/cockroach/blob/master/docs/de...) and in the source code. This blog post doesn't mention HLC because the explanation didn't require it. HLC boils down to a mechanism for taking the maximum physical wall time across >= 2 nodes, while still being able to provide monotonically increasing time via incrementing the logical component of the hybrid logical timestamp. In the blog post, this is referred to as "taking the maximum timestamp across requests". A segue into HLC would have served only to further complicate the explanation. The work done by Sandeep Kulkarni, Murat Demirbas, David Alves, Todd Lipcon, Vijay Garg, and others was instrumental to our early design efforts. I am dismayed to see there's a patent pending, though both our design and open source implementation predate the patent filing.
- tlipcon 11y ago
  FYI on the date issue, lest anyone think we filed the patent trying to steal the work done by others, the patent application says: "This application claims to the benefit of U.S. Provisional Patent Application No. 61/911,720, entitled “HYBRIDTIME and HYBRIDCLOCKS FOR CLOCK UNCERTAINTY REDUCTION IN A DISTRIBUTED COMPUTING ENVIRONMENT”, which was filed on Dec. 4, 2013, which is incorporated by reference herein in its entirety." (which predates the creation of the cockroachdb repo and the hybrid logical clock paper).
- deleted 11y ago
  [deleted]

tlipcon 11y ago

Kudu uses a similar algorithm which we call HybridTime. You can read the tech report here: http://pdsl.ece.utexas.edu/david/hybrid-time-tech-report-01.pdf http://pdsl.ece.utexas.edu/david/hybrid-time-tech-report-01.... and the source here: https://github.com/apache/incubator-kudu/blob/master/src/kudu/server/hybrid_clock.h https://github.com/apache/incubator-kudu/blob/master/src/kud... Both are probably more readable than patent-ese :)

jasonwatkinspdx 11y ago
I know I'm diping my toe in some history here, but is there a sense of how the patent situation is going to shake out? I think this general family of algorithm is very important.
- tlipcon 11y ago
  Agreed -- personally I'm against offensive use of patents like this as well, and it's my understanding that Cloudera doesn't intend to use this patent offensively. If it did, I would be upset and would consider leaving the company - I know many other employees feel the same way. The reason I agree to help write patent applications as an engineer is that I've seen the distraction and damages caused by patent trolls (or even other companies) and the importance of having a defensive portfolio. Disclaimer: Obviously I'm not speaking for the company or making any promises here :) -Todd

monochromatic 11y ago

That's a pending patent application, not (yet, anyway) an actual patent.

nickpsecurity 11y ago

Far as the patent, why would one want to claim knowledge of a patent if willful infringement gives so much extra damages? ;)

hnkimb3558 11y ago

CockroachDB's time api is based on the Hybrid Logical Clocks paper. We credit it on our design doc (https://github.com/cockroachdb/cockroach/blob/master/docs/design.md https://github.com/cockroachdb/cockroach/blob/master/docs/de...) and in the source code. This blog post doesn't mention HLC because the explanation didn't require it. HLC boils down to a mechanism for taking the maximum physical wall time across >= 2 nodes, while still being able to provide monotonically increasing time via incrementing the logical component of the hybrid logical timestamp. In the blog post, this is referred to as "taking the maximum timestamp across requests". A segue into HLC would have served only to further complicate the explanation. The work done by Sandeep Kulkarni, Murat Demirbas, David Alves, Todd Lipcon, Vijay Garg, and others was instrumental to our early design efforts. I am dismayed to see there's a patent pending, though both our design and open source implementation predate the patent filing.

tlipcon 11y ago
FYI on the date issue, lest anyone think we filed the patent trying to steal the work done by others, the patent application says: "This application claims to the benefit of U.S. Provisional Patent Application No. 61/911,720, entitled “HYBRIDTIME and HYBRIDCLOCKS FOR CLOCK UNCERTAINTY REDUCTION IN A DISTRIBUTED COMPUTING ENVIRONMENT”, which was filed on Dec. 4, 2013, which is incorporated by reference herein in its entirety." (which predates the creation of the cockroachdb repo and the hybrid logical clock paper).
deleted 11y ago
[deleted]