مرتب‌سازی توپولوژیکی؛ کاهش بیش‌از 90 ساعت زمان و 3 میلیون کوئری

چطور با نگاه الگوریتمی به یک مسئله‌ی زنجیره‌وابستگی در فرآیند Data Migration تونستیم بیش از ۳ میلیون Query و ۹۰ ساعت زمان صرفه‌جویی کنیم. یه چالش سنگین که از یه مهاجرت ساده‌ی داده بین دو نسخه‌ی سیستم شروع شد، ولی خیلی زود تبدیل شد به یکی از پیچیده‌ترین تجربه‌های من در مدیریت dependency و performance شد.

---

شروع ماجرا

فرآیند مهاجرت داده بین نسخه‌ی قدیمی و جدید سیستم قرار بود ساده باشه؛ فقط یه migration script که داده‌ها رو از طریق API Call از نسخه‌ی قبلی می‌گرفت و وارد ساختار جدید می‌کرد.

اوایل همه‌چیز عالی پیش می‌رفت. روی داده‌های تستی (حدود 10 هزار رکورد) کل فرآیند ظرف چند ساعت انجام می‌شد و هیچ خطایی هم نداشت.

اما وقتی تست نهایی رو با دیتای واقعی اجرا کردیم — بیش از 300 هزار رکورد — همه‌چی از کنترل خارج شد: فرآیند بیش از 48 ساعت طول کشید و نزدیک به 30٪ از داده‌ها بدون هیچ اروری از بین رفت.

---

وضعیت اولیه

• حجم داده‌ها: بیش از 315,000 رکورد با روابط سلسله‌مراتبی پیچیده
• زمان پردازش: حدود 48 ساعت برای هر چرخه‌ی مهاجرت داده
• پایداری: شکست‌های مکرر به‌دلیل تداخل وابستگی‌ها
• مکانیزم Retry: باعث ایجاد حلقه‌های بی‌پایان و رفتار غیرقابل‌پیش‌بینی می‌شد
• از دست رفتن داده: نزدیک به 30٪ از رکوردها بدون هیچ هشدار یا خطای مشخصی گم می‌شدن

---

ساختار داده

سیستم، داده‌های چندین business entity رو در یک جدول ذخیره می‌کرد:

data_table:
├── id (auto-increment)
├── source_id
├── entity_type (orders, clients, products, etc.)
├── company_identifier
├── data (JSON)
├── target_id
└── relationships (parent/child references)

مشکل از اون‌جا شروع شد که چند شرکت مختلف از همون source_id استفاده می‌کردن:

Company A: Order ID 1, 2, 3
Company B: Order ID 1, 2, 3
Company C: Order ID 1, 2, 3

---

زنجیره‌های وابستگی

هر رکورد می‌تونست parent داشته باشه. بعضی زنجیره‌ها تا 24 سطح عمق داشتن:

Root Order (ID: 100)
└── Reorder (ID: 200, parent: 100)
    └── Reorder (ID: 300, parent: 200)
        └── Reorder (ID: 400, parent: 300)

یعنی رکوردها باید دقیقاً به ترتیب وابستگی‌ها وارد می‌شدن؛ اگر رکورد والد هنوز ثبت نشده بود، فرزند هم هنگام وارد شدن خطا می‌داد.

---

تحلیل مسئله

اولین نسخه‌ی اسکریپت یه رویکرد Retry-based داشت. هر رکوردی که parentش هنوز آماده نبود، دوباره توی صف retry قرار می‌گرفت.

for ($attempt = 0; $attempt < 10; $attempt++) {
    foreach ($records as $record) {
        if ($record->hasParent() && !exists($record->parentId)) {
            $retryQueue[] = $record;
            continue;
        }
        importRecord($record);
    }
    $records = $retryQueue;
    $retryQueue = [];
}

روی داده‌های کوچک خوب جواب می‌داد، اما در مقیاس واقعی تبدیل شد به Retry Hell با پیچیدگی باورنکردنی O(n²)

---

کشف بزرگ: ID Collision

وقتی لاگ‌ها رو دقیق‌تر بررسی کردم، متوجه شدم حدود 94 هزار رکورد گم شده. علتش ساده ولی دردناک بود: Duplicate ID بین شرکت‌ها.

foreach ($records as $record) {
    $graph[$record->data['id']] = $record; // Overwrites older entries!
}

در نتیجه، رکوردهای شرکت B و C داده‌های مربوط به شرکت A رو بازنویسی می‌کردن. مشکلی ساده در ظاهر، اما با تبعات بزرگ.

---

فشار روی دیتابیس

برای هر رکورد حدود 4 تا query زده می‌شد:

SELECT target_id FROM data WHERE entity_type='clients';
SELECT target_id FROM data WHERE entity_type='products';
SELECT target_id FROM data WHERE entity_type='orders';
SELECT data FROM data WHERE entity_type='products';

نتیجه: بیش از 1.26 میلیون Query فقط برای یه migration. عملاً bottleneck ایجاد کرده بودم.

