Work in Progress

Design Goals

Circa 2007, much of Facebook's codebase was littered with explicit policy checks in the display/presentation layer:

if (can_see($user_id, $object_id)) {
  // Show this thing to the user.
} else {
  // Show an empty state or 404.
}

The major issue with this approach was that it is fragile.

Among other reasons, this approach is fragile because it is default-permit (by default, things are allowed unless you remember to add the right policy check) and violates DRY (the right set of policy checks would end up encoded in multiple places in the application). A practical issue this caused was that the mobile site and desktop site sometimes had different policy behavior. The mobile site had essentially been copy/pasted from the desktop site at one point, and the policy checks used by each site either differed or diverged over time. Policy behavior occasionally even differed on the main site, if two different interfaces let you accomplish a similar goal and they were not updated with exactly the same policy rules. Later, the API could sometimes diverge from the desktop site and from the mobile site.

When policy behavior differed, one interface was almost inevitably too permissive because the policy implementation was default-permit: if you forgot to perform a check, or a new rule was added to the desktop site and not to the mobile site, the consequence was a missing check which should have been in place, and a capability given to the user which they should not have had.

As a less serious concern, this approach was also slow. PHP application performance is a larger issue and not directly relevant to understanding the Phabricator query layer, but two broad issues were operation on single objects instead of lists of objects (which often resulted in inefficiencies) and passing IDs instead of objects (which, given the state of application architecture at the time, tended to devolve into a lot of expensive and complicated cache queries).

I designed Phabricator's query layer primarily to remove the fragility from this system. The Phabricator query layer accepts a $viewer and implements all the visibility policy rules, never returning objects which the viewer can not see. As long as callers use this layer non-abusively, they're guaranteed to get correct, consistent policy behavior automatically. And all the policy rules live and execute in one place, so they can be updated easily without changing application code.

Phabricator's query layer doesn't make policy implementation impossible to get wrong, but it makes it easy to implement the right behavior and hard to make mistakes.

Simply, the core ideas are:

• Require a viewer to query objects.
• Implement visibility policies inside the query layer: do not return objects the viewer can not see.
• Require a special "omnipotent" viewer to violate policies: policy violation is a non-default mode which you have to clearly and explicitly enable.

Policy-Aware Queries and Paging

Most objects in Phabricator support individual "Visible To" policy controls which let you choose who can see each object. For example, you can set one task in Maniphest to be visible to "All Users", and another to be visible to "Only alice".

These policies are potentially complex (they may have multiple conditions and depend on things like project membership and lunar phase) and can not be evaluated by MySQL: it is not possible, or at least not realistic, to build a SQL query which returns only results which are visible to the viewer. MySQL can apply almost all other constraints (and even some policy constraints) but policies must be evaluated in the application layer after MySQL returns results.

Much of the complexity of the query layer is related to filtering and paging results without disclosing information to the viewer.

Simple pagination systems often use offset-based paging. The first few pages of results looks like this:

/stuff/
/stuff/?offset=100
/stuff/?offset=200
...

Under the hood, this is implemented in MySQL by adding ... LIMIT 300, 100 to the end of the query.

This is very easy to implement and performs well (MySQL can apply an offset and limit very efficiently). However, it is unsuitable for paging objects which may be filtered by the application after MySQL returns results.

The first query will return 100 results from MySQL, but after policy filtering you may have fewer results to show to the user, and possibly even 0 results. Users reasonably expect each page to have a consistent number of results, say 100, not 80 or 32 or 0, and not 100 on some pages and 73 on others. The page the application should show to the user is "the first 100 visible results", not "the first 100 results". If you fetch 100 results from MySQL and filter some, you need to go fetch more results from MySQL and keep filtering until you get 100 visible results.

After doing this, you may have consumed a larger number of actual rows. For example, you selected 130 total rows and filtered 30 results as not visible to the viewer.

A simple way to continue using offset-based paging is to move the LIMIT operation from MySQL to the application. To apply ?offset=100, you load and filter 200 results, then throw away the first 100 so you're left with visible results 101-200. You return these to the user.

This is straightforward and works well, and is how paging through videos worked at Facebook for quite a while. The major problem is that the cost to generate a page is now proportional to the page offset: to apply ?offset=600, you must load and filter 700 results, then discard the first 600. To apply ?offset=1300, you must load and filter 1400 results, then discard the first 1300. Each time the user clicks "Next Page", the page becomes slower and slower. When Facebook's video list worked like this, it was impossible to page very far back in a list of videos because the page became too slow to render before being timed out. This slowdown is fairly linear and applies even if most results are visible. So: this approach is simple, but scales very poorly.

Another approach is to keep track of how many rows you examined, and use that as the offset. If you examine 130 rows and filter away 30 before ending up with 100 visible results, you retain the raw count of examined rows and make the second page ?offset=130.

This is relatively easy, works well, and scales well. However, it discloses information to the viewer about how many results were filtered: they can determine how many objects matched their query constraints but were filtered by examining the offset value. This might be acceptable in some applications, or if available queries have very limited power. In Phabricator, users have access to sufficiently powerful queries (e.g., freeform text) to deduce a substantial amount of information about objects they don't have permission to see if they're given information about how many results were filtered.

Another approach is to keep track of the database offset, but not show it to the user. Instead, save it in some cursor object ({"offset":130}) and return a reference to that cursor (?cursor_id=32nf1x). This solves the information disclosure problem, but every query result must now perform a write to save the cursor, and the cursor must either be retained indefinitely or the "next page" link allowed to expire when the cursor is garbage collected.

The approach Phabricator uses is to keep track of the last result which was shown to the user, then use that as the starting point for the next query (?after_object_id=239). This solves the performance problem, solves the information disclosure problem, and doesn't require a write or expire. However, it generally makes the paging logic in the query layer more complex.

Overheating

What if a viewer can see very few objects, or none at all? For example, if an install has a million open tasks but the view policies prevent the user from seeing any of them, or allow them to see only 15 at the very end.

The query layer will begin to read rows, apply policies, and discard results which the viewer can't see. If allowed to continue this process indefinitely, it would load and policy check every object, which could take an arbitrarily long (but finite) time. Users often prefer not to wait for an arbitrarily long amount of time, even with the substantial assurance that the duration of their wait is finite.

One way we can mitigate this is to apply more policy checks in MySQL so that fewer rows are returned for evaluation at the application level. When possible, this is generally a good solution, and it's a solution we use in some cases (like the implementation of Spaces). However, many policies are too complex to realistically represent in SQL so this isn't a complete solution in the general case.

The approach the query layer uses instead is to let queries "overheat". When a query filters too many results without finding an entire page of visible results, it triggers an "overheated" failure state, similar to a timeout. It returns any results it found and the query is marked as "overheated". Today, the UI renders guidance for the user about this ("Try adding more constraints to your query so it matches fewer results."). Context and technical details about overheating can be found in T11773.

This behavior is not ideal, but we can not guarantee we can find the first page of results in a reasonable amount of time, since we may need to process an arbitrarily large number of objects to find a full page of visible objects (or determine that no such page exists by exhaustion).

Generally, it is rare for queries to overheat. In normal situations, most users can see most objects on most installs. Where they can't, Spaces are the most common tool used to silo large blocks of objects away, and policies from Spaces can be evaluated and discarded very efficiently in MySQL, so hiding a lot of stuff with Spaces doesn't tend to cause overheating. Users also normally search for objects they can see (for example: tasks assigned to them, revisions they've been asked to review) and rarely search for objects they can't see.