Divide and conquer

Traditionally, in algorithms, "divide and conquer" means splitting a task into independent parts, solving each part on its own, and merging the results. On Solana, the same pattern is used but for the purposes of architecting programs around the chain's constraints.

Context: On Solana, transactions are limited in size, programs are limited in compute (amount of operations), and every single change to a dynamic structure in an account rewrites the account fully (even if you change one byte out of a thousand, you write a thousand bytes again).

Pattern: Divide data into partitions that can be stored separately, while retaining a central storage for the result of those partitions. Users interact only with the very partitions they need in order to execute their actions, making the transactions as minimal as they can be.

Depending on the program specifics, Pay-As-You-Act can be utilized in order to update the central storage within the same transaction where the partitioned state is accessed. If it's not necessary or not optimal, the Pay-As-You-Act pattern may not be used.

• Orca DEX: All ticks are stored virtually, with only the active ones referenced in the programs directly. The ones that are inactive are not referenced in the program instructions, thus significantly optimizing the transactions.
• Compressed NFTs (Bubblegum): A million NFTs live in one account as a Merkle tree. Leaves are hashed in pairs, level by level, up to a single root, and that root stands for all million. To prove or change one NFT, the client brings the leaf and the hashes along its path, about twenty for a million leaves. The program recomputes the root and compares it with the stored one. The top levels of the tree are stored in the account (the canopy), so the client sends only the bottom of the path.
• ZK Compression: does the same for any account and adds one more merge on top: proofs for several accounts fold into one proof of fixed size, however many the transaction should touch.