OpenStack stack update failing with Internal Server Error (HTTP 500)

Issue

When doing a normal stack update operation, it can timeout and in the logs (/var/log/heat/heat-engine.log) you can see the following:

2019-11-29 03:22:03.123 7241 ERROR heat.engine.resource [req-40d3916a-999d-4f39-9991-3505a0656a85 - 7fcf41e657af44d39e36b8c6fa8b28ad - - -] Resource type OS::Heat::StructuredDeployment unavailable
2019-11-29 03:22:03.123 7241 ERROR heat.engine.resource Traceback (most recent call last):
2019-11-29 03:22:03.123 7241 ERROR heat.engine.resource File "/usr/lib/python2.7/site-packages/heat/engine/resource.py", line 184, in _validate_service_availability
2019-11-29 03:22:03.123 7241 ERROR heat.engine.resource (svc_available, reason) = cls.is_service_available(context)
2019-11-29 03:22:03.123 7241 ERROR heat.engine.resource File "/usr/lib/python2.7/site-packages/heat/engine/resource.py", line 711, in is_service_available
2019-11-29 03:22:03.123 7241 ERROR heat.engine.resource service_name=cls.default_client_name)
2019-11-29 03:22:03.123 7241 ERROR heat.engine.resource File "/usr/lib/python2.7/site-packages/heat/engine/clients/client_plugin.py", line 175, in does_endpoint_exist
2019-11-29 03:22:03.123 7241 ERROR heat.engine.resource endpoint_type=endpoint_type)
2019-11-29 03:22:03.123 7241 ERROR heat.engine.resource File "/usr/lib/python2.7/site-packages/heat/engine/clients/client_plugin.py", line 99, in url_for
2019-11-29 03:22:03.123 7241 ERROR heat.engine.resource keystone_session = self.context.keystone_session
2019-11-29 03:22:03.123 7241 ERROR heat.engine.resource File "/usr/lib/python2.7/site-packages/heat/common/context.py", line 149, in keystone_session
2019-11-29 03:22:03.123 7241 ERROR heat.engine.resource if self.auth_needs_refresh():
2019-11-29 03:22:03.123 7241 ERROR heat.engine.resource File "/usr/lib/python2.7/site-packages/heat/common/context.py", line 162, in auth_needs_refresh
2019-11-29 03:22:03.123 7241 ERROR heat.engine.resource auth_ref = self.auth_plugin.get_auth_ref(self._keystone_session)
2019-11-29 03:22:03.123 7241 ERROR heat.engine.resource File "/usr/lib/python2.7/site-packages/keystoneauth1/identity/generic/base.py", line 181, in get_auth_ref
2019-11-29 03:22:03.123 7241 ERROR heat.engine.resource return self._plugin.get_auth_ref(session, **kwargs)
2019-11-29 03:22:03.123 7241 ERROR heat.engine.resource File "/usr/lib/python2.7/site-packages/keystoneauth1/identity/v3/base.py", line 167, in get_auth_ref
2019-11-29 03:22:03.123 7241 ERROR heat.engine.resource authenticated=False, log=False, **rkwargs)
2019-11-29 03:22:03.123 7241 ERROR heat.engine.resource File "/usr/lib/python2.7/site-packages/keystoneauth1/session.py", line 705, in post
2019-11-29 03:22:03.123 7241 ERROR heat.engine.resource return self.request(url, 'POST', **kwargs)
2019-11-29 03:22:03.123 7241 ERROR heat.engine.resource File "/usr/lib/python2.7/site-packages/positional/__init__.py", line 101, in inner
2019-11-29 03:22:03.123 7241 ERROR heat.engine.resource return wrapped(*args, **kwargs)
2019-11-29 03:22:03.123 7241 ERROR heat.engine.resource File "/usr/lib/python2.7/site-packages/keystoneauth1/session.py", line 594, in request
2019-11-29 03:22:03.123 7241 ERROR heat.engine.resource raise exceptions.from_response(resp, method, url)
2019-11-29 03:22:03.123 7241 ERROR heat.engine.resource InternalServerError: Internal Server Error (HTTP 500)

In this case the update was working on some nodes but failing on a bunch of them.