Some initial calculations
Opened this issue · 12 comments
We need to distribute daily tracking keys (dtks) of all infected users.
- A single dtk is 16 bytes (128 btis).
- A DayNumber is 4 bytes (32 bits).
- Each infected user submits exactly one key for each DayNumber (defined by the standard of Apple and Google).
- The expected number of dtks a user submits is 14 plus or minus 2.
- The maximum number of dtks a user can realistically submit is 46.
If we assume that 500k persons will get infected simultaneously (Which is 1/34 for The Netherlands), we will receive about (46 * 20 * 500 * 10 ^ 3) / (1024 ^ 2) = about 438 MebiBytes of keys for their entire disease period.
If we assume that (1/46-th) of that amount of data will come in to update the new dtks. That still means we will have an influx of (20 * 500 * 10^3) / (1024^2) = about 10 MebiBytes of new key material that we have to distribute each day.
These numbers are small enough to handle with a simple combination of nginx / apache, PHP and MySQL on the write-side of the backend.
On the read-side of the backend we will have to serve these 10 new MebiBytes each day to all 17M smartphones in The Netherlands.
This means that we have an output of ((20 * 500 * 10^3) * (17 * 10^6)) / (1024^4) = about 154 TebiBytes every 24 hours! Which roughly translates to an output of ((20 * 500 * 10^3) * (17*10^6)) / (3600 * 24) = About 2 GibiBytes per second!
This is ((20 * 500 * 10^3) * (17 * 10^6) * 8) / (3600 * 24 * 1000^3) = about 16 gigabits/second.
If use the current situation as a benchmark (this is a bad idea, because we should expect to have underreporting) and assume that only 20k infections will be active at the same time, the numbers look like this:
Daily new dtks: (20 * 20 * 10^3) / (1024^2) = about 390 KibiBytes.
Daily data output: ((20 * 20 * 10^3) * (17 * 10^6)) / (1024^4) = About 6 TebiBytes.
Average output rate: ((20 * 20 * 10^3) * (17 * 10^6)) / (3600 * 24 * 1024^2) = about 75 MebiBytes per second
Or in megabits/second: ((20 * 20 * 10^3) * (17 * 10^6) * 8) / (3600 * 24 * 1000^2) = about 630 megabits/second.
So this is doable, but I think we need about 12 servers, each with its own 1 gigabit/second connection for the read side.
It's way more efficient to partition by the day number. Since the amount of day numbers are limited, e.g. 14, you can provide 14 append only logs, and you can calculate with sending 16 bytes again (plus a fixed overhead for fetching 14 files).
I would advise a PostgreSQL + PostgREST solution so you get a free API if you define a schema + views.
It's way more efficient to partition by the day number. Since the amount of day numbers are limited, e.g. 14, you can provide 14 append only logs, and you can calculate with sending 16 bytes again (plus a fixed overhead for fetching 14 files).
I would advise a PostgreSQL + PostgREST solution so you get a free API if you define a schema + views.
No you can't because the amount of day-numbers is variable and not limited to a 14 day window. See: #7 (comment)
Also: This is off-topic here, because it is addressed in #5
Also number 2: PosgREST is not a good idea, because the volume of READ-operations is enormous (greater than (new DayNumbers) * 24 * 17 million per day), so we probably can't allow every read to hit the database.
Also number 3: We need to consider simplicity, because this code probably has to be audited in a very short amount of time. If we include PostgREST, we might become unauditable because an entire audit of the PostgREST-version we use, might have to be done.
I use 14 as X, I was not my purpose to repeat that discussion. The point about partitioning stays the same. It's a easy optimization that will shave 20% of data. BTW four bytes are overkill anyway.
I agree to export on a hourly rate to a static file (e.g. to a CDN). PostgreSQL and PostgREST could even handle every READ-operation if you would want this (which is probably stupid, because an T interval static export/append), by replicating the database to some read-only database instances, it's easy to horizontal scale this.
I use 14 as X, I was not my purpose to repeat that discussion. The point about partitioning stays the same.
Noted.
It's a easy optimization that will shave 20% of data. BTW four bytes are overkill anyway.
Are you referring to the 4 bytes of the DayNumber?
Those are unit32 values dictated by the Apple/Google standard.
I'm not very keen on diverging from that, but we can shave those 4 bytes off with the file-naming scheme that is also described in: #5
I agree to export on a hourly rate to a static file (e.g. to a CDN). PostgrSQL and PostgREST could even handle every READ-operation if you would want this (which is probably stupid, because an T interval static export/append), by replicating the database to some read-only database instances, it's easy to horizontal scale this.
I agree that It might be useful (especially for the write-side of the back end) so your input is certainly not bad.
The problem is that I don't know if the government has an audited and approved haskell-compiler that can compile PostgREST. And if such a compiler is available, I don't know whether or not PostgREST would pass such an audit.
Those are a few dangerous known-unknowns that could wrack this project.
I'd rather eliminate those by using delivering a backend-application for which an employee of the AIVD (or some other auditor) would only need a couple of hours to understand and sign off on.
Every additional line of code, product or library we add, slows this process down while increasing our potential attack-surface at the same time.
In this case, extreme simplicity is best.
With the client distribution you are assuming that we need to distribute the updates from a set of servers to a set of operational (mobile) clients. However, there are other ways of distribution besides that approach. Firstly, updates could be written as files to a (for the clients read-only) bucket that is replicated with a CDN. This may be a less expensive approach. Secondly, another alternative is to have client devices sync among themselves in a peer-to-peer fashion, using either some structured approach for message passing or a more slowly converging gossip network (or anything in between). The point here is: we are not restricted really to a strict thick server / thin client architecture here.
With the client distribution you are assuming that we need to distribute the updates from a set of servers to a set of operational (mobile) clients. However, there are other ways of distribution besides that approach. Firstly, updates could be written as files to a (for the clients read-only) bucket that is replicated with a CDN. This may be a less expensive approach. Secondly, another alternative is to have client devices sync among themselves in a peer-to-peer fashion, using either some structured approach for message passing or a more slowly converging gossip network (or anything in between). The point here is: we are not restricted really to a strict thick server / thin client architecture here.
Good point!
I think you can find an anwer for your question in what has been discussed here: #4
I'd have a good look at the CF filter in Design2 of DP3T. That saves an order (or two) in size (with better privacy as a side effect).
Secondly I'd use a pyramid download scheme for this; so you can use stupid CDN servers with just 'get if modified'.
So generate day 1, day 2+3 (combined), day 4,5,6,7 combined and day 8 tot 16. For a Daily key (I'd argue for Design 1 and certain Design 2 of DP3T that you can change keys every 15 mins with no real drawbacks and great privacy benefits).
That way a client does not have do download what it does not yet have. And there is not much of a penalty (with get-if-modified) to fetch very regularly. As long as you honour the -has not changed of the CDNs.
Which CDNs are good at.
I'd have a good look at the CF filter in Design2 of DP3T. That saves an order (or two) in size (with better privacy as a side effect).
Secondly I'd use a pyramid download scheme for this; so you can use stupid CDN servers with just 'get if modified'.
So generate day 1, day 2+3 (combined), day 4,5,6,7 combined and day 8 tot 16. For a Daily key (I'd argue for Design 1 and certain Design 2 of DP3T that you can change keys every 15 mins with no real drawbacks and great privacy benefits).
That way a client does not have do download what it does not yet have. And there is not much of a penalty (with get-if-modified) to fetch very regularly. As long as you honour the -has not changed of the CDNs.
Which CDNs are good at.
Can you link to the relevant documents and elaborate further?
@spycrowsoft so the main document is the design document (Design 2) https://github.com/DP-3T/documents/blob/master/DP3T%20White%20Paper.pdf from page 15 onwards/
There is a description of a serialisation in https://github.com/dirkx/DP-3T-Documents/blob/implementation-profile-start/implementation-profiles/profile.md and my code is at https://github.com/dirkx/DP-3T-Documents/tree/editable-version/impl/design-2-openssl-C, the python version is at and the rust implementation is at:
It boils down to roughly 1/3 of the bits you'd normally would have to distribute (the theoretical limit is much lower; and if you tweak the params you can get it (server side driven) down quite far) for NL/BE/LU plus a bit of DE.
Thanks!
I'll look into it.
Meanwhile: Please think about how we can sell the added complexity?
We have to convince regular users and medical specialists and technologists as well. I'm not too worried about technologists, but too much mathematical and/or technological "stuff" might scare the other groups off.
Note: This by no means a rejection of the idea, but it's the next hurdle we have to consider.
Fraction of the bandwidth, less data leakage, less risk of data being abused for smearing / quelling movements of large groups.
And I do not see this as much harder to sell as a particular form of compression.
Everyone knows what 'zip' does. This is just a better zip for this type of sensitive data.