Nested results should multiply the complexity of inner results. Currently these are added.

For example the below query should have a complexity of 17 (1 query + 1 human + 5 * 3 (friends * children) );

 query { 
      human(id: 1) { 
          name, 
          friends(first: 5) { 
              name, 
              children(first: 3){ 
                  name 
              } 
          } 
      }
  }

Nested results with a complexity of 0 should not zero out outer results. In the above example if children resolved to a list of scalars, which have weight 0 then the overall complexity should be 7 (1 query + 1 human + 5 (friends ) and not 2 (1 query + 1 human + 5 * 0 (friends * children) );
;

TODO

• Enable the "with nested lists" tests in typeComplexityAnalysis.test.ts to verify resolution of this issue. (tests updated by #61).

Our token bucket algo is currently getting data from the redis cache and doing computations server side. 'Redis Functions' allow the redis store to carry out computations on the redis's side, which possibly decreases the number of requests made to speed up the algorithm. Try this out to see if it actually has any performance differences.

At the time of writing, the express rate limiter middleware function is sending a status code 429 when request is throttled. Refactor this to also send data like remaining tokens in bucket, requested tokens, etc. on the response.

Need to figure out if IP is always present on the request object or make this a requirement to process requests.

A full testing suite using jest should be written for the LeakyBucket class based on the spec decided on in issue #50. Tests can be modelled on those written for TokenBucket

Fragments should be added to the test suite for query complexity analysis.

Currently interfaces are not handled in the type weight configuration. We should consider the pros and cons of allowing these types to be configurable or simply have them default to the weight configured to objects.

A spec for the Leaky Bucket algorithm should be decided on prior to writing tests. The constructor should accept parameters for the following:

• capacity - Number of tokens each bucket should hold
• outlfowAmount - Number of complexity tokens added that can be processed at a fixed rate. Combined with outflowPeriod to create an outflow rate
• outflowPeriod - Time (seconds) that must elapse before tokens flow out of the bucket
• client - redis client instance

The LeakyBucket class must implement RateLimiter

This can be written in similar fashion to rateLimiters/tokenBucket.ts.

During initialization the user provides redis connection options. If the middleware fails to connect to the Redis server, it should throw the error from the redis client.

Get fragment tests to pass

Configure a Redis store to track the number of user requests and the current capacity of their token bucket based on their IP address.

Implement FixedWindow class per the spec in #51. The implementation should pass the tests written in #53.

In essence the Fixed Window algorithm rate limits requests by tracking the complexity of requests that are received in the current window and limits any requests that exceed the capacity.

Requests should be limited using IP address.

Complexity data should be stored for each user by connecting to a developer provided Redis client.

GraphQLNonNull types can wrap any GraphQLInputType. We should add tests and update buildTypeWeights and complexity analysis to ensure both incoming queries and schemas including non null types are accounted for and successfully parsed.

Per the GraphQL type def files GraphQLInputType can consist of the following types. Note the level of nesting that can occur.

GraphQLInputType = 
  | GraphQLScalarType
  | GraphQLEnumType
  | GraphQLInputObjectType
  | GraphQLList<GraphQLInputType>
  | GraphQLNonNull<
      | GraphQLScalarType
      | GraphQLEnumType
      | GraphQLInputObjectType
      | GraphQLList<GraphQLInputType>
 >;

should include noImplicitAny and strictNullChecks

A full testing suite using jest should be written for the FixedWindow class based on the spec decided on in issue #52.

See the notes below for implementation. The type weight object used in testing should be updated to reflect the implementation.

• type weight object used for all complexity analysis tests
• buildTypeWeights test 'fields returning lists of objects of determinate size'
• buildTypeWeights test 'fields returning lists of objects of indeterminate size'

Notes

The end goal is to have a function that can be used to calculate the total type complexity for a field by multiplying the arg value times the weight of the Resolved Type.

For example, if we receive a query reviews(episode: 'NEWHOPE', first: 5), the type complexity algorithm would call the function with the value of first the weight of a Review to get 5 * 1 = 5;

This function could be global that receives both arguments or a unique function could be assigned to each applicable field as below.

When looking up a field weight, we would check the type of the value. If the weight is a number, simply return the number otherwise call the associated function with relevant args.

We will also need to determine if the relevant information (variable names and resolve types) is available in the GraphQLSchemaObject or the AST created by parsing the schema object

first, last, limit are conventional keywords for limiting results. Later on we could make these keywords configurable to provide a more unopinionated solution.

Query {
  weight: 1,
  fields: {
    reviews: (type) => args[multiplierName] * typeWeightObject[type].weight
  },
}, 

Review {
  weight: 1,
  fields: {
    stars: 0,
    commentary: 0,  
  }
}

Iterate through the graphQL schema object to determine field weights for query cost calculation.

Input: graphQL schema object
Output: An object with properties as types and values as weights. These could be nested in some way...
example outpu:, schema has type user with feilds username and password

{
  name: {
    weight: 1,
    feilds: {
      username: 0,
      password: 0,
    }
  }
}

Unit Tests should be added for the Express Rate limiting middleware with a initial focus on using the Token Bucket algorithm.

Test should focus on testing the initial configuration steps as well as the returned middleware functioning as expected without testing the specific implementation details of each individual algorithm as these are covered by their own Unit Tests.

Once this issue gets picked up, our buildTypeWeightsFromSchemaObject should be creating the type weight object out of a schema with query and basic types AND PASSING THE TESTS. Extend this functionality to work for subscriptions.

• Write tests for this additional functionality
• Add functionality to the algorithm to pass the tests.

The mock for ioredis supports promises whereas the mock for node-redis does not

Once this issue gets picked up, our buildTypeWeightsFromSchemaObject should be creating the type weight object out of a schema with query and basic types AND PASSING THE TESTS. Extend this functionality to work for mutations.

1. Write tests for this additional functionality
2. Add functionality to the algorithm to pass the tests.

At the time of writing, the express rate limiter function is rate limiting requests by IP address by default. Add a configuration option to allow the developer to throttle requests by user ID or some other 'uuid'.

Use a TDD approach to verify correctness of the Token Bucket algorithm used for rate limiting incoming GraphQL requests.

Testing should not be concerned with computing an incoming requests complexity. Each request should be considered to consume 1 token.

Testing should verify the following;

1. Requests are limited as expected based on user IP address.
2. CAPACITY and REFILL_RATE are accepted input parameters.
3. Size of the token bucket never exceeds the set CAPACITY
4. Token bucket is refilled at the provided REFILL_RATE

Implement LeakyBucket class per the spec in #50. The implementation should pass the tests written in #52

The LeakyBucket algorithm works similarly to TokenBucket except that requests are processed at a fixed rate. The algorithm is usually implemented with a FIFO queue and works as follow:

• When a request arrives, the limiter checks if the queue is full. If it is not full, the request is added to the queue.
• Otherwise, the request is dropped (a 429 status is sent)
• Requests are pulled from the queue and processed at regular intervals

If the fieldWeight is undefined during complexity analysis then an unhandled error is thrown. These errors should be handled in development environments to provide clarity on why the fieldWeight is undefined. Production environments should attempt to default to a logical complexity value.

Currently thebuildTypeWeights tests for queries that resolve to lists of scalars or enums fail. The type weight for these lists should be set to the configured or default type weight for enums or scalars.

• TODO Enable tests under `fields returning lists of objects of determinate size and...the list resolves to an enum or scalar
• TODO Enable tests under `fields returning lists of objects of determinate size and...the list resolves to an enum or scalar and a custom scalar weight was configured

Related to #61

It is a known problem that eslint will error on prettier formatting if they are not configured to integrate with each other. There are many known solutions.

Implement a Token Bucket algorithm using TDD which limits requests based on a user's IP address and allows developers to provide the desired CAPACITY and REFILL_RATE (in milliseconds).

The algorithm should consider each request to consume exactly 1 token. It should not consider GraphQL query complexity when limiting requests.

The TokenBucket instance of a RateLimiter limits requests based on a unique user ID.
Whenever a user makes a request the following steps are performed:

1. Refill the bucket based on time elapsed since the previous request
2. Update the timestamp of the last request.
3. Allow the request and remove the requested amount of tokens from the bucket if the user has enough.
4. Otherwise, disallow the request and do not update the token total.

For more information on implementing a Token Bucket Algorithm see the following resources:

• https://www.alibabacloud.com/blog/throttling-solutions-in-standalone-and-distributed-scenarios_596984#:~:text=Redis%20can%20easily%20implement%20the,hash%20data%20structure%20of%20Redis.
• https://en.wikipedia.org/wiki/Token_bucket
• page 54 of System Design interview (pinned in Slack)

Currently buildTypeWeights only generates a WeightFunction for queries that live on the root Query type. This functionality should be expanded to handled queries resolving to bounded lists that live on any type.

• TODO Enable tests under fields returning lists of objects of determinate size and...are not on the Query type to show resolution of this issue.

When analyzing the complexity of a query that returns a bounded lists, the length of the list is currently determined by searching the provided parameters for one of three limiting keywords first, last and limit. Currently, the algo only parses numbers when determining the value of these arguments. Update the algorithm to also parse use values pass as Variables.

This implementation should pass the tests added in #61.

• TODO Enable test a default value is provided in the schema...and a value is not provided with the query
• TODO Enable test `a default value is provided in the schema...and the argument is passed in as a variable
• TODO Enable test `a default value is not provided in the schema...and the argument is passed in as a variable

Once this issue gets picked up, our buildTypeWeightsFromSchemaObject should be creating the type weight object out of a schema with query and basic types AND PASSING THE TESTS. Extend this functionality to work for all additional GraphQL schema types, including lists, enums, interfaces, unions, and input types (is this just an object type). Figure out if there is anything else we need to account for.

1. Add functionality to the algorithm to pass the tests.

The primary entry point for our rate limiting middleware will be a function that accepts:

• rate limiting method
• GraphQL Schema
• optional TypeWeightConfig parameters and outputs Express middleware.
• redis client

Rate Limiter options should be presented as an enum consisting of Token Bucket, Leaky Bucket, Fixed Window, Sliding Window Log and Sliding Window Counter choices.

During configuration this function should:

• Setup a Redis Client
• Parse the schema using the provided or default TypeWeightConfig to obtain a TypeWeightObject.
• Configure the selected RateLimiter
• Configure complexity analysis algorithm using the TypeWeightObject
• Return express middleware based on the above configuration.

The middleware will need to be able to have access to the GraphQL query , a unique user identifier (such as IP) and request timestamp and will call the next middleware if the request is allowed or reject the request using a 429 status code if the rate limiter denies the request.

There are numerous ways to get the IP address off of the request object.

The header x-forward-for will hold the originating IP address if a proxy is placed in front of the server. This would be common for a production build.

• req.ips wwill hold an array of IP addresses in x-forward-for header. Client is likely at index zero
• req.ip will have the IP address
• req.socket.remoteAddress is an instance of net.socket which is used as another method of getting the IP address
• req.ip and req.ips will work in express but not with other frameworks

The token bucket parameter refillRate is being used to set the bucket refill amount for every 1 second. Add a parameter refillFrequency to adjust to time between refills other than 1 second. Maybe it defaults to 1 second and maybe the parameter refillRate needs to be changed to refillAmount. The end goal is to be able to configure the algorithm to refill at a rate of 10 tokens a minute, for example.

At the time of writing, the express middleware function is hard coded to use the type complexity algorithm for complexity analysis. Refactor this function to make the choice of resolve or type complexity analysis a configuration option for the developer.

At the time of writing, the express rate limiter function is responding to the client with a status code of 429 if the query has been throttled. Refactor this function to return the request with a "retry after" header set to the proper time duration in ms that the client should wait before retrying the request to be successful.

Create a class specification for RateLimiters in order to allow a user to interchange different ratelimting algorithms. Should exposing a constructor, method to check if a request is allowed and a method to connect to redis store

Implement the resolve complexity analysis algorithm. Include thorough testing of you implementation. Model this algorithm after the type complexity algorithm.

See issue #2

Create a test GraphQL query and schema object with a few types and feilds. Compare the output complexity against expected.

A spec for the FixedWindow algorithm should be decided on prior to writing tests. The constructor should accept parameters for the following:

windowSize - Size of the window in milliseconds
capacity - Number of requests allowed during the window
client - redis client instance

The FixedWindow class must implement RateLimiter

There are currently 5 r more parameters going into the express rate limiter function for setup. Over half of these are configuration options. Refactor the function to take in one config object that can be used to setup redis, algo settings and type weights for easier use by the developer.

The algorithm should do roughly these things.

1. Accepts a GraphQL query string and a 'field weight object' from issue #3
2. Parses the string and iterates through the AST
3. Counts and totals complexity by checking the query fields against field weight object
4. Returns the total complexity

Use the GraphQL.js library.

Variables should be added to the test suite for query complexity analysis.

see issue #3

Create basic schema and query. Test function against expected schema field types

when making a redis command like setex() or get(), if the connection to redis fails the function will fail silently. Refactor the algo to handle these edge cases.