The amount of memory being utilized to store token state information is monitored. In response to the monitoring, one or more actions are taken. For instance, if the monitoring indicates that too much memory is being used to store token state information, then one or more actions are performed to reclaim memory and/or obtain additional memory elsewhere. These actions may include informing one or more clients to reduce their cache sizes, thereby relinquishing tokens; reducing or eliminating one or more byte range token trees; and/or migrating the token server from one node to another node. If the monitoring indicates that additional memory can be used for storing token state information, then one or more client nodes are informed that their cache sizes can be increased.