всегда́ • (vsegdá)
The все part is related to весь meaning "all, every, the whole". The -гда ending is also found in когда, see the etymology there. This ending may have derived from the genitive of год (god, “period of time”). See also годъ, тогда.