Allow recursive references in fragments selection subsets #929
Comments
|
As a note: GraphQL the language is purposefully not Turing Complete: you must not be able to create an operation which, when executed with known-to-halt resolvers, does not halt. Basically, if all your scalar field resolvers always just return a value (and do no additional server work), and your non-scalar field resolvers just create a Map/JSON Object out of the resolved child fields, is it possible to create an operation that will not complete its execution? We know it's possible to have GraphQL not complete if you have a field resolver that doesn't halt, but if you assume all resolvers halt then is it guaranteed that the operation halts too? I believe proving that will be a requirement to adding any recursion to fragments. Or we'd need to gain consensus that we want to allow operations that might not halt. |
|
GraphQL is not a programming language. So I believe Turing-complete stuff is out of place here.
Allow me to respectfully disagree. IMO: requirement to adding something to spec is to show that benefits of the change are bigger than potential drawbacks or added complexity. I think I provided enough arguments for this. |
Discussion of RecursiveFragments, response to arguments in WG meeting Feb 03, 2022Before responding to particular argumentats expressed in the meeting, let me give you an idea how it looks for a server developer. It is important, since the recursive fragments feature mostly concerns the server side, the complexity and 'safety' of processing. I will refer to this material later in my counter-arguments for args expressed in the meeting. How the problem of recursive fragments is seen by a server devContext: a server dev reads GraphQL spec or some introductory material for the first time. All right, I am reading GraphQL spec. You can ask for multiple things in one query, cool! No more multiple roundtrips to the server. And you can go deep into child objects and lists! Cool! So the client can express exactly what fields and child/grandchild objects it wants and what fields there... Very cool! But...!!! Clearly it is so easy to produce a ROGUE, BAD query - by mistake or by evil intent - that will overwhelm my server, hog all resources and eventually kill/DDOS it with a few repeats. I better start thinking early about ways to protect the server. I will use this Facebook-like model/Query as an example: query {
user(id: 123) {
name friends {name friends {name friends {name friends {name} }}}
}
}Considering that it's not unusual for a user to have 500+ "friends", this query will definitely blow up into millions. And has to be aborted. Yes, I am not Facebook, but my model has similar type relations with list fields, and the difference for me is just that rogue query needs to be a couple of nesting layers longer. By the way, even if this Facebook API limits friends to 100/query, all bad guy needs to do is add a few more levels, to get the same 'explosion' into millions. So... what should I do? Static analysis of the query would not help. Just limiting nesting level to say 5 - that's too restrictive for valid queries with limited size collections. Clearly, it's all dynamic, in the actual data, all depends on actual size of particular data 'slices'. I need to introduce a lot of stoppers, limiters, circuit breakers in my server code. And limiting values would not be constant, depend on 'user'. What's allowed to internal import process should not be allowed to external anonymous user. So it is a system of quotas, varying by user/customer, most likely. Max values for return objects, response sizes, resolving nesting levels, processing time limits, total number of field values in response, total size of the response etc. I need many of these because it does not look like any single one can protect the server. Continuing reading. Oh, fragments - cool. Ah, spec prohibits recursion in fragments... Well, does not change much, one can abuse the hell out of a server without any recursion. Hmm.. spec wants me to detect cycles early, with static analysis? Ok, doable, not a rocket science, finding loops in graphs, well known algorithms. Will code it and run for every incoming query. But wait... this code will be running for all incoming queries?! Many many of them. For almost all of them, nothing will be detected. Only one in a million/zillion bad query will have a deadly loop. But would this query be stopped and aborted by dynamic limitors and circuit breakers I already have? Of course! Would the request do much damage before it is aborted? No, just like with other rogue quieries, an effective protection must be in place. And punishing system as well - if client tries to repeat the query multiple times, just cut him off for an hour or a year, to prevent DDoS. With or without fragment recursion, rogue queries are detected, aborted and the server is protected. But then it means that this static analysis is just a waste of CPU cycles for all queries; and with a redundant result for quite rare and exceptional event of a BAD query. So hell with the static analysis of fragment loops, disable it, cut the waste. Remove the code - any non-trivial but not used code sitting in the repo is no good. Then will my server become non-compliant with the spec? NO - any valid query is handled as before. But also YES, sort of, invalid query with fragment loop, although rejected (correct behavior), but rejected kinda late, and the rejection/error is not kind of compliant. Do I care? - not really. (end of server dev thoughts) So that is the train of thought and action; I do believe I represented it accurately for a typical server dev. The main conclusion is: Allowing Recursive Fragments does NOT make it easier to misuse or abuse a GraphQL API - it is already REALLY EASY without them. The server should have (already has!) a protection system built to defend against ANY bad query. Allowing recursive refs DOES NOT create any new problems for server developers, and is in fact IRRELEVANT. Specific points in Feb 03 discussionAnswering the arguments in discussion at WG meeting on Feb 03, 2022; as recorded in meeting notes here:
Responses and counter-arguments:
I do not think 'themselves' is the right term - who is DDoS-ing who? A client sends 'arrogant' request that overloads the server, multiple bad requests maybe (DDoS?). It is easy enough to do with or without recursion as I explained before. Recursion does not make any difference.
Sorry, Lee, that's not important at all. Because there's no 'halting problem' - server process has a hard stop at 50 cycles/nesting levels (100 or whatever). I don't care if the query would halt eventually (after 10K cycles? 1 million cycles?) or if it does NOT halt at all. Hard stop; one of many circuit breakers for different 'query complexity/required effort' indicators - that work for non-recursive queries as well. Any server MUST have these limiters. So there is NO 'stopping problem', at all. By the way, the limiting number (max iter) should NOT come with the query, from the client. It is a strict server limit, so we do NOT need to discuss any extra directive (@maxiter?) as you did in the past.
Well, we are not that different I think. One of possible semantic/mental models of a GraphQL query is that a Query is a set of invocations of fields - which are methods, especially clear when there are arguments; and there is method on the server - resolver, which we invoke remotely. So GraphQL query is a kind of list of remote proc calls - then GraphQL is a kind of a programming language, for encoding RPC calls. Sounds reasonable I think. Fragments are separate functions that can be invoked from 'mainline' code. And these functions - well, may be called recursively, maybe. Even if GraphQL is really VERY different - many things still apply. The principle of the 'least surprise'. Whenever we introduce a concept that is similar to something that the reader already knows, we should not 'surprise' with behavior that is different from reader's expectations. But if it is different, then it requires lengthy explanations of this difference in the spec. And the reader has to remember that "X is different in GraphQL'. We must try to reduce the 'mental load' on readers, cut-off all the unneeded 'fat' - unless it is really important for us and GraphQL to be different. What could be a simple one-sentence comment like 'Recursion OK, but servers - beware of infinite loops' - instead we have a whole section, larger than a page, explaining in details an absolutely trivial case - how you screw up with recursion. Even more surprising for a reader, after going thru this - wait, other real programming languages face the same problem/challenge. But they do NOT prohibit recursion nevertheless. We say 'we are different', GraphQL is not a programming language. OK, but it would not be clear to the spec reader what's so different here.
We don't have any 'safety' today. As I explained with users/friends example, it is already very easy to abuse the API, without any fragment recursion. Allowing recursion does not change anything regarding safety.
I bring up one case - a server dev thinking about this whole issue. And that it makes sense to disable this static check for fragment cycles if he ends up coding it - it is wasteful and useless. It would burn CPU cycles for all good queries with 0 effect, and once in a million queries would find something that would be detected anyway. If this is not convincing, I don't know what would be. Basically what we ended up with here is a feature that likely will be disabled. In conclusionThe reason I do not give up and keep beating on this is not that I think that recursive fragments are so crucially important - they are not. But this small issue is just one example of a stuff that is in the spec, but should not be there; there are other cases like this, and I intend to bring them up. Pushing the spec forward is not only adding stuff, but it is also important to 'optimize' it, cut off the fluff that does not belong there. |
|
I do humbly agree with @rivantsov on this and think the most profound point made here is that malicious queries can already overwhelm GraphQL APIs regardless of whether recursive fragments are involved. In this regard, the backend developer must already be conscious of thinking ahead for how to best protect the server. Therefore, allowing recursive references in fragments could be an opt-in feature, perhaps restricted in scope to usage on only certain types and/or fields. @rivantsov provided the example of a client wanting to resolve all managerial levels of an organization without making assumptions on query depth. In these cases, where one is dealing with acyclic data it would be great to allow a client to flexibly request the full-graph in a structured response. Another example would be the product tree typical in CAD software: type Query {
parts: [Part!]
}
type Part {
name: String
created: DateTime!
children: [Part]
}
fragment allParts on Part {
name
children {
...allParts
}
}
# Resolve full product tree using recursive references in fragment
query {
parts {
...allParts
}
}I see that this topic was discussed in the GraphQL Spec WG, are there currently any plans for a follow up on that discussion? |
|
Hi, and thank you for your support! At the time of WG meeting in Feb, the outcome was - need real-life examples why it's needed. So sounded like I needed to bring in a few people like John TheHacker who would testify that he definitely needs it for his new project yada-yada blah blah. So I in fact just gave up. IMHO, the situation should be opposite, we FORBID something in the spec, bring in restriction, and we should have arguments or real-life cases FOR doing this. But whatever, looks like the issue resurfaced. We can bring it up again in the next meeting, I might sign-up and add agenda item (really busy with other urgent stuff now). But if I do, please attend and voice your support please! Thank you |
To be clear: I am not in favour of recursive fragments. Struct does not have recursive fragments, as currently proposed it doesn't allow fragments at all in fact (though that may change). Struct allows for pure data to be finitely recursive on output in a similar way to how an
You shouldn't give people things and then take them away in a future release, that's a breaking change. GraphQL's approach is to be conservative in what we offer and remove restrictions as the needs arise (and the trade-offs are evaluated). |
|
hmm.. sorry for misunderstanding of your intents in STRUCT.
Regarding breaking backwards compatibility. This is not 'taking things away', this is allowing MORE. Allowing recursive fragments (RF) do not break any old stuff. All old engines and queries (that did not have RF) - still continue to work. We now ALLOW extra stuff - for servers to support RFs if they want to and for devs to use these in queries. |
|
+1 |
|
I've just stumbled across this issue and want to voice my support. There are many cases where recursive queries will be useful for describing acyclic data. One major example of this is for any graph that can be represented as a hierarchy or tree. As a compromise for the objections, would it be possible to add a built-in This way it is up to the server/schema to declare whether recursion is allowed for that field and the client has to knowingly request recursive data. This makes it explicit when recursion is requested and allowed and static analysis can easily check that |
|
+1 - this would be a useful, practical addition to the schema. |
|
I have come across this issue and believe our API would benefit from allowing recursive GraphQL queries. Our schema contains types that have a field of the same type, but the overall data structure is still finite and acyclic. Without recursive query support, one is forced into awkward workarounds like:
Being able to write a recursive query would make this situation a lot simpler. |
|
@AlexKubiesa Please could you expand with a concrete example? |
|
OK, here is a subset of the old version of our electronics design schema. # ...
type DesCadDesign {
# ...
boardOutline: DesCadComplexShape
# ...
}
interface DesCadGeometricShape {
shapeType: DesCadGeometricShapeType!
startPoint: DesCadPoint!
endPoint: DesCadPoint!
}
enum DesCadGeometricShapeType {
ARC
B_SPLINE
CIRCLE
COMPLEX
ELLIPSE
ELLIPTICAL_ARC
PARABOLA
POLYLINE
ARC_SIMPLE
}
type DesCadComplexShape implements DesCadGeometricShape {
isHole: Boolean!
shapes: [DesCadGeometricShape!]
shapeType: DesCadGeometricShapeType!
startPoint: DesCadPoint!
endPoint: DesCadPoint!
}
type DesCadCircleShape implements DesCadGeometricShape {
diameter: Int!
center: DesCadPoint!
shapeType: DesCadGeometricShapeType!
startPoint: DesCadPoint!
endPoint: DesCadPoint!
}
type DesCadPolylineShape implements DesCadGeometricShape {
points: [DesCadPoint!]!
shapeType: DesCadGeometricShapeType!
startPoint: DesCadPoint!
endPoint: DesCadPoint!
}
# ...I didn't include all the shape types but as you can see, we have To query this API, the client would need to write a query including fragments like this: # ...
fragment MyCadDesign on DesCadDesign {
# ...
boardOutline {...MyCadComplexShape}
# ...
}
fragment MyCadGeometricShape on DesCadGeometricShape {
shapeType
startPoint {...MyCadPoint}
endPoint {...MyCadPoint}
...MyCadArcShape
...MyCadSimpleArcShape
...MyCadBSplineShape
...MyCadCircleShape
...MyCadEllipseShape
...MyCadEllipticalArcShape
...MyCadParabolaShape
...MyCadPolylineShape
...MyCadComplexShape
}
fragment MyCadGeometricShape2 on DesCadGeometricShape {
shapeType
startPoint {...MyCadPoint}
endPoint {...MyCadPoint}
...MyCadArcShape
...MyCadSimpleArcShape
...MyCadBSplineShape
...MyCadCircleShape
...MyCadEllipseShape
...MyCadEllipticalArcShape
...MyCadParabolaShape
...MyCadPolylineShape
...MyCadComplexShape2
}
fragment MyCadGeometricShape3 on DesCadGeometricShape {
shapeType
startPoint {...MyCadPoint}
endPoint {...MyCadPoint}
...MyCadArcShape
...MyCadSimpleArcShape
...MyCadBSplineShape
...MyCadCircleShape
...MyCadEllipseShape
...MyCadEllipticalArcShape
...MyCadParabolaShape
...MyCadPolylineShape
}
fragment MyCadComplexShape on DesCadComplexShape {
isHole
shapes {...MyCadGeometricShape2}
}
fragment MyCadComplexShape2 on DesCadComplexShape {
isHole
shapes {...MyCadGeometricShape3}
}
fragment MyCadCircleShape on DesCadCircleShape {
diameter
center {...MyCadPoint}
}
fragment MyCadPolylineShape on DesCadPolylineShape {
points {...MyCadPoint}
}
# ...And that's assuming there are only 3 levels, there may be more. In the end we felt this was too big an ask for our clients, so we just changed |
|
@AlexKubiesa Please could you look at the https://github.com/graphql/graphql-wg/blob/main/rfcs/Struct.md |
|
@AlexKubiesa the use case seems closely related to what I was referring to here #929 (comment) Would your clients benefit from being able to formulate a query like: give me the start and end points of all sub-shapes? I ask since the struct RFC of @benjie (which I really like by the way!) doesn't allow selection sets to apply recursively. Please correct me if I'm wrong @benjie |
|
@skilkis Indeed it doesn’t BUT omitting the selection set for a field will return everything in that field as if you had exhaustively written the selection sets recursively. The result being that you can simply query the |
|
@benjie @skilkis thank you for your suggestions. The Struct RFC feels like a good fit. Our current use case involves a client querying the whole board outline, making some local modifications, and then uploading the whole modified outline (like the RESTful PUT described in the RFC). So, having a complex type that functions as both an input and output is quite appealing. It would allow our clients to use strongly-typed client libraries like Strawberry Shake without having to set up an input-to-output type mapping. I think we could switch to union-based polymorphism quite easily. #929 (comment) would also address the recursion issue, but doesn't address the input-vs-output issue. |
|
Thank you for the datapoint @AlexKubiesa 🙌 |
|
I wanted to share my use case which is along the lines of this and the structs proposal. I'm not sure where to share this but I think perhaps this issue is the right place. I develop and maintain Ordbok API which is a public and free GraphQL API for data from the Norwegian dictionaries (Yes, there's multiple. It's a long story). One of the use cases I have for finite recursion is definitions in dictionary articles, which can have subdefinitions, which can themselves have subdefinitions, and so forth. Currently, writing a query would require writing a lot of boilerplate up to a specified depth past which the user can reasonably expect there not to be any further subdefinitions, as the depth can vary from article to article. Some definitions have more depth than one may expect. Each definition has multiple fields that may or may not be desired by the client application. This includes, for example, content in either plain text or structured formats, or relationships to other articles on a definition level, or other data a definition contains. Thus it is desirable to maintain the ability to pick what fields the user desires while still allowing recursion to a reasonable depth. Here's what queries have to look like currently: # Fragment using textContent instead of richContent for simple use cases
fragment DefinitionContent on Definition {
content {
textContent
}
examples {
textContent
}
}
query WordDefinitions(
$word: String!
$dictionaries: [Dictionary!]
$wordClass: WordClass
) {
word(word: $word, dictionaries: $dictionaries, wordClass: $wordClass) {
articles {
id
dictionary
lemmas {
lemma
}
gender
wordClass
definitions {
...DefinitionContent
subDefinitions {
...DefinitionContent
subDefinitions {
...DefinitionContent
subDefinitions {
...DefinitionContent
subDefinitions {
...DefinitionContent
subDefinitions {
...DefinitionContent
subDefinitions {
...DefinitionContent
subDefinitions {
...DefinitionContent
}
}
}
}
}
}
}
}
}
}
}What would be much preferable is some kind of recursion-friendly syntax that would continue to allow users to select the fields they need from a Definition. A naive example with fragments could be: fragment DefinitionContent on Definition {
content {
textContent
}
examples {
textContent
}
subDefinitions {
...DefinitionContent
}
}
query WordDefinitions(
$word: String!
$dictionaries: [Dictionary!]
$wordClass: WordClass
) {
word(word: $word, dictionaries: $dictionaries, wordClass: $wordClass) {
articles {
id
dictionary
lemmas {
lemma
}
gender
wordClass
definitions {
...DefinitionContent
}
}
}
}However, of course, infinite recursion is a problem in other use cases though it is not in mine. |
|
@adalinesimonian at some point you probably don't intend to show the entire tree of recursive subdefinitions on a single screen. At which point the recommended pattern would be to split into a recursive query rather then rely on recursive fragments: You can choose how deep to recursively request subdefinitions in a single round trip, and you can recurse infinitely via a pattern similar to pagination, but what you will not accidentally do is DDOS yourself because someone added a cyclically-referential subdefinition. |
The most common use case for definitions is to display the entire definition tree. Though it may be deep, it does not necessarily take up that much room, or at least not that much room relatively speaking. And even when it does, the data is usually needed all together as most client implementations are not displaying articles in parts when definitions are included in the response. There are certain use cases where it's possible that the client may not want the entire definition tree all at once, but those use cases for this particular API are not the majority.
With the way the data is stored, it's impossible for a cyclical subdefinition to be added. Each article is stored as a JSON document in Redis, and so is the definition tree per article. When the definitions are requested, they are processed from the document that is retrieved from Redis, according to the client's demands (e.g. returning rich content with article references or just plain text, etc.). Unless Redis finds a way to allow infinitely long key values, we'll be fine on that front. A limitation of the dataset is that subdefinition IDs are not unique dataset but to each article. Together with the fact that articles and subdefinitions are stored together as documents means that querying by a subdefinition ID would require passing in the article ID to know which subdefinition to query. Currently, the server implementation is quite straightforward (with the one exception being data processing) and is easily able to respond to definition data requests without any additional implementation work as the data is available on the object retrieved from the database with all definitions attached to it, given how the dataset is structured (something I have little control over — academia, etc. etc.). Definitions aside, there are other areas where such recursion could and would result in infinite recursion, for example, references to related articles. While definitions are guaranteed to never infinitely recurse, this is not true with references to articles. The word skule may be related to lærar, which in turn may be related back to skule. Infinite recursion with the article object is a real danger and is why I am not particularly in favour of syntax like what I naively wrote earlier. Otherwise it would send my server into a loop I don't want it to be in. Some kind of way to indicate a maximum recursion depth per key, both on the server and the client, would make it such that the client still can send really intuitive queries but without the risk of a ridiculous response from the server. I've read the structs proposal, but am not entirely certain what the equivalent may look like in that paradigm. Here's a naive and by no means perfect (read: ugly) approach using fragments. I'm not advocating for this specific syntax as much as the ability to effectively do something similar. fragment DefinitionContent on Definition {
content {
textContent
}
subDefinitions {
...DefinitionContent
}
}
# Phrases are articles for phrases that include the current article
fragment PhraseFragment on Phrase {
phrases {
...PhraseFragment
}
}
query WordDefinitions(
$word: String!
$dictionaries: [Dictionary!]
$wordClass: WordClass
) {
word(word: $word, dictionaries: $dictionaries, wordClass: $wordClass) {
articles {
id
dictionary
lemmas {
lemma
}
gender
wordClass
# Max 10 steps deep from this point onwards
# Server is configured to allow a max depth of 15 for this field.
definitions(#depth: 10) {
...DefinitionContent
}
# Error as recursion is not allowed here, default n is 0
phrases {
...PhraseFragment
}
}
}
} |
|
Stop talking about philosophy !!! |
Problem statement
GraphQL spec currently forbids recursive references in fragments - section 5.5.2.2:
The reasoning given is that reference cycles result in infinite loops - which is not always true. However, reference cycles, known as recursion in programming languages, can be useful in some situations, making GraphQL code shorter and cleaner while not causing any infinity problems.
Recursive references do not necessarily produce infinite loops. When a reference to a fragment (the owner fragment or other one forming a reference cycle) is inside a selection subset on one of the fields, the execution/unfolding the fragment(s) does not result in infinite loop (unless the data itself forms a loop at the same time, more on this later).
Example - type-unfolding fragment in GraphiQL introspection query
To unwrap complex type definitions for fields, the GraphiQL UI tool uses the following TypeRef fragment:
Not pretty to put it softly; unfolds the wrapped types only to a fixed limited depth, thus making an assumption of max type complexity.
The same information could be retrieved with a simple recursive fragment, if recursion was allowed:
There are many common examples of data reference chains that can be unfolded using recursive fragments. For example the corp hierarchy, the sequence of 'reports-to' links for an employee in a company. Microsoft Outlook has a UI form that shows the employee's chain of managers up to the top CEO, as shown in this article (scroll down to the pic of Organization tab):
https://blog.hyperfish.com/get-the-most-out-of-your-organizational-charts-in-office-365
Retrieving the entire managers list can be easily done using a recursive fragment. Without recursion, we have to make an arbitrary assumption about number of subordination levels (which can be high in large corp like Microsoft), and then explicitly encoded it in a multi-level fragment.
As a general observation, most (all?) programming languages allow recursion, at least syntactically, and none to my knowledge forbid using it. GraphQL spec stands out as a strange outlier, especially considering obvious good use cases as shown above.
Suggested Change
Change the section in spec to allow servers to allow circular (recursive) references; leave it to server implementation, to ALLOW them in selection subsets (new behavior) or FORBID them outright (old behavior).
General note : In this and many other cases I feel like the spec tries to dictate too much and go into excessive details about implementation of some simple matters. Honestly, it feels like insult sometimes, as if I do not know the potential dangers of recursion and need these excessive explanations with examples. It's not just me, as a server developer; I feel we insult reader's intelligence in general, no matter his/her specific expertise. In the case of recursive fragments, instead of putting all this text and examples etc, we could just put a simple reminder - beware of circular refs, they can result in infinite resolution loops.
Potential Objections/Challenges
Recursive fragments can result in infinite loops if data references form a loop.
Fix: Can be easily detected by the server; the engine needs a counter of current fragment depth, and a check/circuit breaker terminating execution when this counter exceeds some reasonably high number. In general, it is much 'easier' to abuse a GraphQL server by a rogue client than RESTful API. So the GraphQL engine must necessarily have multiple circuit breakers to prevent abuse or excessive resource hogging by mistake. The extra counter for fragment depth is just one of multiple limiting counters inside the engine, and should not be a challenge.
Potential impact in breaking existing implementation
The impact should be very low or none at all. The suggested change is to ALLOW servers to ALLOW recursive fragments, but server implementers are free to forbid them as before. Thus old servers are automatically compatible with new spec.
Test implementation
The recursive fragments are implemented successfully in [NGraphQL] (https://github.com/rivantsov/ngraphql) framework. There is a unit test in the solution that uses a recursive TypeDetails fragment (slightly modified here, 'displayName' in actual test is another ext of standard irrelevant here):
This fragment is used to unfold the type of the 'list' member:
The test printout (request and response) can be seen here:
https://github.com/rivantsov/ngraphql/blob/master/misc/UnitTestsLog.txt#L655
Note that the server uses static analysis of the query (pre-execution) to detect circular references at the top level (not in subsets) and rejects such queries outright. It uses run-time depth counter to detect infinity loops in data and returns runtime error.
The text was updated successfully, but these errors were encountered: