mslot

(press play, you can click cars and enable visualizations)

The system analyzes the driving tracks in the map and finds potential conflict areas. Cars require permission from other cars they might conflict with to enter into a conflict area. To deal with communication failure, they also need confirmation that there are no other cars in the (relevant) area than the ones that responded, which they can determine by sharing and combining LIDAR data and correcting the observations for delays.

When receiving a request from another car, a car can decide to respond with accept (if no conflict), reject (if the responder is competing for the same area and has a lower eta or identifier), or tentatively accept (if the responder already got confirmation), which builds a directed, acyclic graph determining the order in which cars can cross. Cars build a trajectory through all the upcoming conflict areas and can enter the next conflict area in the trajectory if all the cars that tentatively accepted have passed it in their trajectory. If this cannot be confirmed through messages from those cars, LIDAR can again be used to confirm that the preceding cars left the area (or did not enter before the deadline).

It improves efficiency quite a lot, though it's slightly academic in the sense that it assumes there are only autonomous cars and no radio jammers or liars. Everything freezes if there is a human car, since safety cannot be confirmed, though this can be solved by combining it with (more probabilistic) recognition algorithms. The thesis mostly focuses on the distributed systems aspect and how to preserve safety in case of communication failure. There's some ongoing work on applying it to lane changing scenarios, where it can be effective even if only a relatively small percentage of cars support it.

Paxos is a rather simple algorithm for reaching consensus on a value once: http://research.microsoft.com/en-us/um/people/lamport/pubs/p...

The two phases of the algorithm are described at the bottom of page 5. Section 3 also describes how to use Paxos to implement log replication, Multi-Paxos, which is comparable to Raft. Unfortunately, this section does a lot of hand-waving, so it requires the implementer to have a thorough understanding of the underlying issues and find good solutions to problems such as membership changes.

Conversely, the Raft paper is much more instructive to implementers, giving a clear overview of the necessary functions, messages and state: https://ramcloud.stanford.edu/raft.pdf

Personally, I find Multi-Paxos a lot more elegant, as it essentially derived by working backwards from the safety constraints. As a distributed systems researcher, it is very obvious to me why it works and I can do a basic implementation almost from memory. Unlike Raft it is also independent of time. Another nice property is that it is symmetric/masterless. All nodes can do reads and writes at any time, though whether that's a good idea is another matter. Of course, these are rather subjective and mostly aesthetic notions.

Multi-Paxos is generally seen as harder to implement, because the Paxos Made Simple paper is not very explicit about implementation, and the original paper is... well... read it :) http://research.microsoft.com/en-us/um/people/lamport/pubs/l...

Raft is getting quite popular, because people find it easy to follow the instructions of the paper, but this can be slightly deceptive. For example, using stable storage for your state is essential for crash-safety (meaning fsync-ing before answering), but I don't see where Hashicorp's raft implementation does that. Raft relies on the combination of several rules to reach consensus reliably, for which Ongaro has given a rather elaborate proof using 20 pages of TLA+ in his thesis. It's quite easy to make a mistake in your implementation and break one of the rules. The same goes for Paxos, but the rules are, at least to some extent, more obvious.

A big benefit of Raft is that it already includes quite a few optimizations that would be necessary to make a Multi-Paxos implementation efficient, and you don't have to come up with them yourself. You can generally expect Raft implementations to outperform Multi-Paxos implementations. On the other hand, Multi-Paxos can be tailored to a specific use-case, such as Google's Megastore, Chubby and Spanner, which would be much more difficult with Raft.

pg_paxos is an extension that uses PostgreSQL's query execution hooks so it doesn't require any external components. An advantage of pg_paxos is that you can do reads and writes on any node. Would love to know what people think and whether it's something you would use (if rigorously tested). Small warning: it replicates SQL queries and doesn't stop you from using volatile functions like now() yet, which would give inconsistent results.

A possible application is a reliable cron service. Each cron node tries to add an entry to a replicated locks table with the same primary key on any of the PostgreSQL nodes. Only one will succeed and then runs the cron job.

Some more details in these slides: http://www.p2d2.cz/files/pg_paxos.pdf

The bottleneck is usually not I/O, but computing aggregates over data that continuously gets updated. This is quite CPU intensive even for smaller data sizes.

You might want to consider PostgreSQL, with Citus to shard tables and parallelise queries across many PostgreSQL servers. There's another big advertising platform that I helped move from MySQL to PostgreSQL+Citus recently and they're pretty happy with it. They ingest several TB of data per day and a dashboard runs group-by queries, with 99.5% of queries taking under 1 second. The data are also rolled up into daily aggregates inside the database.

There are inherent limitations to any distributed database. That's why there are so many. In Citus, not every SQL query works on distributed tables, but since every server is PostgreSQL 9.5, you do have a lot of possibilities.

Looking at your username, are you based in the Netherlands by any chance? :)

Some pointers:

- How CloudFlare uses Citus: https://blog.cloudflare.com/scaling-out-postgresql-for-cloud...

- Overview of Citus: https://citus-conferences.s3.amazonaws.com/pgconf.ru-2016/Ci...

- Documentation: https://www.citusdata.com/documentation/citusdb-documentatio...

- availability: always accept writes, but reads in other partitions might not see them so there's no consistency.

- consistency: writes fail/block until the partition is resolved, so there's no availability.

Clearly, parts of your data that are not affected by a partition might still be consistent and available.

The point is, in classical database systems 100% of transactions are consistent. In distributed databases this is only possible if you sacrifice availability some of the time, or alternatively you can sacrifice consistency some of the time.

The author of this paper is suggesting a more elaborate theory that involves network delay, which is great, though criticising what is effectively a mathematical truth seems strange.

Given local join machinery, a join between 2 distributed tables can be achieved by joining the partitions of the tables locally after ensuring that tables are co-partitioned and partitions are co-located. That is, if performing A JOIN B ON (A.X = B.Y), ensure that A is partitioned by X and B is partitioned by Y with the same partitioning scheme such that every partition in A has a corresponding partition in B with which it can be joined. A distributed join can then be performed (in parallel) by joining each pair of partitions and concatenating the results.

Ideally, tables are co-partitioned and partitions are co-located in advance. The article describes scenarios in which the tables need to be repartitioned during the query, which can cause a lot of network traffic. However, the amount of traffic is limited in practice since filters and projections can be applied before shuffling any data.

The great thing about implementing a distributed database on top of PostgreSQL is that the local machinery already exists, and it is very good.

With sharding, the distributed executor can work on the SQL level and translate one SQL query to many SQL queries. In that case your distributed executor can focus on issues such as partitioning and merging data, while the low-level work is still being done by the regular PostgreSQL executor, so you don't have to implement it from scratch.

[1] https://github.com/citusdata/postgres_vectorization_test

For a proposal i with value x:

1. Ask everyone not to participate in proposals older than i, get a majority to agree and send back any previously accepted values.

2. Ask everyone to accept proposal i with the newest previously accepted value or x if none, get a majority to accept.

- On failure, restart with i > max(previous proposals)

That is the Paxos algorithm.

Its fault-tolerance comes from the fact that you can tolerate losing the minority (1 out of 3 / 2 out of 5). There's no magic. If the majority fails, Paxos blocks. If two proposers keep blocking each other's proposals by going through round 1, Paxos can take forever.

The goal of Paxos is to agree on 1 value. Once consensus is reached (majority agrees), the value can never be changed, since no one can complete round 1 without getting back the newest accepted value from at least one node. However, you can run Paxos again and again to agree on a sequence of values (e.g. transitions in a state machine). This is Multi-Paxos.

The Paxos algorithm is optimal, but Multi-Paxos allows for a lot of optimizations and there is no clearly defined implementation. A pretty typical optimization is to elect a leader (through Paxos) which makes the proposals. This avoids duelling proposers and ensures you have a node that is always aware of the latest accepted value. Making this optimization requires you to make decisions that fall outside the scope of Paxos, such as how long a node remains leader, what happens if the leader fails, and what happens if two nodes think they are the leader. These optimizations can easily cause you to lose the fault-tolerance and consistency guarantees that Paxos gives you within the scope of reaching consensus on a single value.

It's important to remember that Paxos itself is easy to understand and a lot of the problems in Multi-Paxos can be solved by running Paxos. You need to familiarize yourself with it as though it was a programming construct.

The differences in priority rules tick me off way more than the side of the road.

