5 ms·

Yes, this is exactly the challenge. It extends far beyond just ad-targeting. On the database side, social network sharding, replication, and caching schemes are

Yes, this is exactly the challenge. It extends far beyond just ad-targeting. On the database side, social network sharding, replication, and caching schemes aren't typically designed based on national origin of users. If you have a full datacenter (i.e. containing databases, not just a frontend or CDN / PoP footprint) in a country, then typically the entire logical data set -- all data for all users worldwide -- is presumably replicated there. Other systems and services will then make assumptions that any object can be looked up with low sub-ms latency. Social networks often contain activity streams and other pages that include content from many users at once. Consider algorithmic ranking of feed content, comments on popular page content, etc: how do you even implement this if even some small subset of the data needs to be fetched from halfway around the world on every page view? Anyway, to answer your original question, friendships are bidirectional associations and would typically be stored in two places: one entry in your db shard, and one entry in your friend's shard. Photos are objects and presumably would be "owned" by a single user or page and located there (at least in terms of the metadata about the photo); however tags may be associations which have entries on multiple shards just like friendships. If some of these shards can only be accessed across a trans-Atlantic link, the entire scheme falls apart due to the latency.

mackman 5y ago
This guy shards. This is the correct answer. "The social graph is tightly interconnected; it is not possible to group users so that cross-partition requests are rare. This means that each TAO follower must be local to a tier of databases holding a complete multi-petabyte copy of the social graph. It would be prohibitively expensive to provide full replicas in every data center. Our solution to this problem is to choose data center locations that are clustered into only a few regions, where the intra-region latency is small (typically less than 1 millisecond). It is then sufficient to store one complete copy of the social graph per region. Figure 2 shows the overall architecture of the master/slave TAO system." https://www.usenix.org/system/files/conference/atc13/atc13-bronson.pdf https://www.usenix.org/system/files/conference/atc13/atc13-b... edit: Oh hah, didn't realize parent was former DB person at FB. I was too, just a few years before :-)
corobo 5y ago
Sounds like the challenge is using peoples' data in a way that isn't scumbaggerific to be honest
- gentleman11 5y ago
  Correct. There would have been no problem if Facebook were not abusing peoples data and trust so dramatically and brazenly, but Europe is forced to do this to deal with the American lawmakers refusing to step up
blablabla123 5y ago
> the entire scheme falls apart due to the latency. Every proper Microservice zoo also has the exact same problem of ownership of data and latency. Holding duplicates of often needed parts of the data works surprisingly well and would also be fine with GDPR.
toast0 5y ago
If this was required, the solution wouldn't be too bad. There is a latency penalty, but in a normal browser on a normal computer, FB doesn't feel that close to the latency minimums as it is. Option A) client sends feed request to all regulatory domains and mixes results itself. Downside is either you'd always see the tail content from all regions, or client would have fetched content it doesn't display. Also, if client has to contact a load balancer in the regulatory domain directly, you're at the mercy of the client's international transit which is often worse than FB's. Option B), like option A, but client sends feed request to nearest server, nearest server bifurcates the request to one per regulatory domain. If regulatory domain is local, satisfy request (with all the sharded queries), otherwise send it to a request processor with local data and do the processing there. Feed request processor mixes the data. Downside, extra memory used holding results waiting for the remote regions to respond and managing more requests in progress. You could get tricky and use recent response times to try to get all responses back around the same time, and reduce the time where you had some region's data in memory, but not all of them, but that's probably silly. Both of these are more work than the current scheme, and nobody likes regulation requiring more work, but still. Figuring out where things are permitted to be stored when they involve people in multiple domains sounds like a headache though. And actually splitting the data once the parameters are clear doesn't sound like my kind of fun either. Disclosure: I worked at FB, but not with FB user data.
- evanelias 5y ago
  As someone who spent a decade working on databases and scalability at multiple social networks (including FB), I believe this problem is substantially more difficult than you're taking into consideration here. Viewing a couple pages of my news feed randomly just now, I see content from a mix of friends in the U.S., Ireland, Germany, the U.K., and Hong Kong. The content is algorithmically ranked and sorted, and then paginated. Similar situation with viewing comments on popular pages, which may span many countries. If ranking/sorting is performed either client-side (your option A) or even in a nearby aggregation server (B), each and every user-facing pageload of N posts/comments/whatever would need to fetch the worst-case of N entries from each regulatory domain, and then re-rank/sort/paginate the aggregation of them. This presents numerous significant problems: not just network latency on every single page load (which would be severe), but also bandwidth consumption, memory, and cpu wherever the aggregation/ranking are being performed. I don't think your option A is even feasible for a worldwide social network, with many users in countries where less powerful devices are prevalent. Even option B would have scary implications for the worldwide increase in network bandwidth consumption alone. And that's not even considering the problem of how you migrate one of the largest data sets in human history from a non-geo-sharded topology to a geo-sharded one. Worst-case, multiply all of this effort (and bandwidth impact) by every single multi-national social network, publishing platform, and user-generated content site/app/product. The GDPR-compliance efforts of 2017-2018, which were quite substantial at all of these companies, would look like peanuts in comparison.
