What is the difference between Memory and Storage ?
From both the EVM point of view and the contract design one.
They are analogous to memory and hard drive storage in a computer. The contract can use any amount of memory (as long as it can pay for it of course) during executing its code, but when execution stops, the entire content of the memory is wiped, and the next execution will start fresh. The storage on the other hand is persisted into the blockchain itself, so the next time the contract executes some code, it has access to all the data it previously stored into its storage area.
Memory is temporary. Storage is permanent. For example, you would perform intermediate computations using memory, and then save the result to storage.
Storage is a key/value store where keys and values are both 32 bytes. It is sparse (like a hash table), and there are no inherent gas savings from having two 32 byte values next to each other. Storing one of the values at key 1 and the other at key 1000, costs the same amount of gas as storing them at key 1 and key 2. (Gas savings from packing storage are still possible, such as fitting 2
uint128 values within a single key, instead of using 2 keys.)
Memory is a byte-array. Memory starts off zero-size, but can be expanded in 32-byte chunks by simply accessing or storing memory at indices greater than its current size. Since memory is contiguous, it does save gas to keep it packed and shrink its size, instead of having large patches of zeros. It's cheaper to have an array of length 2 storing 2 values, than an array of length 1000 where the values are at the ends of the array and the middle is all zeros.
The subtleties wiki explains further the gas costs for using memory:
The fee for expanding memory is determined via a subtract-the-integrals method. Specifically,
TOTALFEE(SZ) = SZ * 3 + floor(SZ**2 / 512) is the total fee for expanding the memory to
SZ 32-byte chunks (note: partially filled chunks are counted, so 33 bytes = 2 chunks), and if a particular operation expands memory from size
y, the additional gas cost is
TOTALFEE(y) - TOTALFEE(x)
Storage gas costs are a little simpler: 20,000 gas when a value is set to non-zero from zero; 5,000 gas when writing to existing storage or setting a value to zero; and a 15,000 gas refund when a non-zero value is set to zero.