Most finance ministers in the eurogroup who decide on the fate of the second biggest monetary union are not economists, and don’t seem to listen to the advice of economists, most of whom are calling for an end to austerity. Since the current pro-austerity administration took office, the Netherlands has performed worse than its mostly ungoverned neighbour Belgium in almost every respect, including debt-to-GDP growth. Mind you that the Netherlands is one of the richest countries in the world with financial assets worth several times its debts, and those assets have much higher returns than what they pay in interest on their loans. Yet even in this most luxurious of positions, the Dutch finance minister who is also the eurogroup president, swears by austerity for his country and for others, and the Greeks must suffer through it.

There's also a video from SFPUG last year, though it's not great quality: https://www.youtube.com/watch?v=yT34i82o99w

You should try React with JSX though. It's a tool like jQuery, but much more sane and structured, and as opposed to frameworks, it becomes more likable the more you use it.

    jq -r 'map(select(.creditcard)) | .[] | .timestamp + ";" + .name + "," + .creditcard' data.json | tr '\n' ';' | xargs -n 2 -d ';' sh -c 'echo $1 >> $(TZ=GMT date --date="$0" +"%Y%m%d").csv'

Not really. The resolvers tend to be geographically dispersed and use anycast. Having a multi-layered cache would probably decrease performance, except within a specific location.

There are some nice research papers studying DNS resolvers, e.g. here's one for cellular networks: http://www.aqualab.cs.northwestern.edu/component/attachments...

Could you perhaps ask your former Route53 colleagues for some log-file insight?

They see what's behind the cache, not how much traffic the resolvers are taking. Could be the same, could be 100x more, hard to tell.

So all it takes is one hit per major ISP per TTL to keep it zippy for almost everyone. That's why DNS works so well, after all?

Caching works great with long TTLs, e.g. as used for NS, MX, CNAME records. The problem is the 60 second TTLs that are commonly used for A records in cloud services. Except for reasonably high volume names, it's not highly probable that your A records will be in a given cache at a given time. Many applications also use many different domain names (e.g., one per user), which creates a long tail of low volume names.

Of course, traffic is not uniformly distributed in any way, so there might be parts of the day when your name will be constantly served from cache everywhere, or parts of the world where it is never served from cache.

The 75000 was mostly a thought example, it's very hard to know what a good number is, although there is a Route 53-related reason for that number. In any case, the benefit of DNS caching is probably much less than you think due to short TTLs and the number of resolvers.

The RTT mechanisms in resolvers have a high degree of randomness and will aggressively try the other, slower name servers again. E.g., out of 1000 samples, my desktop in the Netherlands (via XS4All) sees low latencies from Route 53 ~60% of the time:

  $ seq 1 1000 | xargs -n 1 sh -c 'dig test-$0.trosc.com | grep "Query time" | awk "{print \$4}"' | histogram.py -f "%3d"

   18 -  59 [   609]: ∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎
   59 - 100 [     1]: 
  100 - 141 [     1]: 
  141 - 182 [   229]: ∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎∎
  182 - 224 [   102]: ∎∎∎∎∎∎∎∎∎∎∎∎
  224 - 265 [    37]: ∎∎∎∎
  265 - 306 [     1]: 
  306 - 347 [    15]: ∎
  347 - 388 [     2]: 
  388 - 430 [     2]:

As you pointed out, Route 53 optimizes for availability and DDoS resilience over RTT performance. There are 4 name server IPs to choose from which gives me 4 different paths to 4 different server locations via anycast, giving me 4 different RTT buckets. Few DNS providers go through such lengths for availability. Still, 185ms is a lot. It's probably because anycast/BGP advertisements from the US get to AMS-IX with a smaller number of hops than competing advertisements from European locations. I would guess Route 53's current striping is not heavily tuned for RTTs.

Caching solves part of this, but there are a lot of resolvers out there. As a thought example: Assume your sources of traffic are uniformly distributed among 75000 resolvers and you use 60 second TTLs (pretty standard), then you won't see significant benefit from caching until you get to >>1000 requests/s.

Many applications also have a long-tail of DNS names and basically wont benefit from caching at all. This could be motivated by availability as well (think shuffle sharding :). I'm building one where DNS query time currently dominates page load time (especially aliasing to CloudFront can be slow :). It's useful to understand that there's a general availability vs. latency trade-off in DNS that only gets partially addressed by the resolver.