---

راه‌حل: Topological Sorting

ایده‌ی اصلی

Topological Sort یکی از الگوریتم‌های پایه در Graph Theory‌ هست. ایده‌اش ساده‌ست: اگه از گره A به B یال داریم، A باید قبل از B بیاد.

در واقع می‌گه:

“هیچ Childی نباید قبل از Parentش پردازش بشه.”

---

گام اول: ساخت Dependency Graph

foreach ($records as $record) {
    $key = "{$record->id}_{$record->company}";
    if ($record->hasParent()) {
        $parentKey = "{$record->parentId}_{$record->parentCompany}";
        $graph['edges'][$parentKey][] = $key;
        $graph['parents'][$key] = $parentKey;
    } else {
        $graph['roots'][] = $key;
    }
}

با Composite Key (ترکیب id + company) تونستم مشکل collision رو حل کنم. هیچ داده‌ای دیگه overwrite نمی‌شد.

---

گام دوم: اجرای الگوریتم

function topologicalSort($graph) {
    $sorted = [];
    foreach ($graph['roots'] as $root) {
        visit($root, $graph, $sorted);
    }
    return array_reverse($sorted);
}

DFS-based و ساده. به محض تشخیص Circular dependency هم throw می‌کرد تا داده‌ی معیوب شناسایی بشه.

---

گام سوم: Smart Caching

برای کاهش Query load، تمام mappingها و نرخ‌ها رو یکبار preload کردم:

$clients = query("SELECT source_id, target_id FROM data WHERE entity_type='clients'");
$products = query("SELECT source_id, company_identifier, target_id FROM data WHERE entity_type='products'");
$orders = query("SELECT source_id, company_identifier, target_id FROM data WHERE entity_type='orders'");

از اون به بعد، همه‌چی از حافظه خونده می‌شد (O(1) lookup). نتیجه؟ از 1.26 میلیون Query به فقط 50 تا.

---

نتایج نهایی

معیار	قبل	بعد	بهبود
زمان کل پردازش	48+ ساعت	<10 دقیقه	99.7٪
Database Queries	1.26M	50	99.996٪
یکپارچگی داده	70٪	100٪	+30٪
Retry Cycles	10+	0	100٪
نرخ موفقیت	85٪	100٪	+15٪
پیچیدگی الگوریتم	O(n²)	O(n)	Linear Scaling

---

تفاوت در عمل

قبل از بهینه‌سازی

• روز 1: شروع مهاجرت
• روز 2: شکست‌های مکرر
• روز 3: تکرارهای بی‌پایان (retry loops)
• روز 4: از دست رفتن داده‌ها (data loss)
• روز 5: رفع خطاها و بازآزمایی
• روز 6: پایان فرآیند، با حدود 30٪ داده‌ی حذف‌شده

بعد از بهینه‌سازی

• دقیقه 1–2: بارگذاری و preload تمام mappingها
• دقیقه 3–5: ساخت dependency graph
• دقیقه 6–8: اجرای Topological Sort
• دقیقه 9–10: import کامل، بدون خطا

در مجموع فقط 10 دقیقه طول کشید؛ نه خطایی، نه داده‌ای از بین رفت. یه لحظه‌ی واقعی از همون حس‌های “بالاخره تموم شد!” 😅

---

دستاوردهای فنی

• حذف کامل Retry:
  از retry-based رسیدیم به dependency-resolved.
  O(n²) → O(n)

• تضمین Data Integrity:
  قبل: 220K رکورد پردازش‌شده
  بعد: 315K رکورد کامل
  علت: استفاده از Composite Key به‌جای ID تکی

• بهینه‌سازی کوئری:
  از 1.26M به 50 کوئری
  99.996٪ کاهش. دیتابیس نفس کشید، منم همینطور 😌

---

اگه این نوت رو دوست داشتی احتمالا از این یکی هم خوشت بیاد :)

---

جمع‌بندی شخصی

بزرگ‌ترین بهینه‌سازی‌ها معمولاً از refactor کردن کد نمیان — از تغییر زاویه نگاه میان.

اون لحظه‌ای که فهمیدم مسئله‌مون "data import" نیست، بلکه یه "dependency resolution problem" هست، همه‌چیز سر جاش نشست.

گاهی لازمه یه قدم بری عقب، تا بفهمی شاید کل مسیر اشتباه چیده شده بوده.

---

قدردانی کوچیک

از حمیدرضا عزیز (lopqto.me) بابت پیشنهاد استفاده از مرتب‌سازی توپولوژیکی و پیگیری و همراهی ارزشمندش توی این مسیر و از خودم — که بعد از بارها خوندن ویکی‌پدیا و لیت‌کد و نفهمیدنشون هنوزم نشستم و کد رو اصلاح کردم کمال تشکر و قدردانی رو دارم :))

در نهایت این‌که؛

یه مسئله‌ی 48 ساعته، توی 10 دقیقه حل شد — نه با زور CPU، بلکه با قدرت Graph Theory.

---