When a bitcoin client sends a transaction to its connecting full nodes, before that transaction is confirmed, where is it stored? on all full nodes?
Full nodes keep a "mempool" of unconfirmed transactions, so yes, but every full node chooses its own rules for how many transactions it keeps in the mempool, e.g. minimum fee, maximum number of transactions, amount of time before the transactions drop out, etc. So not every full node keeps every unconfirmed transaction. If a node doesn't have a transaction in its mempool when a block is mined, it will just request that transaction.
The reply to your answer is: in the mempool.
What Is The Bitcoin Mempool?
The Bitcoin mempool is the pool of unconfirmed Bitcoin transactions on the Bitcoin network. Once a Bitcoin transaction happens on Bitcoin’s blockchain, it is not immediately added; instead, it goes into this pool of in-motion transactions.
Each running full node on the Bitcoin network is connected to this mempool. The miners, working at their respective nodes, collate a bunch of transactions from this mempool, and then they try to solve an energy-intensive math problem.
The collection of these transactions is called a “block”, and whichever miner first solves the math problem gets to add this block to Bitcoin’s blockchain. This is the first confirmation of that block.
So that is the mempool, but wait! There’s more to it…
The question is: how do certain transactions get picked out of the mempool before others?
Bitcoin’s block time is 10 minutes, but we all experience extreme delays from time to time in getting our transactions confirmed.
This happens because miners are not picking out our transactions from the mempool.
Miners win a lottery of 12.5 BTC every time they successfully mine a Bitcoin block. But apart from this fixed lottery of 12.5 BTC, miners also get a bonus amount of bitcoins for successfully mining a block. This bonus is called the “Bitcoin mining fee”.
So when a miner successfully mines a block, they get 12.5 BTC plus X amount of transaction fees, which is a cumulative sum of all the transaction fees in that block.
And that’s why it stands to reason that a miner will pick to mine the blocks in the mempool with higher transaction fees.
And this is the reason that our Bitcoin transactions sometimes get “stuck” in the mempool and are not picked up until several hours (maybe even days) later.