p-lang thread: (now (have you (problems two)))

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > YOSPOS > p-lang thread: (now (have you (problems two)))

«‹›1784 »

MononcQc: May 29, 2007

Notorious b.s.d. posted:

so in this system, the physical timestamp is just for laffs?

The physical timestamp is the primary mechanism by which you define which update wins. It's a Last-Write-Wins mechanism.

It's inspired by Google's Spanner, which uses GPS and atomic clocks to give you a very predictable interval of uncertainty between your updates, and keep them as small as possible.

These require hardware and specific deployments in a data center. Hybrid clocks, on the other hand, try to give you the spanner semantics, but without the special handrolled hardware Google can afford to use and maintain. They replace the very small inaccuracy with a bigger one constrained by NTP, but compensated with a lamport clock to retain some causality information to reduce the number of conflicts you'd have otherwise.

it's a cool software-level fix to a hardware-level lack of capacity.

# ? Nov 23, 2014 01:21

Adbot: ADBOT LOVES YOU

# ? May 20, 2024 07:56

MononcQc: May 29, 2007

suffix posted:

so if you have two messages with the same time and counter, they came from different servers and are unordered?

That's a cool conflict. So what you do is pick a winner (any, may depend on your system), and then increment the logical clock.

Dealing with causality will necessarily yields these sooner or later, but they try to limit them as much as possible.

the talent deficit posted:

no it's like a best effort thing. event α probably happened at time t but definitely happened before event β. the casual part (α → β) is critical but the timestamp being a wall clock time is nice to have

I think it's the opposite. In hybrid clocks, the hardware clock more or less dominates. The best effort is in using a lamport clock for causality, which is the nice to have whenever the hardware clock is bad. That's why you reset the lamport clock, but never reset the timestamp.

the talent deficit posted:

it doesn't really do this i don't think. not without some kind of synchronization on top (paxos or some kind of write throttling that prevents writes that fall outside some tolerance bracket). i mean, they're consistent in the sense they all make some sort of sense but they don't necessarily reflect reality. different nodes can have wildly different skew. you only get happened before relationships on a single node

It does this because it assumes NTP keeps a bound on the skew, and the paper mentions ignoring updates that are too far ahead in time they have to be an error. The synchronization is implicit otherwise to every clock (which is why you switch from the timestamp to the lamport clock when the other one is more advanced, to make things monotonic)

It will not necessarily reflect reality, but it will be a best effort to reduce it.

# ? Nov 23, 2014 01:25

MononcQc: May 29, 2007

the talent deficit posted:

paxos is the only linearizable algorithm in common use. i know etcd and consul (and maybe something else i'm forgetting) are using raft but they are both very new. spanner and zookeeper aren't strictly paxos (spanner uses crazy gps synchronized atomic clocks to skip some steps and zookeeper requires your transport make a bunch of guarantees to do the same) but they are based on paxos

Raft gives you linearization. Spanner is a LWW system afaik, and is not purely linearizable in that you can be dropping writes that have been perceived to happen before another one despite that not being the truth. Either you will do that, or you'll have to delay writes, at which point you may have a serializable but not linearizable guarantee. Not too sure there.

Zookeeper isn't a quorum system so to say, but the result is the same in that there's a leader election and every write has to go through the master in a well-defined order. They are equivalent systems. Same with Raft.

To be exact, Paxos only gives you linearization (with a guarantee of progress) when you first use it to elect a leader and the leader thereon becomes your central point of decision-making, which needs to be backed by a majority to ensure the information can't be crushed or lost. Without the leader you lose the guarantee of progress.

the talent deficit posted:

the sacrifice crdts make over paxos based systems is linearizability. they're serialized but not linear. if you apply the entirety of some set α you get result β but there's no guarantee that applying a partial set of α is consistent with any other partial set of α. in practice that means there's no read consistency except when you can apply some total ordering, ie, linearize. single nodes get read consistency but reading from two different nodes can give completely different results. two nodes may start in the same state and end in the same state in a serialized system but their intermediate states could be completely divergent

CRDTs aren't serialized because during a netsplit, you will have inconsistent views that may not ever represent a view you could have serialized on a regular system. ACID transactions are serializable but not necessarily linearized as a guarantee because replaying the same requests in the same order could end up applied differently on a single system. CRDTs provide 'strong eventual consistency' meaning they're still eventually consistent, but will never have conflicts.

the talent deficit posted:

in an op based crdt (cmrdt) you can establish a casual relationship (i mean 'happened before') on events from a single node. that lets you relax commutativity because you can control the order of ops. you still need associativity for the reason you state (other nodes can essentially insert operations between yours). cmrdt's are really just a specialization of crdts in which you can make the casual guarantee

Good point on associativity vs. commutativity.

# ? Nov 23, 2014 01:31

the talent deficit: Dec 20, 2003; self-deprecation is a very british trait, and problems can arise when the british attempt to do so with a foreign culture

MononcQc posted:

I think it's the opposite. In hybrid clocks, the hardware clock more or less dominates. The best effort is in using a lamport clock for causality, which is the nice to have whenever the hardware clock is bad. That's why you reset the lamport clock, but never reset the timestamp.

right but it can reset the lamport clock because the physical clock has incremented. it still guarantees α → β

MononcQc posted:

It does this because it assumes NTP keeps a bound on the skew, and the paper mentions ignoring updates that are too far ahead in time they have to be an error. The synchronization is implicit otherwise to every clock (which is why you switch from the timestamp to the lamport clock when the other one is more advanced, to make things monotonic)

right that's what i meant by throttling writes that are outside whatever your error bound is

how are you synchronizing clocks such that an event generated on one node happened physically before an event on another node? you get a consistent logical ordering but not necessarily an accurate one

# ? Nov 23, 2014 02:01

MononcQc: May 29, 2007

the talent deficit posted:

how are you synchronizing clocks such that an event generated on one node happened physically before an event on another node? you get a consistent logical ordering but not necessarily an accurate one

Well, again, NTP limits the uncertainty there. In most practical cases, my guess is the regular clock will be good enough. Whenever it conflicts, the you can only ever get the 'happened before' relationship if the evidence is hard (you saw your peer's update before you performed yours, which the lamport clock ensures).

It's true there's risk that you will lose or erroneously get some of your updates in the wrong order. That's when neither your causal nor your physical clocks can be used to figure things out. That's a risk and that's where the hybrid clock does a best effort, but not much more.

# ? Nov 23, 2014 02:34

akadajet: Sep 14, 2003

lmao there is a for real programming language called "coq"

# ? Nov 23, 2014 03:01

gonadic io: Feb 16, 2011; >>=

akadajet posted:

lmao there is a for real programming language called "coq"

the (french) guy named it specifically to piss off english speakers

# ? Nov 23, 2014 03:04

gonadic io: Feb 16, 2011; >>=

every year the first 3 lectures of the course on it are basically non-stop giggling. from 20 year olds.

# ? Nov 23, 2014 03:04

akadajet: Sep 14, 2003

yeah, i'm giggling at youtube videos right now of guys talking about how long they've been using coq and how it helps them with their work

# ? Nov 23, 2014 03:07

Ator: Oct 1, 2005

why would anyone use django's html template language?

python code that outputs an html string: fast to write, easy to debug, very powerful.
html template languages: inferior in every way.

# ? Nov 23, 2014 04:00

abraham linksys: Sep 6, 2010

Ator posted:

why would anyone use django's html template language?

python code that outputs an html string: fast to write, easy to debug, very powerful.
html template languages: inferior in every way.

mainly b/c operating on strings is terrible. tho i have recently been using react.js, which uses a an XML-like DSL compiled to function calls for markup, meaning you can do fun stuff like

code:

var MyComponent = React.createClass({
  render: function() {
    var myItems = ["uno", "dos", "tres"];
    
    var listItems = myItems.map(function(item) {
      return (
        <li>{item}</li>
      );
    });
    
    return (
      <ul>
        {listItems}
      </ul>
    );
  }
});

being able to interact with markup like any other code is pretty cool, but only because it's an abstract representation of markup (the above DSL gets compiled into function calls like this) and not, y'know, loving strings

also the only good templating language is jinja2 (and mozilla's javascript port nunjucks)

# ? Nov 23, 2014 04:11

tef: May 30, 2004; -> some l-system crap ->

suffix posted:

nope. tried with 128 bit keys and still getting ridiculous distributions like
kademlia:
Counter({b'endpoint7': 249270, b'endpoint0': 125624, b'endpoint3': 124987, b'endpoint6': 124666, b'endpoint9': 62954, b'endpoint4': 62699, b'endpoint5': 62601, b'endpoint1': 62481, b'endpoint8': 62426, b'endpoint2': 62292})

i think it tends to skewed distributions and isn't good for load balancing like consistent hashing is

consistent hashing is terrible, that's why we use vnodes :3:

# ? Nov 23, 2014 13:22

tef: May 30, 2004; -> some l-system crap ->

suffix posted:

nope. tried with 128 bit keys and still getting ridiculous distributions like
kademlia:
Counter({b'endpoint7': 249270, b'endpoint0': 125624, b'endpoint3': 124987, b'endpoint6': 124666, b'endpoint9': 62954, b'endpoint4': 62699, b'endpoint5': 62601, b'endpoint1': 62481, b'endpoint8': 62426, b'endpoint2': 62292})

i think it tends to skewed distributions and isn't good for load balancing like consistent hashing is

my results say the opposite:

consistent hashing (without vnodes), has a crap distribution
rendevous hashing (without vnodes), has a pretty good distribution
kadmelia has a better distribution than consistent hashing, but not as good as rendevous hashing, which is what i'd expect

# ? Nov 23, 2014 14:20

tef: May 30, 2004; -> some l-system crap ->

what i'm actually finding is rendevous hashing is really, really good

but using hash(a,b) as hash(a) ^ hash(b) is not as nice as i'd hoped

# ? Nov 23, 2014 15:54

tef: May 30, 2004; -> some l-system crap ->

trying now with vnodes:

rendevous hashing works amazingly, every time, even with small numbers of workers

kadmelia works ok-ish, but adding vnodes you can clamp variance between nodes to something ok

consistent hashing works, but less well than kadmelia most of the time. adding vnodes helps, but kadmelia with same amount of nodes usually performs better

it seems that rendevous hashing is loving ace, far better than i thought.

i haven't tried with rebalancing, but, my gut tells me that i'll see similar results: rendevous hashing gets the best result, kadmeila isn't as good, better with vnodes, and consistent hashing does badly by comparison

# ? Nov 23, 2014 16:08

tef: May 30, 2004; -> some l-system crap ->

the thing is, i should be able to implement kademlia as fast as consistent hashing, and i think there will be a point where rendevous is too slow and kadmelia is good enough

tef fucked around with this message at 16:52 on Nov 23, 2014

# ? Nov 23, 2014 16:09

MononcQc: May 29, 2007

If it were possible to have a crush on algorithms, Rendez-Vous hashing would be pretty drat near the top of my list.

# ? Nov 23, 2014 17:32

suffix: Jul 27, 2013; Wheeee!

rendezvous hashing is perfect. with a good hash function each key gets a independent endpoint ordering

consistent hashing needs a silly number of hashes to get good distribution
kademlia does seem to perform slightly better if you add more hashes, but i think they're pretty similar. they both hash both the endpoints and the key and try to find the closest one. you could look at kademlia as a different way to divide the circle. is there a tradeoff here with behavior on node failure?

we have some services that use consistent hashing but makes the hash ring for each request, getting the worst of both worlds. i think i'll change those to rendezvous hashing

code:

consistent hashing (100):
Counter({b'endpoint1': 114982, b'endpoint5': 112189, b'endpoint3': 107064, b'endpoint7': 106997, b'endpoint8': 97593, b'endpoint4': 96533, b'endpoint9': 93977, b'endpoint0': 93370, b'endpoint2': 91195, b'endpoint6': 86100})

consistent hashing (1000):
Counter({b'endpoint2': 106531, b'endpoint7': 104597, b'endpoint1': 104539, b'endpoint4': 103723, b'endpoint3': 98615, b'endpoint6': 98575, b'endpoint0': 97184, b'endpoint9': 95936, b'endpoint5': 95791, b'endpoint8': 94509})

rendezvous hashing:
Counter({b'endpoint5': 100392, b'endpoint6': 100320, b'endpoint9': 100286, b'endpoint8': 100205, b'endpoint1': 100169, b'endpoint7': 100033, b'endpoint4': 100013, b'endpoint3': 99690, b'endpoint0': 99539, b'endpoint2': 99353})

kademlia (1):
Counter({b'endpoint4': 125414, b'endpoint0': 125197, b'endpoint6': 124991, b'endpoint7': 124907, b'endpoint5': 124666, b'endpoint1': 124274, b'endpoint2': 62987, b'endpoint8': 62604, b'endpoint9': 62568, b'endpoint3': 62392})

kademlia (100):
Counter({b'endpoint1': 113392, b'endpoint5': 110640, b'endpoint3': 109044, b'endpoint0': 103649, b'endpoint4': 101108, b'endpoint2': 93704, b'endpoint9': 93132, b'endpoint8': 93099, b'endpoint6': 92184, b'endpoint7': 90048})

kademlia (1000):
Counter({b'endpoint1': 104545, b'endpoint2': 103823, b'endpoint4': 100984, b'endpoint9': 100771, b'endpoint0': 100471, b'endpoint6': 99726, b'endpoint8': 98636, b'endpoint5': 97315, b'endpoint7': 97078, b'endpoint3': 96651})

# ? Nov 23, 2014 18:31

MononcQc: May 29, 2007

The downside of rendezvous is that it costs more for each single call, so it makes sense to use it specifically when its objective is to save a lot more time than it costs by using it. i.e. caching dispatching and whatnot, and when you expect frequent variation in the nodes of your cluster with a need for low displacement.

If you have a set of dedicated servers that you will grow or shrink once in a blue moon and where your objective is to find info (and is purely a cost, not a cost-saving measure), persistent hashing remains fairly great and has a lower cost.

I'm not too aware of how Kamdelia compares in either case, might be a compromise?

# ? Nov 23, 2014 19:39

tef: May 30, 2004; -> some l-system crap ->

rendevous hashing is good if

- your server size is small
- you're not looking for very very low latency
- you want excellent balancing on addition/removal of nodes
- you have global knowledge of all workers

kadmelia is I think a better choice than chord, because it does a bit better than balancing
it takes the same storage requirements + runtime for consistent hashing, and can be just as fast

it can also deal with partial knowledge too

# ? Nov 23, 2014 19:46

MeruFM: Jul 27, 2010

3 of those requirements seem pretty terrible. And 4 begets 1 so it's just 2 requirements i guess.

# ? Nov 23, 2014 20:25

JewKiller 3000: Nov 28, 2006; by Lowtax

The DS (Distributed Systems) thread: I'm glad Erlang is the current hipste

# ? Nov 23, 2014 20:36

MononcQc: May 29, 2007

MeruFM posted:

3 of those requirements seem pretty terrible. And 4 begets 1 so it's just 2 requirements i guess.

Well, let's see.

1. your server size is small
2. you're not looking for very very low latency
3. you want excellent balancing on addition/removal of nodes
4. you have global knowledge of all workers

1. Technically, the definition of 'small' depends on 2 and 4; rendezvous-hashing is an O(n) algorithm requiring you to hash a key with all the servers in your set to find the best match. Whether you can do this or not will depend on how long you can take to hash, and how easy it is to know your server list.

2. Depending on the hash algorithm and language, the cost will be x*n, where x is the cost of hashing a message, and n is the number of servers that are candidates to be routed to. If you need 5�s to hash once and have 150 servers, choosing where to send the data is going to take ~750�s.

If using rendezvous-hashing lets you save 30ms once in a while due to good data locality even through failures, it might be a winning proposition in order to shrink your long tail (p99 or p999) and get more predictable results.

3. This one is okay. If nodes come and go, network is unreliable, or whatever, rendezvous hashing lets you pick primaries and failovers for a given key on the go. Adding or removing nodes from the cluster permanently guarantees the least disruption possible (1/|nodes| keys move on average for each addition or removal of a node, as opposed to the consistent's hash (|nodes|-1)/|nodes| unless you use vnodes)

4. This fully depends on how dynamic your cluster is. Most people, for example, may have an idea of what machines they are running.

# ? Nov 23, 2014 20:51

Malcolm XML: Aug 8, 2009; I always knew it would end like ｔｈｉｓ．

tef posted:

rendevous hashing is good if

- your server size is small
- you're not looking for very very low latency
- you want excellent balancing on addition/removal of nodes
- you have global knowledge of all workers

kadmelia is I think a better choice than chord, because it does a bit better than balancing
it takes the same storage requirements + runtime for consistent hashing, and can be just as fast

it can also deal with partial knowledge too

This is like 99.9% of poo poo inside a webserver DC, where who gives a gently caress about an extra hash call or something

# ? Nov 23, 2014 21:05

Malcolm XML: Aug 8, 2009; I always knew it would end like ｔｈｉｓ．

MononcQc posted:

Well, let's see.

1. your server size is small
2. you're not looking for very very low latency
3. you want excellent balancing on addition/removal of nodes
4. you have global knowledge of all workers

1. Technically, the definition of 'small' depends on 2 and 4; rendezvous-hashing is an O(n) algorithm requiring you to hash a key with all the servers in your set to find the best match. Whether you can do this or not will depend on how long you can take to hash, and how easy it is to know your server list.

2. Depending on the hash algorithm and language, the cost will be x*n, where x is the cost of hashing a message, and n is the number of servers that are candidates to be routed to. If you need 5�s to hash once and have 150 servers, choosing where to send the data is going to take ~750�s.

If using rendezvous-hashing lets you save 30ms once in a while due to good data locality even through failures, it might be a winning proposition in order to shrink your long tail (p99 or p999) and get more predictable results.

3. This one is okay. If nodes come and go, network is unreliable, or whatever, rendezvous hashing lets you pick primaries and failovers for a given key on the go. Adding or removing nodes from the cluster permanently guarantees the least disruption possible (1/|nodes| keys move on average for each addition or removal of a node, as opposed to the consistent's hash (|nodes|-1)/|nodes| unless you use vnodes)

4. This fully depends on how dynamic your cluster is. Most people, for example, may have an idea of what machines they are running.

lets say hashing takes 5us. 1k instances, goes up and down between 600-1100 as demand goes up and down so: 5ms. Network latency is 10s-100s of ms, who gives a gently caress

if u tryin to route packets and trades and poo poo, sure

# ? Nov 23, 2014 21:08

MononcQc: May 29, 2007

Also the number of installs that have thousands of servers and no way to somehow filter or cull the total amount to find a candidate is fairly low. Still interesting from a theoretical point of view though.

# ? Nov 23, 2014 21:19

tef: May 30, 2004; -> some l-system crap ->

fwiw anyone interested may want to watch this
http://vimeo.com/52446728

and maybe follow with this
https://www.youtube.com/watch?v=ggCffvKEJmQ

# ? Nov 23, 2014 21:28

Malcolm XML: Aug 8, 2009; I always knew it would end like ｔｈｉｓ．

MononcQc posted:

Also the number of installs that have thousands of servers and no way to somehow filter or cull the total amount to find a candidate is fairly low. Still interesting from a theoretical point of view though.

i guess u could do it hierarchically

# ? Nov 24, 2014 03:20

Zombywuf: Mar 29, 2008

Malcolm XML posted:

lets say hashing takes 5us. 1k instances, goes up and down between 600-1100 as demand goes up and down so: 5ms. Network latency is 10s-100s of ms, who gives a gently caress

if u tryin to route packets and trades and poo poo, sure

Or if you make more than one call to the hash table per operation. I've seen systems make hundreds. Terrible, terrible systems.

# ? Nov 24, 2014 13:14

Zombywuf: Mar 29, 2008

tef posted:

fwiw anyone interested may want to watch this
http://vimeo.com/52446728

and maybe follow with this
https://www.youtube.com/watch?v=ggCffvKEJmQ

Reading the paper now. They've implemented it as a Ruby DSL :smith:

# ? Nov 24, 2014 17:33

Cybernetic Vermin: Apr 18, 2005

i rather think that that is the legitimate use of ruby though. works out basically like tcl, but with worse libraries

# ? Nov 24, 2014 18:36

tef: May 30, 2004; -> some l-system crap ->

second talk is about daedelus :3:

# ? Nov 24, 2014 18:36

tef: May 30, 2004; -> some l-system crap ->

Cybernetic Vermin posted:

i rather think that that is the legitimate use of ruby though. works out basically like tcl, but with worse libraries

it's not a dsl if the errors are in another language, it is not a legitimate use, it is a terrible use

# ? Nov 24, 2014 18:37

Notorious b.s.d.: Jan 25, 2003; by Reene

Cybernetic Vermin posted:

i rather think that that is the legitimate use of ruby though. works out basically like tcl, but with worse libraries

power botton posted:

https://hubot.github.com and write your own plugins or maybe go outside and get some fresh air imo

quote:

Today's version of Hubot is open source, written in CoffeeScript on Node.js,

*record scratch*

# ? Nov 24, 2014 20:32

power botton: Nov 2, 2011

if you're gonna do dumb poo poo like reinvent spotlight/alfred plugins for fucktarded ideas you deserve all the pain you get

# ? Nov 24, 2014 20:34

Adbot: ADBOT LOVES YOU

# ? May 20, 2024 07:56

Dessert Rose: May 17, 2004; awoken in control of a lucid deep dream...

power botton posted:

if you're gonna do dumb poo poo like reinvent spotlight/alfred plugins for fucktarded ideas you deserve all the pain you get

fair, but spotlight/Alfred only search my local machine, and they are pull only; I can't see my web server data on my desktop without some serious work, and then I still have to do yet more work to get it on my iPhone or my work machine.

I will freely admit that part of the inspiration for this comes from my childish desire to have a window with scrolling text/graphics on all of my computing devices

except it should show me interesting (to me) data instead of fake placeholders

the ability to write code in a box and have it run on a machine in my cluster without any more effort needed than "type the code" is sort of important too

# ? Nov 24, 2014 20:40

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > YOSPOS > p-lang thread: (now (have you (problems two)))

«‹›1784 »