GraphQL 查詢成本分析的原則性方法

1. 簡介

GraphQL 透過允許客戶端精確指定其所需資料，徹底改變了網路 API 的設計。然而，這種表達能力也為服務供應商帶來了重大風險。一個單一、結構不良的查詢可能請求指數級的資料量，導致伺服器負載過重、成本增加，並可能引發阻斷服務攻擊漏洞。實證研究顯示，許多 GraphQL 實作都面臨此風險。本文旨在解決一個關鍵缺口：缺乏一種原則性、準確且高效的方法，能在執行之前估算查詢成本。

2. 背景與相關工作

目前 GraphQL 成本分析方法存在不足：

• 動態分析：執行查詢或探測後端。準確，但對於即時請求過濾而言成本過高（例如，Hartig & Pérez, 2018）。
• 現有靜態分析：通常過於簡單（例如，計算查詢節點數量）。它們未能考慮常見的 GraphQL 慣例，如列表大小、查詢參數以及介面/聯合類型，導致成本被高估或低估（例如，GraphQL Complexity 函式庫）。

本研究定位為首個提供可證明正確的靜態分析的工作，其複雜度為線性，且可配置以符合實際的綱要慣例。

3. GraphQL 語意形式化

本分析的基礎是對 GraphQL 執行語意進行新穎且嚴謹的形式化。此形式模型精確定義了：

• 查詢與綱要的結構。
• 欄位的解析，包括巢狀物件和列表。
• 查詢參數（例如 `first`、`limit`）對結果大小的影響。

此形式化超越了 GraphQL 規範的文字描述，使得對查詢執行路徑及其相關成本進行數學推理成為可能。它將 GraphQL 綱要視為類型的定向圖，其中欄位是邊。

4. GraphQL 查詢複雜度衡量指標

本文定義了兩個主要的成本指標，反映了不同利害關係人的關注點：

1. 伺服器成本 ($C_s$)： 模擬解析器函式執行的工作量。它是查詢深度、廣度及估計列表大小的函數。形式上，可以表示為查詢路徑的總和：$C_s(Q) = \sum_{p \in Paths(Q)} \prod_{f \in p} weight(f)$，其中 $weight(f)$ 估計欄位 $f$ 的基數。
2. 回應大小 ($C_r$)： 模擬 JSON 回應中的資料量，直接影響網路傳輸。它與回應樹中的節點數量密切相關。

這些指標由 API 開發者提供的簡單配置進行參數化（例如，預設列表大小 = 10，最大深度 = 7）。

5. 線性時間靜態成本分析

核心技術貢獻是一個在O(n) 時間和空間內計算 $C_s$ 和 $C_r$ 上限的演算法，其中 n 是查詢文件的大小（AST 節點）。

演算法概述：

1. 解析與驗證： 將查詢解析為 AST 並根據綱要進行驗證。
2. 標註 AST： 根據節點類型（物件、列表、純量）和配置的權重，為 AST 中的每個節點標註成本變數。
3. 傳播成本： 透過一次由下而上的遍歷，將成本估計從葉節點傳播到根節點，對巢狀列表應用乘法，對兄弟欄位應用加法。
4. 提取上限： 根節點的標註包含最終的成本上限。

該分析正確處理了 GraphQL 的特性，如片段、變數和內嵌參數，並將其整合到成本計算中。

6. 評估與結果

該分析在一個包含來自兩個商業 GraphQL API（GitHub 和一個私有企業 API）10,000 個真實查詢-回應配對的新語料庫上進行了評估。

圖表解讀（概念性）： 散點圖將顯示，對於所提出的方法，計算出的上限（x 軸）與實際回應大小/時間（y 軸）之間存在強烈的正線性相關性，點聚集在 y=x 線附近。而簡單方法的點則會廣泛分散，遠離這條線。

7. 分析框架範例

情境： 一個部落格 API，查詢用於取得文章及其評論。

綱要配置：

type Query {
  posts(limit: Int = 10): [Post!]!  # weight = 'limit' argument
}
type Post {
  title: String!
  comments(limit: Int = 5): [Comment!]! # weight = 'limit' argument
}
type Comment { text: String! }

查詢：

query {
  posts(limit: 2) {
    title
    comments(limit: 3) {
      text
    }
  }
}

成本計算（手動）：

• 根 `posts` 列表大小：2（來自 `limit` 參數）。
• 對於每個 `Post`，巢狀 `comments` 列表大小：3。
• 伺服器成本 ($C_s$) 上限： $2 \times (1_{title} + 3 \times 1_{text}) = 2 \times 4 = 8$ 次解析器呼叫。
• 回應大小 ($C_r$) 上限： $2_{posts} \times (1_{title} + 3_{comments}) = 8$ 個 JSON 物件。

該分析遍歷查詢一次，應用這些乘法規則，得出上限 8。

8. 未來應用與方向

此原則性成本分析開闢了多個方向：

• 自適應速率限制與定價： 從基於請求次數的模式轉向基於成本的定價模型（類似 AWS CloudWatch Logs Insights），客戶端根據計算複雜度付費，而不僅僅是 API 呼叫次數。
• 查詢最佳化與規劃： 與資料庫查詢規劃器（例如 PostgreSQL、MongoDB）整合用於 GraphQL，類似於 SQL 最佳化器使用成本估算的方式，如 Hasura 等專案所探索的。
• 主動式綱要設計： 在開發期間審計 GraphQL 綱要是否存在 DoS 漏洞的工具，建議分頁限制或深度限制，類似於安全性的 ESLint 規則。
• 聯合式 GraphQL 成本分析： 將模型擴展到估算聯合式架構（Apollo Federation）中的成本，其中查詢跨越多個子圖，這是 Apollo 工程團隊指出的重大挑戰。
• 機器學習整合： 使用歷史查詢/回應資料來自動學習並精煉欄位的 `weight` 參數，從靜態配置轉向動態、資料驅動的成本模型。

9. 參考文獻

1. Hartig, O., & Pérez, J. (2018). Semantics and Complexity of GraphQL. Proceedings of the World Wide Web Conference (WWW).
2. Facebook. (2021). GraphQL Specification. https://spec.graphql.org/
3. Wittern, E., Cha, A., Davis, J. C., et al. (2019). An Empirical Study of GraphQL Schemas and Their Security Implications. ICSE SEIP.
4. GraphQL Foundation. (2022). GraphQL Complexity Analysis Tools.
5. GitHub. (2023). GitHub GraphQL API Documentation. https://docs.github.com/en/graphql
6. Isola, P., Zhu, J., Zhou, T., & Efros, A. A. (2017). Image-to-Image Translation with Conditional Adversarial Networks (CycleGAN). CVPR.

10. 專家分析與評論