oldgregg 5y ago
There is an assumption that everything in the world should have 10ms latency. Why? Borders have always been meaningful to protect unique people groups. Maybe the extra latency is a way to protect indigenous cultures and allow local solutions to compete with Facebook. There are indigenous people groups all over the world where governments have said "leave those people alone!" American tech companies have done FAR more to destroy local cultures than missionaries could have ever dreamed of. Just because you can doesn't mean you should. Ultimately where it's going is that to the degree Facebook can't buy off all the local politicians it's going to have to follow the local laws and have unique policies for each jurisdiction. Ideally you would just have local companies running the social network, enforcing local norms, with federated APIs to communicate globally. Unfortunately the tech companies already control so much media and mindshare they are gonna probably keep that from happening in most places.
trasz 5y ago
So Facebook would have to redesign their sharding. Who cares? Also, let's not forget that we're talking about a service with absolutely horrible reliability. Facebook only cares about reliability at scale; at a single person level reliability is quite poor; you can suddenly discover that your random post has 60 thousand likes (for a few minutes), or a friend of yours has a new post (they don't). Thus, the questions of "what if something has >10ms latency" don't really matter - Facebook fails much worse than that all the time.
- evanelias 5y ago
  > So Facebook would have to redesign their sharding. Who cares? Do you believe Facebook is the only company that would ever be affected by this? Personally I strongly suspect that once the precedent is set -- that is, regulation requiring user data to remain strictly on servers in the user's country and nowhere else -- the entire tech industry would be severely impacted. > the questions of "what if something has >10ms latency" don't really matter Internal point lookups for each individual piece of content would go from sub-ms (intra-region) to now being upwards of 200ms (network requests spanning the globe). And for many social applications, a given page contains content from dozens of sources. Much of this could be parallelized, but even then, the total wall time for each parallelized multi-get is determined by whichever source had the worst-case latency. In any case, we're not just talking about tens of ms of impact here, but rather a latency increase of 2 orders of magnitude (or more!) for even the simplest lookup operations.
  - trasz 5y ago
    > Do you believe Facebook is the only company that would ever be affected by this? Of course not, Facebook is not the only company parasitizing on users' privacy. The point still stands, though: it's an absolutely tiny (compared to the company's income) amount of work, versus users's rights. As for delays - again, FB routinely displays much worse problems, adding some more delay there wouldn't be noticeable.
  - teachingassist 5y ago
    > Do you believe Facebook is the only company that would ever be affected by this? It's quite clear that GDPR allows data to cross the border, if particular safeguards are guaranteed by the data recipient. That continues to be the advice generally given following the rejection of "Privacy Shield" e.g. by https://gdpr-info.eu/issues/third-countries/ https://gdpr-info.eu/issues/third-countries/ This particular ruling affects only Facebook (and is specifically against Facebook), because it is only Facebook that has here been identified as failing to offer those safeguards. Google similarly is a tech giant operating across this border, and doesn't currently face such a sanction.

mackman 5y ago

This guy shards. This is the correct answer. "The social graph is tightly interconnected; it is not possible to group users so that cross-partition requests are rare. This means that each TAO follower must be local to a tier of databases holding a complete multi-petabyte copy of the social graph. It would be prohibitively expensive to provide full replicas in every data center. Our solution to this problem is to choose data center locations that are clustered into only a few regions, where the intra-region latency is small (typically less than 1 millisecond). It is then sufficient to store one complete copy of the social graph per region. Figure 2 shows the overall architecture of the master/slave TAO system." https://www.usenix.org/system/files/conference/atc13/atc13-bronson.pdf https://www.usenix.org/system/files/conference/atc13/atc13-b... edit: Oh hah, didn't realize parent was former DB person at FB. I was too, just a few years before :-)

corobo 5y ago

Sounds like the challenge is using peoples' data in a way that isn't scumbaggerific to be honest

gentleman11 5y ago
Correct. There would have been no problem if Facebook were not abusing peoples data and trust so dramatically and brazenly, but Europe is forced to do this to deal with the American lawmakers refusing to step up

blablabla123 5y ago

> the entire scheme falls apart due to the latency. Every proper Microservice zoo also has the exact same problem of ownership of data and latency. Holding duplicates of often needed parts of the data works surprisingly well and would also be fine with GDPR.

toast0 5y ago

If this was required, the solution wouldn't be too bad. There is a latency penalty, but in a normal browser on a normal computer, FB doesn't feel that close to the latency minimums as it is. Option A) client sends feed request to all regulatory domains and mixes results itself. Downside is either you'd always see the tail content from all regions, or client would have fetched content it doesn't display. Also, if client has to contact a load balancer in the regulatory domain directly, you're at the mercy of the client's international transit which is often worse than FB's. Option B), like option A, but client sends feed request to nearest server, nearest server bifurcates the request to one per regulatory domain. If regulatory domain is local, satisfy request (with all the sharded queries), otherwise send it to a request processor with local data and do the processing there. Feed request processor mixes the data. Downside, extra memory used holding results waiting for the remote regions to respond and managing more requests in progress. You could get tricky and use recent response times to try to get all responses back around the same time, and reduce the time where you had some region's data in memory, but not all of them, but that's probably silly. Both of these are more work than the current scheme, and nobody likes regulation requiring more work, but still. Figuring out where things are permitted to be stored when they involve people in multiple domains sounds like a headache though. And actually splitting the data once the parameters are clear doesn't sound like my kind of fun either. Disclosure: I worked at FB, but not with FB user data.

evanelias 5y ago
As someone who spent a decade working on databases and scalability at multiple social networks (including FB), I believe this problem is substantially more difficult than you're taking into consideration here. Viewing a couple pages of my news feed randomly just now, I see content from a mix of friends in the U.S., Ireland, Germany, the U.K., and Hong Kong. The content is algorithmically ranked and sorted, and then paginated. Similar situation with viewing comments on popular pages, which may span many countries. If ranking/sorting is performed either client-side (your option A) or even in a nearby aggregation server (B), each and every user-facing pageload of N posts/comments/whatever would need to fetch the worst-case of N entries from each regulatory domain, and then re-rank/sort/paginate the aggregation of them. This presents numerous significant problems: not just network latency on every single page load (which would be severe), but also bandwidth consumption, memory, and cpu wherever the aggregation/ranking are being performed. I don't think your option A is even feasible for a worldwide social network, with many users in countries where less powerful devices are prevalent. Even option B would have scary implications for the worldwide increase in network bandwidth consumption alone. And that's not even considering the problem of how you migrate one of the largest data sets in human history from a non-geo-sharded topology to a geo-sharded one. Worst-case, multiply all of this effort (and bandwidth impact) by every single multi-national social network, publishing platform, and user-generated content site/app/product. The GDPR-compliance efforts of 2017-2018, which were quite substantial at all of these companies, would look like peanuts in comparison.

oldgregg 5y ago

There is an assumption that everything in the world should have 10ms latency. Why? Borders have always been meaningful to protect unique people groups. Maybe the extra latency is a way to protect indigenous cultures and allow local solutions to compete with Facebook. There are indigenous people groups all over the world where governments have said "leave those people alone!" American tech companies have done FAR more to destroy local cultures than missionaries could have ever dreamed of. Just because you can doesn't mean you should. Ultimately where it's going is that to the degree Facebook can't buy off all the local politicians it's going to have to follow the local laws and have unique policies for each jurisdiction. Ideally you would just have local companies running the social network, enforcing local norms, with federated APIs to communicate globally. Unfortunately the tech companies already control so much media and mindshare they are gonna probably keep that from happening in most places.

trasz 5y ago

So Facebook would have to redesign their sharding. Who cares? Also, let's not forget that we're talking about a service with absolutely horrible reliability. Facebook only cares about reliability at scale; at a single person level reliability is quite poor; you can suddenly discover that your random post has 60 thousand likes (for a few minutes), or a friend of yours has a new post (they don't). Thus, the questions of "what if something has >10ms latency" don't really matter - Facebook fails much worse than that all the time.

evanelias 5y ago
> So Facebook would have to redesign their sharding. Who cares? Do you believe Facebook is the only company that would ever be affected by this? Personally I strongly suspect that once the precedent is set -- that is, regulation requiring user data to remain strictly on servers in the user's country and nowhere else -- the entire tech industry would be severely impacted. > the questions of "what if something has >10ms latency" don't really matter Internal point lookups for each individual piece of content would go from sub-ms (intra-region) to now being upwards of 200ms (network requests spanning the globe). And for many social applications, a given page contains content from dozens of sources. Much of this could be parallelized, but even then, the total wall time for each parallelized multi-get is determined by whichever source had the worst-case latency. In any case, we're not just talking about tens of ms of impact here, but rather a latency increase of 2 orders of magnitude (or more!) for even the simplest lookup operations.
- trasz 5y ago
  > Do you believe Facebook is the only company that would ever be affected by this? Of course not, Facebook is not the only company parasitizing on users' privacy. The point still stands, though: it's an absolutely tiny (compared to the company's income) amount of work, versus users's rights. As for delays - again, FB routinely displays much worse problems, adding some more delay there wouldn't be noticeable.
- teachingassist 5y ago
  > Do you believe Facebook is the only company that would ever be affected by this? It's quite clear that GDPR allows data to cross the border, if particular safeguards are guaranteed by the data recipient. That continues to be the advice generally given following the rejection of "Privacy Shield" e.g. by https://gdpr-info.eu/issues/third-countries/ https://gdpr-info.eu/issues/third-countries/ This particular ruling affects only Facebook (and is specifically against Facebook), because it is only Facebook that has here been identified as failing to offer those safeguards. Google similarly is a tech giant operating across this border, and doesn't currently face such a sanction.