Phần 6 cho thấy engine backtracking có thể bị một chuỗi vài chục ký tự làm treo. Phần 7 này mổ xẻ cỗ máy đã miễn nhiễm với điều đó: RE2 — engine regex của Go (regexp), của Rust (regex), và của Google (dùng trong nhiều hệ thống production nơi regex chạy trên đầu vào không tin cậy). RE2 không phải "nhanh hơn nhờ tối ưu vặt"; nó khác về bản chất thuật toán, và sự khác biệt đó vừa là điểm mạnh lớn nhất vừa là giới hạn của nó. Hiểu RE2 giúp bạn quyết định đúng: khi nào chấp nhận mất vài tính năng để đổi lấy an toàn tuyệt đối. Bài này (phần 7 loạt Regex) đo thật cả sức mạnh tuyến tính lẫn những gì nó từ chối.

RE2 chạy tuyến tính bằng cách nào

Nhớ lại phần 6: engine backtracking nổ vì nó thử từng đường đi một, quay lui khi hỏng, và số đường có thể mũ. RE2 dùng một ý tưởng cũ mà tinh tế (Thompson, 1968): thay vì thử từng đường, giữ đồng thời tất cả các trạng thái mà máy "có thể đang ở". Với mỗi ký tự input, nó cập nhật cả tập trạng thái một lượt.

Điểm mấu chốt: số trạng thái khả dĩ bị chặn trên bởi kích thước mẫu (hữu hạn, cố định). Nên xử lý mỗi ký tự tốn O(1) (theo độ dài input), và toàn bộ là O(n). Không có khái niệm "quay lui" nên không thể có bùng nổ mũ — bất kể mẫu viết thế nào. Đây là lý do RE2 nuốt trọn cả những mẫu "độc" như (a+)+b mà không hề hấn.

Ảnh chụp đoạn mã nền tối minh hoạ RE2 và Go regexp đánh đổi tính năng lấy tuyến tính Thompson NFA mô phỏng trạng thái song song không backtracking, RE2 chạy tuyến tính bằng cách nào engine backtracking thử từng nhánh quay lui có thể mũ bài 06 RE2 Thompson NFA thay vì thử từng đường nó giữ mọi trạng thái có thể đang ở cùng lúc rồi với mỗi ký tự input cập nhật cả tập số trạng thái nhỏ hơn hoặc bằng kích thước mẫu hữu hạn nên mỗi ký tự tốn O 1 toàn bộ O n không bao giờ backtrack không thể mũ, cái giá bỏ những gì cần nhớ hoặc nhìn hai chiều RE2 không hỗ trợ dấu hỏi bằng lookahead nhìn trước bài 08 dấu hỏi nhỏ hơn bằng lookbehind nhìn lui slash 1 slash 2 backreference nhớ đã bắt bài 05 vì chúng đòi backtracking hoặc bộ nhớ không chặn phá vỡ cam kết tuyến tính, đo lại tuyến tính trên mẫu độc nối tiếp bài 06 re MustCompile a cộng cộng b nested quantifier bẫy ReDoS for range 100 nghìn 1 triệu 5 triệu 20 triệu s Repeat a n tới 20 triệu ký tự a MatchString vẫn tuyến tính không treo, mẫu an toàn thì tương thích cả hai engine mẫu không dùng tính năng độc quyền chạy giống nhau trên RE2 và python b d 1 3 chấm d 1 3 lặp 3 b IPv4 dùng ở cả hai

Hình 1: RE2 giữ mọi trạng thái khả dĩ cùng lúc (Thompson NFA) thay vì thử-và-quay-lui, số trạng thái bị chặn bởi kích thước mẫu nên O(n); cái giá là bỏ lookahead/lookbehind/backreference (vì chúng cần backtracking hoặc bộ nhớ không chặn).

Đo thật: tuyến tính tới 20 triệu ký tự, và bốn lời từ chối

Ảnh chụp bảng kết quả chạy thật RE2 output thật go-lab Go regexp RE2 vs python re, a RE2 trên mẫu độc a cộng cộng b ns mỗi ký tự hằng số bằng O n n 100 nghìn thời gian 2.239375ms ns mỗi ký tự 22.394 n 1 triệu 21.956333ms 21.956 n 5 triệu 109.183375ms 21.837 n 20 triệu 443.535292ms 22.177 20 triệu a mẫu ReDoS vẫn O n input gấp 200 lần thì thời gian gấp khoảng 200 ns mỗi ký tự khoảng 22 cố định, b RE2 từ chối tính năng cần backtracking lỗi thật Compile d cộng dấu hỏi bằng px lỗi invalid or unsupported Perl syntax dấu hỏi bằng lookahead Compile dấu hỏi nhỏ hơn bằng đô la d cộng lỗi invalid named capture lookbehind Compile w cộng slash s slash 1 lỗi invalid escape sequence slash 1 backreference Compile dấu hỏi chấm than abc w cộng lỗi invalid or unsupported Perl syntax dấu hỏi chấm than neg-lookahead, c mẫu an toàn RE2 và python cho cùng kết quả mẫu b d 1 3 chấm d 1 3 lặp 3 b input IP 10.0.0.1 và 192.168.1.254 không phải 999.1 Go RE2 FindAll 10.0.0.1 192.168.1.254 python findall 10.0.0.1 192.168.1.254 cùng kết quả mẫu không dùng lookaround backref thì đổi engine không đổi kết quả

