Scaling XML Sitemap Protocol

Context: We operate a popular 'Free XML Sitemap Generator' web tool that's been performing really well for small to medium-sized websites. Our user base has grown significantly, and now we're seeing more and more sites with millions of URLs attempting to use our service. This is great, but we're hitting some pretty significant bottlenecks.

Problem: The core issue we're facing is scaling our sitemap generation process for these extremely large sites. Specifically, when we try to process URL lists exceeding roughly 500,000 entries, we consistently run into memory exhaustion or script timeout errors. Our current architecture, while optimized for typical loads, just struggles immensely with the sheer volume of data involved in such large-scale sitemap generation.

Attempts & Failures: We've definitely tried several conventional approaches to mitigate this:

• Incrementing memory_limit and max_execution_time in PHP (we've pushed it up to 4GB and 3600s, respectively). This only delays the inevitable or becomes completely unsustainable from a resource perspective on our shared hosting environment.
• Implementing chunked processing for writing the XML files (e.g., generating multiple sitemap_X.xml files and a sitemap.xml index). While this helps with the writing part, the initial URL collection and in-memory processing before writing still consume too much memory.
• Exploring different data structures for storing URLs before writing, including iterating over flat files with SplFileObject. However, the overhead of sorting or de-duplicating these massive lists can still overwhelm memory, even when trying to be file-based.
• Attempting to stream output directly, but the parsing and validation logic for correct sitemap protocol still requires substantial temporary memory, especially for ensuring uniqueness and proper XML structure.

Specific Technical Block: The most common failure mode we observe is a PHP Fatal error related to memory exhaustion during the URL aggregation or initial XML structure creation phase. Here's a typical log entry we're seeing:

[2023-10-27 14:35:01] PHP Fatal error:  Allowed memory size of 1073741824 bytes exhausted (tried to allocate 20480 bytes) in /var/www/html/sitemap_generator.php on line 147

This occurs even after allocating a significant amount of memory, which strongly suggests a fundamental architectural limitation in our approach rather than just insufficient resources.

Question: We're really looking for robust, scalable architectural patterns or specific strategies to efficiently handle the generation of XML sitemaps for websites with multi-million URL counts. Are there established best practices for memory management and efficient I/O in such scenarios that we might be overlooking? Has anyone here successfully implemented distributed processing or leveraged specific libraries (perhaps in Python or Go, if PHP isn't the right tool for this scale) that excel at ultra-large dataset manipulation specifically for sitemap protocol generation? Any insights on breaking down the problem beyond simple chunking would be immensely helpful. Help a brother out please...