I've been having problems with part lag, does anyone know how to counter this?

StreamingEnabled should help for client-side lag (it is half of what you are describing in option 1), though that doesn't do anything for server-side lag. Roblox servers are fairly powerful, but you can only ask them to do so much before they start lagging. You'll need a way limit how much the server has to keep track of. If you're going for an infinite (or near infinite) terrain, there are only a few things I can think of that might work:

1. A non-Roblox game could store needed terrain information to disk when no player is near it. Roblox doesn't offer this functionality exactly, but you use either Datastores or HTTPService (requiring the renting/purchasing of your own servers) instead.

2. Use of math.randomseed can let you randomly generate a section of terrain the same way over and over again. Use this to "load" a chunk's default state. Keep track of any modifications players have made to the terrain and apply these changes onto the chunk after loading. Note that if players are likely to make a lot of changes to the majority of each chunk, this won't be worth it. Naturally you can combine this idea with #1.

3. You can increase the amount the server can deal with by using memory efficiently. I found the following results:

• Unanchored Part in workspace: ~9.9KB each
• Anchored part in workspace: ~2.7KB each
• Part with no parent: ~1.3KB each
• Integer in 2D lua table: ~0.016 KB each

With that in mind, if you can store each terrain block in memory as an integer (terrain type), you'll be able to store tons more in the server's memory than by using parts (a million integers takes up only 16MB -- not quite the 500 million you wanted, but still large)

Depending on how Roblox's Streaming service works, it may not know how to transmit duplicate parts efficiently. If this is the case, then it would be faster for your server to use a RemoteEvent to send the 3D table of terrain integers. The client would have a sample of each terrain type (and any other objects) so that it could locally recreate the terrain. (Meanwhile, the server itself would have few if any parts in the workspace, besides the players). You may want to experiment with both methods (using Streaming vs doing it yourself) and see which one performs better.

If terrain generation takes a long time, you may only want to do it when players get close to an area, and possibly spread it out over time (by using 'wait's so that the server can attend to other matters periodically -- otherwise the whole server will freeze for potentially a few seconds, or however long it takes to generate the relevant terrain).

In your game you mentioned to me you use Parts for your terrain. I believe that using Terrain would speed up both the server and client, even if you only use it for some blocks. (You may want to experiment to confirm whether this really is the case, of course). Roblox can display a lot more Terrain blocks than Parts, and I'd be surprised if Parts weren't slower than Terrain in terms of impact on server performance in general (even if the Parts are anchored) and certainly on memory usage. (I haven't tested out how much memory is used by the Terrain, but you could do this yourself -- I was just using the Performance window in Roblox Studio and generating 10,000 -> 1 million entitites, depending on memory usage).

I recall seeing in mining games where the lower bricks aren't created until they are needed. If you generate something 100 bricks high, 99 of those bricks are wasted while the player is on the surface (and they are all wasted if the player never digs down). Generate them only as needed.