News for hackers. Stuff that matters.
Re:Writing a very fast cache service with millions of entrie... by endymi0n on Wednesday March 30, 2016 @08:36AM (#11388757)
I still don’t get why people try writing their own data store, especially in a language that's simply not very well suited to that task (and we're an almost 100% Golang shop here). Seems to be a rite of passage.

The requirements are literally <100LOC of wrapping an HTTP interface around Redis with using TTL - which has been battle tested for years and is both rock solid and ridiculously fast.

Public service announcement: Don't write your own data store. Repeat after me: Don't write your own data store, except if you want to experimentally find out how to build data stores. It's arbitrarily hard and gets even more so at every layer. Plus, you leave behind an unmaintainable mess for the people after you. There's already a great OSS data store optimized for every use case and storage medium I could possible imagine.

Re:Writing a very fast cache service with millions of entrie... by im_down_w_otp on Wednesday March 30, 2016 @11:45AM (#11390122)
There are two datastores I would really like that don't exist.

1) An efficient, high-performance distributed persistence store for arbitrarily large CRDT's.

2) A Kafka-like highly-available distributed binary log w/ cheap topics, that doesn't require external coordination, and doesn't lose acknowledged writes (which I'll happily give up any shape of linearization guarantee for).

Re:Writing a very fast cache service with millions of entrie... by lobster_johnson on Wednesday March 30, 2016 @02:06PM (#11391554)
Riak does CRDTs (not sure about arbitrarily large), though I never understood their reasoning for requiring that CRDTs be pre-registered in a schema — it's a major drawback in an otherwise schemaless K/V store.
Re:Writing a very fast cache service with millions of entrie... by im_down_w_otp on Wednesday March 30, 2016 @03:08PM (#11392038)
But they're also required to be relatively small, because of how they're treated on disk and inside the system as opaque at the storage layer. As a result of this, and a smattering of other reasons, they're also not very fast.
Re:Writing a very fast cache service with millions of entrie... by endymi0n on Wednesday March 30, 2016 @12:08PM (#11390293)
can't help with 1), but as for 2), maybe Kudu is an option for you? http://blog.rodeo.io/2016/01/24/kudu-as-a-more-flexible-kafk...
Re:Writing a very fast cache service with millions of entrie... by im_down_w_otp on Wednesday March 30, 2016 @12:57PM (#11390809)
Uses Raft. Not highly-available enough unfortunately. Availability > Consistency for the use case that matters to me (basically a service message bus where all ACK'd writes will eventually be read by some consumer(s), but I don't care when or in what order, just that they all eventually get consumed, and where as long as any node in the cluster is up, it'll ACK a write).
Re:Writing a very fast cache service with millions of entrie... by Xorlev on Wednesday March 30, 2016 @01:20PM (#11391046)
> just that they all eventually get consumed

Unless you have some sort of replication or consensus, this is still just best-effort delivery. For example, the message could be acknowledged & fsynced followed by drive death. At scale, this would happen.

However, with asynchronous best-effort replication, broker death would be much less likely to lead to a loss of messages.

In general, it's all about playing the odds. Acknowledged writes can still be lost in the best of systems if the entire DC catches fire.

If you tune Kafka settings, you essentially get this behavior. You have to ensure ZK is up, but it will allow all topics to be published to so long as a single broker is alive.

Re:Writing a very fast cache service with millions of entrie... by im_down_w_otp on Wednesday March 30, 2016 @01:50PM (#11391384)
If I tune my Kafka settings I can't get this behavior.

The closest I can get is allowing sloppy leader election, but that will definitely, definitely lose writes that have been ACK'd by a stale leader who comes back and has to become a follower. So I can get Kafka to basically accept all writes regardless of level of cluster degradation, but I can't keep it from dropping some of those writes silently onto the floor.

Re:Writing a very fast cache service with millions of entrie... by jasonwatkinspdx on Wednesday March 30, 2016 @06:06PM (#11393402)
> Uses Raft. Not highly-available enough unfortunately.

Did you test this or is it just a general view? What sort of write rate are you looking for, per topic?

Re:Writing a very fast cache service with millions of entrie... by im_down_w_otp on Wednesday March 30, 2016 @08:08PM (#11394024)
Raft requires both a stable leader and a majority of replicas to be reachable in order to advance the consensus protocol. I'd like to be able to lose more than a majority of replicas and require no leaders because I don't care about consistency.

I care that as long as even one node in the system is alive, it will accept writes, and those writes will eventually propagate and converge on the union set of all writes ever observed, without obliterating any ACK'd observed writes, as the system as a whole moves toward a less degraded state.

I'd want topics themselves to be able to be basically "free" to create, and the write latency to remain stable over arbitrarily large datasets. Write rate isn't really much of a consideration since it's almost embarrassingly low (hundreds per second).

Re:Writing a very fast cache service with millions of entrie... by jasonwatkinspdx on Wednesday March 30, 2016 @11:49PM (#11394858)
> I don't care about consistency.

Fair nuff, I asked because I was curious if you were assuming that eventual consistency was necessary for high availability.

> Write rate isn't really much of a consideration since it's almost embarrassingly low (hundreds per second).

Yup, looks like my concern above is the case. A single consensus replica set will do that no problem. I'd use raft if you're in a single geo location or epaxos otherwise (the epaxos source is a little early and needs eyeballs/production diversity testing, but the algorithm is absolutely solid). There's no reason to borrow all the troubles of CRDT's when it's not needed.

Edit:

Example from the epaxos paper, this is latency vs throughput for 3 replicas in one geo location: http://charap.co/wp-content/uploads/2015/10/latency_over_thr...

Re:Writing a very fast cache service with millions of entrie... by im_down_w_otp on Thursday March 31, 2016 @01:00AM (#11395083)
What happens when I don't have a majority of Raft replicas alive?
Re:Writing a very fast cache service with millions of entrie... by jasonwatkinspdx on Thursday March 31, 2016 @11:25AM (#11397839)
Then raft locks until you do again. We live in the era of on demand infrastructure. With even just 3 replicas and some reasonable automation it's extremely unlikely you'll see any unavailability. Or run 5 way across two different systems (ie 3 at google, 2 at AWS). That setup is less than $100/month to run now.

You seem extremely concerned about a fault tolerant system experiencing more faults than the majority, which I think is quite easily dealt with, and utterly blithe about making inconsistency your best case.

At this kind of request rate I'd honestly just shove things in postgres and call it good. There's just no reason to build out a bunch of CRDT complexity when you don't _need_ it.

Re:Writing a very fast cache service with millions of entrie... by im_down_w_otp on Thursday March 31, 2016 @11:49AM (#11398015)
The system that's my benchmark to go up against has seen 6 seconds of downtime in 25 years.

Does that give you a better perspective for my availability concerns?

I also don't have "on demand" infrastructure. I have to deploy to a fixed footprint of bare metal hardware.

I'm "utterly blithe" about inconsistency being my best case for a variety of reasons:

1) I know my use case extremely well.

2) I know that within that use case there are several places where availability is the #1, #2, and #3 priority because the system being unavailable for any time at all has a non-trivial direct financial impact.

3) I know within that use case where there are necessary points of consistency and how to move them out of the critical path that requires extreme availability.

4) I know exactly the problem that CRDTs solve for me, and exactly why I need them in this case, and how to avoid them with simpler immutable/idempotent write patterns where possible.

5) I have to be able to tolerate very high proportion of the infrastructure experiencing temporary and/or permanent failure because the places I have to deploy into are no where near the level of reliability of even a low-mid tier data center in the US. Janky telcos, natural disasters, malicious operators, and flimsy power delivery are the norm.

Re:Writing a very fast cache service with millions of entrie... by jasonwatkinspdx on Thursday March 31, 2016 @12:01PM (#11398140)
And what consistency assurances does it provide?

Edit: I see you edited in a longer comment after my question above. I was just curious, not looking to pick a fight. Suffice it to say we have very different perspectives on how to attack those requirements. I'm bowing out now, cheers!.

Re:Writing a very fast cache service with millions of entrie... by im_down_w_otp on Thursday March 31, 2016 @01:28PM (#11398904)
The problem is this:

1) Anything that is suggested which avoids data loss via consistency models is going to reduce my availability to unacceptable levels.

2) Anything that is suggested which keeps my availability up where it needs to be and doesn't use CRDTs, and/or a sufficiently similar semantic guarantee, is going to silently lose data due to "lost-updates" (ACK'd writes that get obliterated during conflict merges and are now gone forever).

At a minimum I need sibling behavior for conflicting writes to ensure that some half-baked LWW strategy that's barely better than "pick at random" doesn't kill my data (which has very high regulatory and audit requirements around it), and then taking that a step further CRDTs, implemented correctly, provide me a nice interface for interacting with multiple version conflicts and resolving them in coherent ways without forcing me, or my other developers, to have to think up case-by-case resolution strategies and verify their correctness.

There really isn't a tremendous amount of complexity to using CRDTs. That's the point of them. They're easy to use. The complexity I'd really like to avoid if possible by avoiding CRDTs is the cognitive burden my team needs to have around distributed data and all it's horrible nuances to satisfy our use case. The knowing when and why to use them, not so much the how.

"At this kind of request rate I'd honestly just shove things in postgres and call it good." is very, very far away from a workable solution because my problem isn't request rate. The number of ops/sec could be hundreds or millions, and it doesn't really change my actual problem. No matter what the request rate is I could just write to a bunch of postgres instances that have a chash ring overlaid onto them... except now I have to deal with my actual problem still, which is redundancy, and local consistency in any postgres replica doesn't guarantee me much, I can't introduce a strong coordinator like a consensus protocol over the top of them, because it dumps my availability, and so I have to figure out how to safely deal with merge conflicts between the replicas... now I'm stuck figuring out how to build CRDTs on top of postgres anyway. So... what exactly did I win?

Re:Writing a very fast cache service with millions of entrie... by chris_va on Wednesday March 30, 2016 @12:26PM (#11390449)
(1) Spanner does exist, though not really available outside of Google
Re:Writing a very fast cache service with millions of entrie... by atomic77 on Wednesday March 30, 2016 @12:42PM (#11390622)
CockroachDB is probably the closest system to spanner that I've come across (and built in Go)

https://github.com/cockroachdb/cockroach

Re:Writing a very fast cache service with millions of entrie... by im_down_w_otp on Wednesday March 30, 2016 @12:50PM (#11390730)
Yes, Spanner does exist. Spanner also does not satisfy what I said in #1.
Re:Writing a very fast cache service with millions of entrie... by QuercusMax on Wednesday March 30, 2016 @04:13PM (#11392589)
Can you elaborate on this?
Re:Writing a very fast cache service with millions of entrie... by im_down_w_otp on Wednesday March 30, 2016 @06:19PM (#11393480)
Well, for starters Google Spanner has almost nothing to do with CRDTs.

For another it would be really weird for Spanner to expose something CRDT shaped since Spanner is a strongly-consistent distributed database which depends heavily on global order and read/write locks driven by meticulously coordinated multi-site global wall-clock time and consensus groups.

In some ways it's almost the opposite of what I want... with exception of the fact that it's also distributed. I want extreme availability with lazy, weak coordination.

Re:Writing a very fast cache service with millions of entrie... by chris_va on Thursday March 31, 2016 @12:23PM (#11398347)
Read/write locks...

No, it's slightly more lazy in that that. It does timestamp coordination, but retrospectively.

Re:Writing a very fast cache service with millions of entrie... by im_down_w_otp on Thursday March 31, 2016 @01:48PM (#11399070)
You mean except for the lock table that's maintained by every paxos leader?
Re:Writing a very fast cache service with millions of entrie... by Maascamp on Wednesday March 30, 2016 @10:52AM (#11389674)
Not sure if this applies to their use case since they mention FIFO in the context of it being a simple eviction policy, but if you _require_ FIFO semantics then both Redis and memcached are out of the question since they use nondeterministic LRU policies (memcached's LRU is particularly egregious in its nondeterminism due to the way slab allocation works).
Re:Writing a very fast cache service with millions of entrie... by krenoten on Wednesday March 30, 2016 @01:08PM (#11390930)
this is rarely a concern for things that are ephemeral in nature to begin with. it's also a 20 line code change to add a similar ttl buffer into memcached.
Re:Writing a very fast cache service with millions of entrie... by tmaly on Wednesday March 30, 2016 @10:52AM (#11389684)
I used Redis with Go and I was very happy with the results. I did have one case where I used boltdb.

I run things on a lean vps, and I had a large amount of data I tried to stuff in a trie. Well it worked fine on my macbook with plenty of memory, but it ran out of memory on my vps. Using bolt helped in this case with the memory mapped file.

Re:Writing a very fast cache service with millions of entrie... by maleck13 on Wednesday March 30, 2016 @01:35PM (#11391213)
Can you explain further why golang is bad for data stores, do you mean cache in particular? Seems contrary to many of the new datastores that I see being developed: etcd[1] , cockroachdb[2], influxdb[3] just to name a couple that are written in go.

[1]https://github.com/coreos/etcd [2]https://github.com/cockroachdb/cockroach [3]https://github.com/influxdata/influxdb

Re:Writing a very fast cache service with millions of entrie... by endymi0n on Wednesday March 30, 2016 @05:46PM (#11393288)
Go is awesome, but has very few facilities for effectively working very close to the machine and memory - you can't skip the runtime or GC. Of course, this mostly affects high throughput, high mutation rate, high memory use data stores. Eventually, you'll end up fighting the garbage collector all the time. ETCD isn't directly affected as it isn't so affected as it's not really about larger data or performance, cockroachdb is still more proof-of-concept of a pretty gigantic (though promising) architecture and Influx has honestly been an imperformant mess for us in Prod so far. It's not that it's not possible to write a decent data store in Go, but eventually, as your GC runs wild from the purposefully simple and naive stdlib implementations of maps for example, the neccessary solutions of aggressive pooling or mmapping off-heap space and writing your own allocators for it (while constantly casting something from and to *unsafe) will suck you deep down the rabbit hole and wish you had written it in C(++) or Rust in the first place.
Re:Writing a very fast cache service with millions of entrie... by markbnj on Wednesday March 30, 2016 @11:54AM (#11390202)
Sort of came here to say this. Interesting article, especially some of the design choices (such as http for the interface), but I am most curious as to why redis, or memcached, or some other k/v store was not good enough?
Re:Writing a very fast cache service with millions of entrie... by atomic77 on Wednesday March 30, 2016 @12:38PM (#11390575)
I wanted to like this article. But this:

> Considering the first point we decided to give up external caches like Redis, Memcached or Couchbase mainly because of additional time needed on the network.

Even mysql+innodb can easily handle 10k read/write queries against a simple pk table with "millions of entries" on desktop-grade hardware.

If the article was "here's a fun experiment to make a cache server in Go", fair enough.

Re:Writing a very fast cache service with millions of entrie... by jakub_h on Wednesday March 30, 2016 @03:02PM (#11391994)
That sounds a little bit harsh (even if I ignore the claims of unsuitability of Go for that purpose). What if I want to write, for example, a Go port of DataDraw? Perhaps with profiling-based memory layout optimization thrown in? And maybe even caching/lazy/caching+lazy collections/maps. If I were obeying your recommendations verbatim, I'd probably still be using mainframe libraries.
Re:Writing a very fast cache service with millions of entrie... by andersen1488 on Friday April 01, 2016 @09:58AM (#11404768)
> Don't write your own data store

I wish more people had this attitude. The amount of times I have seen people re-implementing something that PhD's have been perfecting since the 70's... it's cringe worthy.