For a long time, certain well-known properties of Black holes, such as the area form of the entropy as well as a long time-scale of information retrieval, have been considered to be mysteries. We explain that black holes turn out not to be exceptional in this respect. Instead, the above seemingly-mysterious properties follow from certain universal bounds on information storage and retrieval. They are imposed by unitarity and are fully non-perturbative. The objects that saturate these consistency bounds exhibit the properties identical to black holes. A long list of examples includes saturated solitons, instantons and baryons in renormalizable field theories. Perhaps the most striking example is the color glass condensate in ordinary QCD. We predict new observable phenomena for such objects, including black holes. We focus on the phenomenon of the "memory burden", the essence of which is that the information pattern stored by the system back-reacts and resists decay. For black holes, this predicts a dramatic deviation from usually assumed evolution, and has potentially important implications for primordial black holes as dark matter candidates.