Hình 2: Chạy thật — (a) RE2 trên (a+)+b với n từ 100.000 tới 20.000.000 cho ns/ký tự hằng số ~22 (O(n), 20 triệu ký tự vẫn 443ms); (b) RE2 từ chối (?= (lookahead), (?<= (lookbehind), \1 (backreference), (?! với các lỗi khác nhau; (c) mẫu IPv4 an toàn cho cùng kết quả [10.0.0.1, 192.168.1.254] trên cả RE2 lẫn python.

  • Tuyến tính, kể cả trên mẫu độc: mẫu (a+)+b là loại đã làm python treo 9 giây ở 28 ký tự (phần 6). RE2 chạy nó trên 20 triệu ký tự trong 443ms, và ns/ký tự giữ hằng số ~22 khi n tăng từ 100.000 lên 20.000.000 (input gấp 200 lần → thời gian gấp ~200 lần). Đây là O(n) trần trụi, không có bất kỳ khả năng nổ nào.
  • Bốn lời từ chối, mỗi cái một lỗi khác: khi biên dịch các mẫu cần backtracking, RE2 báo lỗi thật và cụ thể: \d+(?=px) (lookahead) → invalid or unsupported Perl syntax: (?=; `(?<=\$)\d+` (lookbehind) → `invalid named capture`; `(\w+)\s\1` (backreference) → `invalid escape sequence: `\1; (?!abc)\w+ (negative lookahead) → invalid or unsupported Perl syntax: (?!``. RE2 cố tình không cài những tính năng này vì chúng phá vỡ cam kết tuyến tính.
  • Mẫu an toàn thì đổi engine không đổi kết quả: mẫu IPv4 \b\d{1,3}(?:\.\d{1,3}){3}\b không dùng tính năng độc quyền nào, nên Go RE2 và python cho đúng cùng kết quả [10.0.0.1, 192.168.1.254]. Với phần lớn nhu cầu thực tế (kiểm tra định dạng, trích token), bạn không cần lookaround/backreference — nên chuyển sang RE2 gần như "miễn phí".

Đánh đổi cần cân nhắc

RE2 không phải luôn nhanh hơn engine backtracking — nó đảm bảo không chậm thảm họa. Trên input "bình thường" (khớp được, không bệnh lý), engine backtracking tối ưu tốt có thể nhanh hơn RE2 nhờ các heuristic. Giá trị của RE2 không nằm ở tốc độ trung bình mà ở cận trên: nó không bao giờ rơi vào trường hợp mũ. Chọn RE2 khi bạn cần đảm bảo về worst-case, đặc biệt với input không tin cậy — không phải khi bạn chỉ muốn "nhanh hơn một chút".

Thiếu lookbehind/backreference đôi khi buộc viết lại mẫu — hoặc dùng code. Một số việc cần lookaround (ví dụ "khớp số không có dấu $ đứng trước") khó diễn đạt trong RE2. Cách xử lý: hoặc viết lại mẫu để không cần nhìn hai chiều (bắt cả phần ngữ cảnh rồi bỏ trong code), hoặc làm phần đó bằng code thường thay vì nhồi hết vào một regex. Đây là đánh đổi công sức, nhưng đổi lại là an toàn và dễ đọc.

Go có sẵn công cụ đo an toàn: regexp không có timeout vì không cần. Trong nhiều ngôn ngữ, bạn phải bọc regex trong timeout để phòng ReDoS. Với Go/RE2, điều đó không cần thiết — không mẫu nào làm nó treo, nên không có timeout để lỡ. Đây là một lợi ích vận hành ít được nhắc: bớt một lớp phòng thủ phải nghĩ tới. (Vẫn nên giới hạn độ dài input vì lý do bộ nhớ, nhưng không vì lý do thời gian.)

Ba ý mang về

  1. RE2 tuyến tính nhờ mô phỏng mọi trạng thái cùng lúc: đo thật (a+)+b (mẫu độc) trên 20 triệu ký tự chỉ 443ms với ns/ký tự hằng số ~22 — số trạng thái bị chặn bởi kích thước mẫu nên O(n), không backtrack nên không thể nổ.
  2. Cái giá là bốn tính năng cần backtracking: đo thật RE2 từ chối lookahead (?=, lookbehind (?<=, backreference \1, negative-lookahead (?! — mỗi cái một lỗi biên dịch cụ thể; chúng đòi backtracking/bộ nhớ không chặn nên phá vỡ tuyến tính.
  3. Chọn RE2 cho đảm bảo worst-case, không phải tốc độ trung bình: đo thật mẫu an toàn (IPv4) cho cùng kết quả trên RE2 và python, nên với phần lớn việc kiểm/trích, đổi sang RE2 gần như miễn phí và loại ReDoS tận gốc; chỉ khi cần lookaround/backreference mới phải cân nhắc viết lại hoặc dùng engine khác.

Nguồn

Phần sau ta xét chính những tính năng mà RE2 từ chối: lookahead và lookbehind — chúng cho phép "nhìn" mà không "nuốt", làm được gì mạnh mẽ, và vì sao cái giá của chúng lại là mất đảm bảo tuyến tính.