11 ms·
God: Scalable in Memory Data Structure Server in Go
- fusiongyro 14y agoNot to be confused with god the Ruby process monitor: http://godrb.com/ http://godrb.com/ Also, great choice for searchability: "go god." You guys are so clever!
- LeafStorm 14y agoAnd that's not even getting into the Third Commandment issues.
- koenigdavidmj 14y agoAnd interestingly enough, your account is 666 days old today.
- jlgreco 14y agoRemember the sabbath, and keep it holy?
- riffraff 14y agoTen commandments are wildly inconsistent http://www.biblicalheritage.org/bible%20studies/10%20commandments.htm http://www.biblicalheritage.org/bible%20studies/10%20command...
- deleted 14y ago[deleted]
- fusiongyro 14y agoThat's not what any reasonable person would call "wildly inconsistent," though it is certainly enough to make the author's point.
- riffraff 14y agoto be honest, that is the first result I found looking on google for "ten commandments jews"[0]. Sure, as another (apparently deleted?) comment said, if you take them as a whole you more or less can respect 80% of it across a few major branches. But they are inconsistent enough that if I tell you one by number there's a 80% chance that you won't be able to understand what I mean unless you know my religion, which is the case i replied to. [0] I first found out that what the roman catholic catechism taught to me (in rome :) as VI, "do not commit impure acts", is different for jews.
- fusiongyro 14y agoIn that case, fair enough.
- jlgreco 14y agoInteresting, apparently as a former Lutheran I learned the Catholic version. Seems it is even worse than that link suggests though, as there are two texts which are considered to be the 10 commandments: http://en.wikipedia.org/wiki/Ten_Commandments#Two_texts_with_numbering_schemes http://en.wikipedia.org/wiki/Ten_Commandments#Two_texts_with... How was I not aware of this...
- fusiongyro 14y agoBecause Christians are generally speaking quite ignorant of the Old Testament, and not infrequently the New as well. Every religious Jew on earth is well aware of this, and if you read the two versions side-by-side you'll see the differences are stylistic and not substantive--the shade of difference between "honor" and "love" or "remember" and "observe" is just not that great, though our practices often are explained as owing to these distinctions. If you are looking for something about the Bible to be upset about, you can certainly do a lot better than this.
- jlgreco 14y ago"The 10 Commandments" and/or the Bible itself upset me for other reasons. In this particular case I am only upset by my own ignorance.
- packetslave 14y agoSearching for [golang foo] has been the recommended strategy for almost as long as Go has been around.
- astrodust 14y agoYet another terrible name for a software package.
- deleted 14y ago[deleted]
- laureny 14y agoCan't be harder to look up than "Go".
- magicarp 14y agoTry looking up anything for R
- Uchikoma 14y agoFirst hit for googling "R api" is "Writing R Extensions". Looks pretty easy googling for R to me.
- mweibel 14y agoActually that would be a neat search engine idea: Targeted at programmers, you can specify the language the library/question/tutorial/etc. should be written in and it searches only websites related to this.
- zond 14y agoYup, I am not happy about the name. It has its root in 'Go database', and began as a working name that I never had time to replace...
- JulianMorrison 14y agoYou could call it Ghord
- zond 14y agoSounds gristly :O
- JulianMorrison 14y agoSounds totally metal. Ghord the conqueror.
- shin_lao 14y agoThe Chord algorithm sounds like a very good choice, however I'm more skeptical about the radix tree approach. I fear you might get a huge performance penalty.
- kibwen 14y agoI'm no data structures expert (far from it), but via hearsay I've only heard good things about radix trees. Care to elaborate?
- amalcon 14y agoRadix trees are great, with the right workload. The main competition (for strings) are the ternary search tree (for sparse keyspaces with rare insertions) and the B-Tree (which is nominally disk-optimized, but that optimization also tends to help with the L3 cache). None of those are best for all workloads. There are situations where using a radix-tree is actually faster than a hashtable with a good hash function, and situations where it is slower than a red-black tree.
- zond 14y agoI would have preferred other algorithms, but there was a strict need for 1) sorted data and 2) that 2 identical trees had the same structure (for the merkle element). Not many structures were left to choose from, and radix seemed to work well enough.
- shin_lao 14y agoMy concern is that you're mixing two different concepts. Do you really need data to be ordered? Why do you care about having "close" data on the same node?
- zond 14y agoThe synchronization uses Merkle trees, and they require ordered data since they hash contiguous data into a tree of hashes. And to avoid having a separate structure for the Merkle trees I just hash all nodes in the main tree, and compare the hashes to find differences. Thus the same content must have the same structure, or the comparisons won't work.
- vph 14y agoobvious question: how is this compared to Redis?
- zond 14y agoHard to know. It seems to perform comparably, anyway, at single node level. I have yet to find a bunch of equally powerful machines to perform a proper scalability benchmark :/
- JulianMorrison 14y agoCan it be run in-process from Go as a library?
- JulianMorrison 14y agoAnd also, can it be run in diskless mode (no logging, no snapshotting)?
- zond 14y agoYes, it isn't documented (for some reason, I must have forgot) but https://github.com/zond/god/blob/master/dhash/dhash.go#L109 https://github.com/zond/god/blob/master/dhash/dhash.go#L109 shows how the empty string as persistence directory will avoid any persistence.
- zond 14y agoYes, look at https://github.com/zond/commendable https://github.com/zond/commendable which is a real life project I am basing on god (as an exercise, showcase and test run).
- clumsybull 14y agoArg, should not have chosen that name: http://godrb.com/ http://godrb.com/
- Whitespace 14y agoI haven't read the article, but the claim of MurmurHash3 having low collision rates is false: you can generate an arbitrary quantity of collisions according to [0]. When this was released last year, ruby[1], jruby[2] and rubinius[3] all switched to siphash[4]. Looking at [5] mentions tomcat, .NET, PHP, etc. all switching away from MurmurHash. (I'm not saying one would HashDoS one's own database, I'm merely pointing out that MurmurHash3 wasn't _designed_ with low collision rates in mind [siphash is, though]) [0] http://emboss.github.com/blog/2012/12/14/breaking-murmur-hash-flooding-dos-reloaded/ http://emboss.github.com/blog/2012/12/14/breaking-murmur-has... [1] http://www.ruby-lang.org/en/news/2012/11/09/ruby19-hashdos-cve-2012-5371/ http://www.ruby-lang.org/en/news/2012/11/09/ruby19-hashdos-c... [2] http://jruby.org/2012/12/03/jruby-1-7-1.html http://jruby.org/2012/12/03/jruby-1-7-1.html [3] https://github.com/rubinius/rubinius/commit/a9a40fc6a1256bcf6382631b710430105c5dd868 https://github.com/rubinius/rubinius/commit/a9a40fc6a1256bcf... [4] https://131002.net/siphash/ https://131002.net/siphash/ [5] http://web.nvd.nist.gov/view/vuln/detail?vulnId=CVE-2011-4815 http://web.nvd.nist.gov/view/vuln/detail?vulnId=CVE-2011-481... [edit: formatting]
- tveita 14y ago> MurmurHash3 wasn't _designed_ with low collision rates in mind There is a difference between "low collision rate" and "collision resistance". Real-world data often contain regular patterns that can cause "bad" hash functions to give very non-random output, e.g. numbers at fixed intervals, pointers all aligned to 4k boundaries, or long strings that differ only by a short suffix. For instance, early versions of Java would sample only a few of the characters in a long string to calculate the hash code, which caused horrendous performance if you stored a bunch of related file paths in a hash map. Most hash functions try to avoid bad behaviour on this kind of good-natured input, but some are better at it than others, due to careful design for random-like distribution, and low collision rates. http://www.strchr.com/hash_functions http://www.strchr.com/hash_functions has examples of collision rates for different hashes, all non-cryptographic.
- wisty 14y agoPython's hash, for example, will generate lower collisions than a "good" hash function. 'file1', 'file2', and 'file3' will not collide, but end up in sequential boxes, which is very efficient. Of course, you can send python web apps a "cookie of death", in which all cookies collide. There's a patch, but I think it's disabled by default.
- lobster_johnson 14y agoBad name. Already taken by a well-known Ruby tool (http://godrb.com/ http://godrb.com/). Why not call it Heaven? It's got clouds.
- codygman 14y agoI didn't know of this tool. I'm sure lots of programs use the name God TBH.
- lobster_johnson 14y agoNo, looks like it's just the one. And it's in Debian/Ubuntu [1][2] as "god", so this tool is already at a disadvantage, namewise: $ apt-cache search god | grep "^god" god - Fully configurable process monitoring [1] http://packages.debian.org/search?keywords=god&searchon=names&suite=stable§ion=all http://packages.debian.org/search?keywords=god&searchon=... [2] http://packages.ubuntu.com/search?keywords=god&searchon=names&suite=quantal§ion=all http://packages.ubuntu.com/search?keywords=god&searchon=...
- pknerd 14y agoInteresting to see how technology is being religionized by hackers. Smirk
- rartichoke 14y agoI don't want to come off as a negative Nancy but why didn't you just stick to using Redis? What problems does your lib solve that Redis does not?
- zond 14y agoIf you run out of RAM or CPU on a single machine you start running into operationally problematic situations with Redis.
- rartichoke 14y agoI've never had this issue pop up (I am not involved in any huge scale sites) but I have to believe this really isn't too common? Also a 5 second Googling shows there's ways to set Redis up to stop writing but continue reading if you're running out of memory. If you really have that large memory needs then you're going to also run out of memory with this new lib on 1 machine. It seems like Redis has more than enough options to prevent real problems from occurring once you do surpass your hardware requirements.
- zond 14y agoI guess it's not for you, then.
- JulianMorrison 14y agoDistributed hash table algorithms were originally created for things like Gnutella and are optimal for cases where you expect nodes to pop up and disappear on a regular (but unpredictable) basis.